いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

硬派パズル,the Sequence [2]の紹介

はじめに

この記事は「プログラマーにオススメしたいゲーム紹介 Advent Calendar 2018 - Adventar」の18日目です.
なんか最近スマホゲーとノベルゲーくらいしかやってないのでスマホゲーで面白かったパズルを紹介します.
似たようなものがsteamに転がってた記憶があるのでそっちやった人には物足りないかもしれないけど後半の難易度は凄まじいのでそう言う方にも是非

概要

iOS版,Android版があります.

the Sequence [2]

the Sequence [2]

  • Maxim Urusov
  • ゲーム
  • ¥240
play.google.com


値段は240円(iOS),220円(Android)です,僕のご飯3食分です.
因みに[2]と言うだけあって1もあります.

[the Sequence]

[the Sequence]

  • Maxim Urusov
  • ゲーム
  • ¥240
play.google.com

1では4方向だったのが2では6方向になってます,なにがやねん.

ルール

すごく基本的なルールとして,ユニットをゴールへ5回運ぶことが要求されます,簡単ですね.
f:id:ratetion:20181217003317p:plain
こんな感じの画面です,このゴールとユニットの周辺の何もないマスにシーケンスを配置してゴールまでユニットを運ぶのが目的となります.
5個運ばないといけないので注意が必要です.
f:id:ratetion:20181217003441p:plain
シーケンスはこんな感じで好きな数使えます,後半にいくにつれてシーケンスの種類が増えていきます,とりあえず置いて見ましょう.
f:id:ratetion:20181217003544p:plain
置きました,このシーケンスは矢印の方向に1マスユニットまたはシーケンスを押す効果があります.
置いた順,又は設定した順にシーケンスが動作して,壁にユニットをぶつけたりして動作不可能になるまで動作し続けます.
なのでこの場合はこの画像がこのままクリアとなります.
またどのシーケンスも押す,引くの切り替え等が可能で,1マス引く効果を持たせることもできます.
f:id:ratetion:20181217003737p:plain
基本ルールはこれだけです,シーケンスには他矢印の列に乗っているユニット,シーケンスを全て押し引きする,シーケンスの周辺を回す,シーケンスそのものの向きを回す,シーケンスの押し引きパターンを入れ替えるなどがあります.
全部で100ステージあるらしくて,僕は80ステージくらいで詰んでます.

序盤の例題

1問だけここで解いて見ます.
ネタバレになるのでここまでの僕の素晴らしい解説で書いたくなってしまった人はこの記事をツイートしてついでに星もつけて,そのあとブラウザバックして購入してきてください.

他にももう少しギミックがあるんですが,ここで解説した内容だけで解ける問題を選びました.
f:id:ratetion:20181217004136p:plain


解説

まずはじめに下のユニットを動かさないと始まりません,とりあえず下のユニットに対して引きます.
f:id:ratetion:20181217004436p:plain
これを動作させるとこうなります.
f:id:ratetion:20181217004759p:plain
今置いたシーケンスが邪魔になるので退けます,左下から押します.
f:id:ratetion:20181217004902p:plainf:id:ratetion:20181217004913p:plain
これでまた上に引っ張れるようになったのであとはゴールへ運んで,動かした1のシーケンスを戻してやればクリア.
f:id:ratetion:20181217005026p:plain
1個目のユニットをゴールまで動かしたあと,初期状態に戻っているのでこのまま動かせば5個同じように運べるのでクリアです.

これはステージ15とかなんですが,シーケンスが押せるみたいな説明がなかったのでINF時間溶けました.

終わりに

拙い記事で申し訳ねえ申し訳ねえ.
なんかアルゴリズムっぽいしパズルだし雑にプログラマーそう言うの好きやろがとか思って選んだんや,俺は好き.
まあ記事じゃ魅力伝えきれないし,ちょっとでもおっとか思った人は買って見てくれ.
240円あれば3食飯が食えるのでリスキーだと思った人はYouTubeに動画も少しは上がってるからそう言うの見てから買うか決めたらいいと思う.
ちんちん.
明日はfalさんがハースストーンの新環境やってから2週間たった感想を書くらしい.
奇遇にも僕もハースやってるんで個人的に勝手に楽しみにしています.
それでは.

ICPC2018 アジア地区横浜大会参加記(JAGサイド)

