AGC029

反省点というのは体調管理(コンテスト中は、動きも立ち回りもよかった)。朝から微妙な感じだったのに、熱を測ったり休んだりといったことをしなかった。体調が悪いからこそ、気力がなくて休むこともサボってしまうというのはあるけどな。どうも頭がすっきりせず、直前に熱を測ると37.0。最近調子よかったから油断してたよ。なんでAGCのときに。体はべつにつらくなかったので、見ないふりをしてAGCに突っ込んだ(参加しないと異質の悔しさに襲われる)。頭が回らないので、遅解きで点数を稼ぐしかない。いかにもプロコンらしいC問題が、解ける状態じゃなくてね。体調が悪いときのコンテストというのは、とにかく楽しくない。苦しんで解き、ACを取っても少し安堵するだけ。ABDの3完で結果だけをもぎ取っていった(それによって精神の安らぎは得られる)。コンテストが終わって布団の中で測ると36.6だった。

A - Irreversible operation

右端の図を描いて考えていたところ、「これはswapじゃない、白石は存在せず黒石を移動させてるんだ」と気づいた。こんな天才は俺だけだろうと思い、急いでコードを書く。焦って(300早解きは早めに人権が得られて良い)ちょっと足がもつれるが、なんとか書き上げてAC。あとで順位表を見ると天才だらけだった(そういう意味でいい問題だと思う)。

B - Powers of two

Aの制約から、使える2冪は高々30種類しかない。2冪を一つずつ固定して考えていくか?いや、1,3,13,19みたいなとき3と13をペアにしたら1と19が余ってしまう。なんか最大マッチングぽいな。だが、計算量は?マッチングをよく理解してないね。計算量的には無理。経験がないからワンチャン行けるかどうかわからないんだよね。まあAtCoder的に想定解じゃないことは予測できるので、ちゃんと考える。最大マッチングだとしても何かいい性質があるはず。

さて、2冪を一つ固定すると、100000=11010+101みたいになる。少なくとも片方は100000の一つ下のビットが立っている。ただまあ、101も10とペアになれるんで、相手が決まるわけじゃない。もう少し考えて、ペアの大きいほうになることが確定していれば相手は一意に決まることに気づいた。グラフでいうと木になっている。木の最大マッチングだ。木は二部グラフの一種。二部グラフの最大マッチングは有名だから、木の場合とか有名に決まっているのでは?なのに自分は何も知らないし、ググってもよくわからない(そんなことある??)。まあ直接考えることもできそうで、葉ノードはその親とつながるしかないので(そういう性質から木だとわかったんだけど)適当に親とつなげてしまってよい(そうしないメリットは親がそのまた親とつながれることだけだが、同じペア数でより広いスペースを使っているのでデメリットしかない)。つまり、残ってる中で大きい数から順に見てその親と貪欲につなげていけばいい。しかし、木の辺を双方向で持つかとか色々あってかなり混乱した。O(N)では行けそうだけど、具体的に見えない。時間がどんどん溶けていく。ていうか木じゃなくて単に大きいほうから見ていけばいいじゃん。ソートして、二分探索で相手を見つける。mapを使う手もあるけどやはりいつも通りがいい。と思ったけど頭が回らないのでmap(じゃあ普段からmapがいいのでは?とも思ったけどそういう難しいことを考える余裕はない)。mapの使い方がいまいち確信が持てなくて、普段からやっとくんだったと思う。たとえmapでもlogはlogなので定数倍は気にしない!mapをどう使うか悩んでいた(当時は気づいてなかったがmapかsetかという話だ)が、同じ数が複数あるケースがあるので残ってる個数を入れる。あれ、大きい数が横入りしてくることない?(11111と1みたいに)って途中で思ったけど、ちゃんと順序が入ってるから大丈夫(そんなに自信はなかったが)。1が1とペアになることに気づき、1同士でペアを作る処理を追加。サンプル合わず、1000+1000=10000みたいなケースを見落としていた。まさに注意書きの「2番目のボール同士をペアにできないことに注意してください」じゃん!条件を追加してなんとかAC。

C - Lexicographic constraints

