AGC041

いやーtourist回面白かった。結果は普通だったけどなあ。

A - Table Tennis Training

問題文が異常に読みにくい。外国人が書いたものなので、翻訳が良くても文化が違うのだ。頑張って読むと内容自体は異様に簡単そうなので、3分くらい経過していたこともあり順位表を見てみる。するとWA（TLEとかの可能性は排除できないけどまあWA）の嵐。なるほど、距離が奇数のときは向きが変わるってことか（必ずしも端で出会うわけではない）。min(f(n, a, b), f(n, n - 1 - b, n - 1 - a)) という書き方で時間をかけて書いた（A<Bの制約がなかったほうが楽だった説まである）。

B - Voting Judges

簡単そうな設定で奥があるのすごい。V=1なら簡単なのだが、Vがでかいとライバルにも票を分配することになるので難しい。とりあえず、ある問題を採用できるかの判定を考える。これがO(N)でできれば二分探索で解ける。tourist回、前回もこの辺の問題で二分探索してなかったか（好きなのかなと思いながら解いていた）。さて、毎回その採用したい問題に投票するのは当然として、Aが自分以下の問題や、上位P-1個の問題にも毎回投票して損しない。残ったライバル問題も、自分が到達できるA_i+M以下までなら投票していい。逆にそれより多く投票したらダメだ。で、票の配り方が難しいと思ってたけど、M*V票をM個以下ずつなら自由に分配できることになんか気づいて（M個ずつV問に配ってから切り崩すイメージ）、これで解けた。

C - Domino Quality

N=2はできない。3はできる。4はできる。できるやつの倍数もできる。ここで、様子を見るために提出（こういう戦い方ができるの楽しい（これで正解なのではという疑いがなくなるのも大きいし、半分くらいACなのでフォーマットが正しい確認にもなる））。かなりWAが多いので、あまり惜しくない感じ。3以上なら常に可能という線も濃くなってくる。5はできた。3の周囲を囲えばいい。周囲を囲ってN-2やN-1のケースに帰着させるテクはありそう。しかし、7や11も簡単ではない。5だけ書き足してまた提出することも考えたが、そうしているうちに11ができてしまった。あまりにもケースバイケースすぎてこういうのが想定とは思えない。7ができない証明とかも思いつかないし、7もなんかできてしまった（碁石を使って考えていた）。終了時刻付近で考えていたのは、周囲を太さ1か2で囲うことで残りを必ず3の倍数にできて、3の倍数なら比較的密度をコントロールしやすい（そもそもN=3に密度の異なる2つの解があるしそれを好きな個数並べることで何でも作れそう）ので、全てのNについて可能なのではと。違うサイズの解を組み合わせる発想が出なかったのが残念。コンテスト中は、「N=7はできるのか？」とかが楽しいからついそっち考えちゃう。視野がせまい。