こんにちは,ICPC大好きおじさんのらてあです.
12月8-9日に横浜で行われたICPC2018 アジア地区横浜大会にJAGからボランティアとして参加してきました.
僕は去年は選手だったので去年の記事を置いておきます.
ratea.hatenablog.com

普段よりは少しだけ真面目に書きます,面白かった出来事は多分Twitterに書ききったのでそちらを.
何か書いててまずいことがあったら修正しますのでお教えください.

登録

JAGのslackにボランティア募集のメッセージが流れてきたのでとりあえずICPC用のSlackに参加した.
登録フォームに必要なことを書いて,集合時間とかわからなかったので備考欄に遠方からの参加のため間に合わないようなら不参加でお願いする旨を書いた.
クレタリーの方からメールが着てもう一泊用意するから7に横浜来れるなら宿泊して8の朝から参加しないかというメールで,予約の関係で至急返信するように書いてあったので条件反射で行きますお願いしますとメールしていた.
後になって,あまり想定されてないってことは遠方からの参加勢は自分だけじゃないか,ボランティア未経験の僕に交通費と宿泊費だけでわんさか出してもらっていいのかみたいな葛藤があった,手遅れなんですけど.

前日入り

出してもらう金額分の働きができるのか不安でしょうがないけどとりあえず新幹線に乗り横浜へ.
マニュアルを2回じっくり読んだ.
Yazaten,しょラーさん,odanさんとご飯へ行った.
しょラーさんとodanさんとは久々に会ったんですがなんかいつも通りで変な感じで楽しかったです.

8日

ホテルの朝食を食べて会場へ行って受付でTシャツと名札をもらう,しばらくして集合があって,4班くらいに別れて作業をすることになった.

午前

なんか一発で別れて,誰もこの仕事嫌とか言う事なくささっと分担してて(当たり前かもしれないけど僕はすごいと思った),人が少なそうなデバッグ班になった.
デバッグ班は主にIDEがクラッシュしないかとかを確かめるのが仕事で,片っ端からIDEを起動して世界に挨拶をしていた.
選手は3人だし3つ同時に起動しとけばええやろと思っていたら素晴らしいデバッグだとか言われてなんか面白かった.
他に配信チェックとかを確認して,大丈夫っぽかったのでふうせん班に合流した.
ふうせん班は紐に輪っかを作ってふうせんを取り付けヘリウムを注入する作業だった.
IOIで余ったドワンゴのボールペンがふうせん止めとして使われていてなんともシュールな光景だった.
practice用のふうせんを作りきったので,膨らませるのはやめて本番用の輪っかまでをある程度作って終了した.


どっかにいます.
ご飯を食べて再集合とのことだったのでお弁当をいただいた,さすがYokohama飯がうまい.
きゅうりさんと喋っていて僕の名字と僕のHNは知ってるけど同一人物とは知らなかったとか,自然言語は難しいとか外国人エンジニアは遅刻はするが終了時刻はキッチリ守るとかそんな話をしていた.

午後

practice準備が始まった,僕は英語が得意ではないんですが,英語に強い人がほとんど受付班になっていたのでアリーナ班になってしまった.
新幹線でマニュアルを2回読んだおかげで説明された内容を全て知っていました.
基本的にはアリーナを巡回して質問対応をする仕事で,わからなかったらセクレタリーを呼ぶようになっていました.
選手が続々入場して来たんですが知り合いが多すぎてあまり話すと怒られるので(不正の疑惑が出てしまう)ごめんねと言う感じでした.
オープニングが終わってpracticeが始まったので,巡回仲間がいなさそうな列を選んで歩く.
トイレ行きたいとか明日お弁当持ち込みたいとかペットボトルの蓋は閉めてねとかそんな事を英語で対応しました.
出来なくはないけどビビって声が小さいのを自覚していました.
中盤から足が痛くて辛かったけど考察の会話とかが聞こえて来て楽しかったです.
グラフを描いているチームやら,「森になるから」とか会話しているチームを見て混ざりたいと思っていました.

practiceが終わり選手たちが退場するとゴミの回収をし,翌日のパスワード用の封筒作成をしました.
封筒作成は紙をハサミで切る人とシールを剥がす人と貼る人とテープをちぎる人とテープを貼る人がいつのまにか出来てて,すごい効率で封筒が生産されていて,昔受けた授業で似たような作業をやって全然うまく行かなくて「作業って計画が大事でしょ?この講義ではそう言うことから学びます」とか言われたのを思い出したんですが,ここの人たちは初めからそれが出来るのか,同じ講義を受けたのかのどっちかだと思います.