「無限に多くの文字があり」というところで、それってwell-definedなのかなN種類の文字でよかったんじゃないかなとか余計なことを考える。サンプルで2種類で済ます方法が書いてなかったので、そこにヒントがあるんじゃないかと自分で構成する。aaa,ab,b。雰囲気は出てる。文字数が増えていくなら、後ろにaを追加していくだけでよさそう。いや、逆から見て、減っていくなら文字を削っていくだけでいい、か?まあそのへんはあとで。Nが20万なので、Aが20以上なら同じ文字数のだけがいくらあっても2種類の文字で足りてしまう。また、1種類で済むかどうかは、狭義単調増加かですぐわかる。細かいところはおいといて、Aが20までと考えていいなら、なんか20桁のmax(A)進法を管理する感じで行けないかな。たとえば"cb"が現れたなら、その先に現れる5文字は"cbaaa"以上でないといけない。そういうふうに更新していく。二分探索も早い時期に思いついてた。使える文字数が固定されるなら少し簡単になりそう。むしろ、問題を簡単なものに分割できるならどんどんするべき。困難はこれからいくらでも出てくる。ただ、どの方針も頭がゴチャゴチャしてしまいなかなか先に進めなかった。かなり時間を使ったが、順位表を見てDへ。

D - Grid game

大して広くもない(メモリには収まらないけど)フィールドにいくつか障害物がある。高橋君は右に、青木君は下にだけ動かせる。パスもできるがパス自体も行動(高橋君の行動回数を答える問題)。連続パスで終局(囲碁みたいだなと思った)なので、高橋君がパスすると、行動回数を少なくしたい青木君は必ずパスし終局させる。よって高橋君は基本的にパスしない。青木君が(障害物があるなどでやむを得ない場合を除き)動くか動かないかを選ぶ(そして高橋君を障害物にぶつける)だけのゲームだ。

異様に簡単そうだが、800点なのでなんかあるだろう。まだ全然具体的な方針は見えないのでもう少し突っ込む。高橋君が毎回右に移動してるので、状況は単純。対角線より下には行けない。対角線上に障害物があったら青木君はそのマスに行けないので、そこから先は対角線より少し上にしか行けなくなる。なんか障害物があればそれに当てたいんだけど、そこに行ける保証はないので困る。いろんな障害物の配置を試して、紙の上で経験値を得る。たとえば、障害物が別の障害物に囲まれて到達できないとき、内側の障害物の左に必ず外側のがあるので、より青木君にとって優れた外側の障害物にぶつければいい。とりあえず可能な中で一番下に到達できるルートを求めるか。これ貪欲でいいか?ある横位置で上にいたほうがのちのち有利になるなんてことある?障害物があって進めないんならそもそもそこでゲームは終わる。つまり、下に行けるときは毎回下に行くことで移動可能な一番低いラインが得られる(もう時間もないし点数だけ得ようという魂胆なので考察は意識できる程度に雑)。もちろん、途中で動けなくなったらそこから先は考える必要がない。ここで、フィールドに端があることを思い出す。横だけじゃなく下も。大した修正は要らなさそう。さて、そのラインより上で最も左の障害物にぶつけることが実は可能なんじゃないかと仮説を立てる。そういう雰囲気がある。だって、防ぎようがないよね。より左に障害物がないんだから。ということで実装に入る。

実装するにあたって具体的な問題文を確認する必要がある。すると、今まで右に動いてると思っていた高橋君が下に動いていたあ~(実際に動いてるのは2人共通の駒だけど、脳内ではそう考えてる)。これはかなり厄介。実装をどちらの向きで行うかかなり迷う。ただ、hとiとxを結び付けるコーディングはAtCoderで慣れているので、きれいに書けばなんとかなるんじゃないかな。障害物の位置はsetで管理する。そのまんま書くだけ(実際には、細部のない考察を最低限埋めながら時間をかけて書いている)。遠い場所はラインの情報が入ってないことに気をつけながら書く(実際は遠いから値を更新しようがなく気をつける必要なかったっぽ)。けっこう混乱する処理で、更新する値を障害物の場所にするかそれとも高橋君が止まった場所かでかなり迷った(どちらでもいいけど、どちらが自然かという話)。サンプルにも助けられながら、合ったらわりとすぐ提出。ACで「よかったー」と思った。