その後僕を含めた3人を指名し「テレビを作って」と言われました.
正確にはテレビ台みたいなもので,割と組み立てが大変らしかったので説明書とにらめっこしながら組み立ててました,去年組み立てた人からも脅されるほどの難易度でした.
組み立てが終わるとJAGは既に解散してご飯に行ったとかで,残ったメンバーでご飯に行きました.
なんか晩ご飯代を出してもらえるらしくて,それ削ってチーム増やして欲しいとかぼやいたらチーム増やす金に比べたらずっと安いし英気を養って翌日頑張ってもらわないといけないからねと言われて,最初の方に書いてた交通費とか諸々もどうでもいいっぽいことに気づいて安心した.
中華街が近くにあってサイコーでした✌️

9日

開場まで

昨日組み立てたテレビを設置と準備しに行く.
なんかネットワークとかがゴタゴタしてコンテスト開始に間に合わなかったけど,ほぼ影響ないくらいで済んでよかった.

コンテスト

設置が済んだら急いでふうせん,印刷物配りに合流した.
こちらの仕事はシステム化されていてプリンター前係から受け取った印刷物にチーム名と解いた問題が書かれているか,さらに印刷物が渡されるので,指示に従って該当チームに届ける.
誤配はやってはいけないので毎回しっかり確認して届けるようにしていた.
1時間程度ごとにアリーナ巡回とふうせん配りを繰り返していた.
ふうせん配りを待っている間に問題を考察したり配信を観戦していて,盛り上がっていてみんなICPC好きすぎるし,善意というか好意というかそういうので成り立っているんだなぁと思った.
すごいエンジニアとかが無償でふうせんを運ぶお仕事をしている.
そんな感じで適宜アリーナとふうせんを行き来してるとコンテスト終了間際になった.
アリーナを巡回すると足が痛くなり,巡回から戻ると腰が痛くなりみんなすげえとか思ってたけどみんな足が破壊されたとか言っててみんなすげえ.
順位表が凍結すると,コーチ向けの順位表ディスプレイ(組み立ててたテレビ)がいらないので回収に行った.
解体して箱にしまう,組み立てた記憶が新しいからかすごい速度で完了した,RTAなら全一取れます.

懇親会まで

選手たちが退場し会場片付けが始まった.
ここでも何度か班分けとかしててみんな積極的に参加していて圧倒されるばかりだった.
ゴミ掃除とふうせん回収をして,椅子を収納,壁のふうせんも剥がしてPCとディスプレイを仕分けして移動,LANケーブルと電源ケーブル回収と仕分けなどをして人があまりはじめたので,Yes/Noおじさんを見に行っていいようになったのでホールへ移動して秋葉さんの圧倒的スピーチや順位発表を見ました.
秋葉さんかっこよかった.

懇親会

終電の影響で最後までいれないことがわかっていたので,セクレタリーの人に伝えて(すでにわかられていた,ありがとうございます)最後の片付けに参加できなくてごめんなさいと行って帰れる準備をしておきました.
懇親会では,競技終了まで選手との会話ができなかったので競技中に目があった人片っ端から話しかけに行ったり欲しいノベルティをもらったりして来ました.

帰りの準備をしていると,さっきのセクレタリーの人がいて,入り口付近におにぎりとかあるから新幹線ででも食べてと言ってくれたので移動中に頂きました.
帰宅し今に至ります.

ポエム

ICPCの手伝いをして思ったことですが


がおおよそ全てです.
記事内でも何度か書きましたが,作業効率がいいし積極的な人しかいないしすごかったです.
去年はわからなかったけど,本当にたくさんの人が携わって成り立っている大会であることがよくわかりました.
来年も可能であれば必ず参加したいと思っています.

とは言えどの仕事も人数はギリギリで,みんなが優秀だから成り立っているような印象を受けました.
あなたも次回から参加してみませんか?
と言うことでICPC引退後の方はまずJAGへ参加!
Join - ACM-ICPC Japanese Alumni Group
やっぱりこんなオチになりましたね,ここまで読んでくださりありがとうございました.

JAG夏合宿2011Day3F Beautiful Currency

問題

Beautiful Currency | Aizu Online Judge
数列が与えられる
数列の要素を変更してa_{i+1}%a_i==0になるようにしたい
仮にa_iからbに変えたいとき,変更コストを|a_i-b|/a_iとする
この変更コストの最大値の最小値を求める

考察

なんかDPっぽいんだけど制約が怪しくて間に合うかわからない
DPするならdp[i][j]を,数列のi番目の数をjにする時の最小コストとするとうまく行きそう
この時更新範囲はjの倍数の部分だけ行えばいいのでjを全探索すると
\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n-1}+\frac{n}{n}
になるのでO(NlogN)になる
これ知らんかった



ここで各aの変更する範囲が1e5ではダメでWAが出るんですけど,適当にどんなに大きくしても1e5*20でしょって思って出すとMLEする
答えは最大値の最小値なのでどんなに大きくても1以上にならないようにできるなぁと思うとa_n番目を頑張って変更する時が最大値になるのでa_n*2が最大とわかるので1e5*2まで変更すればいい

#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;
const int N_MAX=1e5*2+1;
 
signed main(){
  int n;
  cin>>n;
  vector<double> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  vector<vector<double> > dp(n+1,vector<double>(N_MAX,1e9));
 
  for(int i=1;i<N_MAX;i++){
    dp[0][i]=abs(a[0]-i)/a[0];
  }
 
  for(int i=1;i<n;i++){
    for(int j=1;j<N_MAX;j++){
      for(int k=j;k<N_MAX;k+=j){
        dp[i][k]=min(dp[i][k],max(dp[i-1][j],(abs(a[i]-k)/a[i])));
      }
    }
  }
 
  double ans=1e9;
  for(int i=1;i<N_MAX;i++){
    ans=min(ans,dp[n-1][i]);
  }
  cout<<fixed<<setprecision(20)<<ans<<endl;
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3265223#1

まあ解説記事とか見つからなかったし知見も得たのでとりあえず記事にしたけど解説になってるかわからん許して

CODE THANKS FESTIVAL 2018 参加記

どうもみなさん,らてあです.
11月25日に行われたCODE THANKS FESTIVAL 2018に参加してきましたので参加記を書きます.
いつものことなんですが時系列のクソポエムほのぼの日記です.
ついでに去年のはこれです.
ratea.hatenablog.com
一回twitterアカウントを消したので引用したツイート画像が見れなくなっててなんか申し訳ないです.
よろしくお願いします.

予選

予選Bで3完92位で通過しました.
予選Aで絶望してから精進したんですが,でた問題は閃き系であんまり意味がなかったなぁとかカッコつけて偉そうなツイートをしておきました.

前前日

なんか勢いで実況動画をあげました.

反響があればまたあげます.
反響があるならば次回がある-次回がないならば反響がない

前日

ゲームマーケット

当日開始時間が早いので前泊を用意していただけることになったので東京へ.
ちょうどゲムマをやっていたので11192916とreminさんと合流して試遊めぐりをしていた.
ボドゲも2つ買ってお家へ帰れるか不安な金額になる.

ばんごはん

TABくんとmonkukuiさんと合流して鍋を食べに行った.
僕もTABくんもお店を予約したことがなくてお互いにあわあわしながら新幹線から電話をかけたら相手がちゃんと聞き取ってくれなくて別の名字で予約されたけど無事美味しい鍋が食べれた.

ドワコン

3人でホテルで出ようとしたら僕だけ予約されてたホテルが別だったのでソロ参加になってしまった.
なんかbit演算部分でlong longを扱うときに1LLにし損ねたのを一生気付かずレートが消えて険しい気持ちになってしまった.

当日

起床フェーズ

7時におきた,開店凸を決めるために速攻で会場に向かった.
途中乗るつもりだったバスに乗り損ねて3駅分くらい歩いたけど無事到着した.
開場まで隣のスペースでルービックキューブとかやってた.

コンテストまで

会場に入るとIndeedTシャツを着ていたため社員さんに声をかけてもらったりした.
Tシャツをもらって着替えたりしてたらシンヤカトーが目の前にヌッって現れたりKokiYmgchが後ろからススッって現れたりYazatenが後ろの方からツイッターで僕の実況をし始めたり11192916が服を脱いだり着たりc7c7くんが颯爽と入場してきたり碧黴くんに名刺をもらって無修正すけべイラストはpixivにあると教えてもらったりしていた.
chokudaiさんに謝罪をしたらAtCoderステッカーをもらったので大切にしまっておいた.
fineさんの席をYazatenが暴露したので2秒であいさつしてきた.
隣の席の人が来てtwitterで見たと言われておよおよしながらあいさつしました.

オープニング

かっこいいBGMが流れ始めて社員さんがルール説明とかをし始めた.
パーカーは50位までもらえるって言われて会場内レート順位を確認すると87位だった,悪いイメージしかできなくなる.
パーカー大好きマンだし去年まるで手が届かない領域だったしどうしても獲得したかった.
なんでこんなに欲しがっているのか自分でもそろそろわからなくなっていた.
こどふぇすは学生しか出れないのでラストチャンスなんだよなぁとかぼんやり思ってたらオープニングが終わっていた.
弁当早食いフェスティバルをしました.
叙々苑弁当美味しかったです.
開始30秒前に入って来た人がいた,伝説の男minamiだった.

コンテスト

beta.atcoder.jp

A問題

去年はFA賞は風船が貼られるだけだった記憶があるのでまあいいやと思いながら適当に読む.
適当に場合分けを書いて投げてWAを出す.
あーこれよくないやつだと思いながらちゃんと読んでAC

B問題

難しすぎる,死んだわオイオイ
なんか雑に4引いたりして投げたりしてWAを量産した.

飛ばしてCDを通した後眺めるもわからないので全探索+randで提出しつつ,実行時間に余裕があればループ数を増やして投げ直すを繰り返してたらACした,これが最適戦略や.

C問題

どっかで見たことあるなと思った.
今振り返るとこれだった.
beta.atcoder.jp
どの問題だったかその場では思い出せなかったけど解法はわかっていたのでそのまま書いてAC.

D問題

なんか配点に騙されて誤読してWAを増やしたけど読み直したらあっさりAC.
落ち着きが足りなさすぎる.

E問題

DPっぽいなぁって思ってノートで詰める.
最初はO(n^2)でなんとかしようと思ってたけど明らかに遷移仕切れてないと気づいてO(n^3)を書いてみると数ケースしか通らない.
自分でテストケースを作ると重複して遷移している箇所が見つかったのでループの順番を変えて投げるとAC.
この時点で確か残り20分くらいで順位表を見ると凍結していたが53位までは凍結前にEまで通していて絶望する.

F問題

とりあえずダイクストラ貼って距離求めて和でなんとかしようとしてたが詰めきれず終わった.

コンテスト後

シンヤと11192916と喋ってたらちょくだいさんが来て
「君は出し過ぎ,もっと落ち着け〜〜〜〜」


って言われた.

シンヤに連立方程式は中学生でも解けるってバカにされた.
ブチギレ,許さん.
中学生が必死で解く連立方程式をマシンリソースで殴ってんだよこっちはなぁ!?

解説が始まるので席に戻って凍結解除された順位を見ると67位だった.
僕にしては健闘した方だしEよく通せたなと思うけど悔しすぎて指の爪が手のひらに刺さって流血していた.
こどふぇすパーカー通販始めてください,心の底からお願いします.
とはいえ去年は歯が立たなかった僕がまあまあ解けたので精進の成果はあったのかもなぁ.

解説を真面目に聞いているとちょくだいさんに煽られた.


あとで調べ直すとrandで通したのではなかったけど.

後半の問題もひょっとしたら発想できたなってところがあってEで時間溶かしすぎたのが悔やまれる.

懇親会

ヌメッと始まった.ヌエック.
コネクションビンゴは速攻でビンゴしたが3位だったのでノートみたいなやつをもらった.
寿司食ってかっささんと名字トークをしたりblue_jamさんとルービックキューブしたりtorusさんと闇深い(?)話をしたりヘクトさんとJAG夏の話をしたりけんしょうさんがシール配りをしていたりした.
色々ありすぎて一瞬で時間が過ぎ去ってしまった.
事あるごとにシンヤがパーカーを自慢して来たので次会った時に彼の人生が幕を閉じます.
会場出口で余ったお菓子とか配ってたんだけど何故か1.5Lのコーラが大量においてあって気がつくとカバンの中に入っていてなんで僕は筋トレしながら帰路につくんだ???って感じだった.
T.MくんとnoyくんとYazatenと帰りがまあ似てるし帰るか〜みたいな感じで一緒に帰った.
帰りの新幹線で永久にTwitterの通知がなり続けていて充電が死んだ,ぴょまえら許さん.
アンケートメールが来ていたのでパーカー売ってくれって答えといた,頼むぜ.
それはさておき真面目に答えた.

感想

結構頑張って思い出しながら書いたんだけど喋ってくれたのに名前出せてない人とかごめんなさい.
喋ってくれた人ありがとうございました.
最高のイベントでした.

ただしシンヤは許さない.

Codeforces Round #462 C. A Twisty Movement

問題

Problem - C - Codeforces

1と2のみからなる長さnの数列が与えられる。
1度だけ連続した区間を選びその区間の1と2を逆転させることが出来る。
最長増加部分列の最大値の長さを出力する。

考察

反転後の数列が
111...111222...222
みたいな感じであれば理想ぽい。
これの反転前を雑にイメージすると
111...122112...222
みたいな感じになる気持ちがある。
ある地点から左は1の個数を最大化、右は2の個数を最大化するような地点を全探索することを考える。
すると左の1の個数の最大化も右の2の個数の最大化も全探索すればいいので、累積和使って計算量を落とす。
累積和パートでO(N)
全探索パートでO(N^2)とかで終わり。

ソース

codeforces.com

添え字ミスには気を付けような

Mujin Programming Challenge 2018 感想

出ました
遅刻した
AtCoderからの”翌日のABC”の告知メールで気付いた

A問題

適当にやるだけ
ペナルティが無いと思って適当に書いて出した
長さが5未満の場合のケアをしてなかったけど通ってて笑う

B問題

適当にやりすぎてWAを量産した
最後に0人になると思ってたりとか
ペナルティないと思って、、、

C問題

ロボットの動きを考えると曲がる点が必ず存在するのでそのような点を全探索する
各点から4方向に進める長さを数えて掛け算
単純にこれをやったらTLEした(計算量見積もれや)
先に各マスに上下左右いくつ進めるかメモしておけばいいやんけってなったので雑にはい

D問題

意味不明
何かパターンがあるのかmodとか利用するのか何か色々模索してた
100ループくらいして0にならない物を列挙してみてその変化の仕方をしたら数ループで同じものに帰ってくるんじゃねえのって思ったけど解けず
解説見ても意味不明なのでそのうち解きなおします

AtCoder Regular Contest 097 D - Equals

問題

D - Equals

考察

入れ替える操作を何回やってもいいらしい
何回やってもいいってことは入れ替え出来る奴らは好きなところにおける
入れ替え可能なところに辺を貼るグラフを描けばわかりやすいけど,辺が貼られてるところ全部自由に交換できるみたいな感じ
数字全部検証する必要がある
UF木貼るだけ

"github beet library"
検索した
library/unionfindtree.cpp at master · beet-aizu/library · GitHub

さすがbeet大先生

AC
Submission #2939193 - AtCoder Beginner Contest 097

AtCoder Grand Contest 002 C - Knot Puzzle

解法

Lより長い場所を1つ確保すると,他は端から1区間ずる切り落としていけばいいことがわかる
連続したロープ2本分のmaxを取ってそれがLより小さければinpossible
L以上ならpossibleでその2本以外の両端から順番に切り落としていけばいい
計算量もO(N)それはそう

Submission #2905875 - AtCoder Grand Contest 002

AtCoder Grand Contest 001 D - Arrays and Palindrome

考察

回文で同じ文字で無いといけない部分に辺を張ると全部に辺が張れればいいとわかる
UF木を考えたけどaの並べ方の列挙とかが必要で間に合う気がしない
なにかこれができれば解けるってパターンがあると思った
もしくは絶対ダメなパターンを見つければいいと思ったのでサンプルを眺める
諦めて解説を読む

解法

http://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf
n点に対して最低でも辺の個数がn-1個無いと達成不可能であることがわかる
回文の性質から奇数長の回文1個につき張れる辺が1本減る
aの数列が全部偶数の場合,aの数列において張れる辺はN/2本
bもN/2本張れるようにすれば,aに含んで良い奇数長の文字列が2個以内だとわかる
あとは解説の図みたいな感じで繋いでいけばいい

Submission #2904435 - AtCoder Grand Contest 001

AtCoder Grand Contest 001 C - Shorten Diameter

解法

木の直径の性質を考えると,どの点からの距離も直径をkとするとのk/2になる点があるような気持ちになる(厳密ではない)
厳密には直径が偶数の場合は全ての点からの距離がk/2以下になる点が
奇数の場合は(k-1)/2になる”辺”が
それぞれ存在する
そのような点または辺を探してそれぞれk/2,(k-1)/2を超える点の数を数えればいい
点または辺は全探索しても間に合うのでO(n^2)で通る

Submission #2904096 - AtCoder Grand Contest 001