Google Code Jam 2021 World Finals
2021-08-22 | [Competitive programming]コンテスト前
さすがに緊張してて何も手につかない。Puzzle Square でパズル解いたりしてた
コンテスト
- A 問題を見る。図を見た時点でもうやる気をなくして飛ばして次へ
- B 問題を読んで考える。とりあえず問題文の条件から、各クエリの後での辺の数はすぐに求められて、追加するとしたらどの辺かまでは求めようと思えば求められることがわかったけど、そこから先がわからない。とりあえず飛ばす
- C 問題を読む。こういうゲーム系苦手なので、とりあえず飛ばす
- D 問題を読む。数え上げでとっつきやすい気がしたので本腰入れて考える。少し考えたら普通に解けることがわかったが、満点解はどこかでバグが出そう && O(N^2) 解はすぐ書けそうだったのでとりあえず O(N^2) を実装。サンプルが合ったので満点解 O(N log D) 書き始める。いろいろ混乱したりして時間使うがなんとか O(N^2) 解と一致するコードができて、送る。AC
- 順位表を見たら B がけっこう解かれていたので考え直す。クエリの対象は「L 以上 R 以下、mod M でほげ」かと勘違いしていたが、よく読むと「mod M でほげ」ではなく「M の倍数」だった。すると調和級数の式から、この「M の倍数」に当たる自由度は高々計算量を O(log E) 倍するくらいだと当たりがつけられて、結局 M=1 に帰着される (そもそも M=1 は部分問題なのでこれが解けないとどう転んでも無理)。その後も少し悩んでいたが、突如乱択 (頂点に乱数を割り当てて xor を見る) という天啓が降ってきて、少し考えたら十分高い確率で解けることがわかったので実装。途中混乱してやっぱり無理じゃね？→やっぱり OK ってなったりしたが AC
- E を考える。small はわりと自明 (深さ d までの頂点数を求めるのは行列累乗で O(N^3 log d)、あとは二分探索) で、どうせすぐ書けるので large もう少し考えてからでいいかなと思っていたが、順位表見たら提出がいくつかあって、この時間で large がそんなに解かれるとは到底思えなかったので「そういうことなのか？」と思って small 特化のコードを書く。AC
- このあたりで、とりあえず C で勝率はともかく合法手を実現するコードを書き始める。
- A, C, E-large どれやるか迷ったが、E-large は少し考えてかなり無理な予感しかしなかったので放棄
- A を考え出す。といってもなにをやればいいかはほぼ自明で、三角形の頂点のある X 座標ごとに区切って、各範囲内ではスコアが 2 次関数で表されるので、2 次関数 (の絶対値) のある範囲での最小値を求めるだけでよい。だけでよいが、2 次関数の係数を有理数で持っておく必要があるし、分母分子がかなり大きい値になりうる。少し書き始めるが、よく考えると 128 ビット整数ですら全然足りないことに気づき絶望する。一旦中止
- C をやる。まじで何も考察できる要素がないので、いろいろ実験してみることにする。配布された testing tool があまりに遅くて実験に支障をきたすので (実験的に勝率を評価するしかないが、100 回程度の試行ではゆらぎの影響が大きすぎるから、最低限 1000 回は試行したい)、コード内に testing tool 相当のものを書いた。なんとなく良さそうな戦略を試しても全然性能が上がらなくて困っていたが普通にバグらせていて、直したら subtask 2 までは余裕を持って通せそうな解ができたので送る。WA して慌てるが手元実行用の testing tool モードを切るのを忘れていた。直して送り、subtask 2 まで AC
- もう少しいろいろ試してみても subtask 3 は通らないし、配点的にも A をやったほうが良さそうなので、覚悟を決めて A をやることにした。C++ の多倍長ライブラリなんて持ってないので Python で書くしかないが、ただでさえ遅い Python 上で多倍長の領域でガンガン計算する必要があるのでかなり不安。なので手元で多倍長整数演算の時間のベンチマークを取ってみると、100 桁とかそこらでは桁数はあまり関係なくて、Python 自体のオーバーヘッドのほうがよほど問題っぽいことがわかった (※このベンチマークは加減算しかしていないので、今思うとすごーくいい加減) ので、Python を信じて実装することにした。
- 終了 5 分くらい前にサンプルが合ったので送る。なかなか結果が返ってこなくてめちゃくちゃ緊張する。TLE。ハァ！？
- 高速化の手段、Fraction (分数型) の分母を極力事前に通分しておいて除算を控えるしか思いつかないのでやり始めるが、かなり慎重にやらないとだめで、この作業を残り 4 分ほどで完璧にできる気がしなくて諦める
- 残り 2 分くらいで、PyPy を使えば多少ましになるのでは…？ということに思い至る。提出可能な言語一覧を見ると PyPy、ある！でも PyPy 2 と書いてある… 最初の提出は Python 3 で書いてあるのでそのままだと多分動かない。実際手元で Python 2 で動かすとエラーになる。大急ぎで Python 2 で動くように修正して、エラーが出なくなったところでサンプルも正しい答えが出てきたので、急いで送る (終了 13 秒前)。
- 当然 13 秒で何かできるわけでもないので終了。最後に送った A が通るかどうか気が気でない。なかなか返ってこないのでまた TLE のような気がして不安だったが、返ってきた結果を見ると AC。やった！！！！！！！！！
コンテスト後
- 順位表を見ると、最後の A の AC が効いて暫定 2 位まで上がっていた。E-large は最初から眼中に入れていないコードを出したので、点数が減ることは明確だったが、おそらく E-large は解いていたとしても tourist くらいのものだろうと予想していて、これなら入賞 (3 位以内) あり得るのでは？という気がしてくる。今までの Finals では終了時点でほとんど入賞見込みがなかったが、今回はそれなりに見込みがあるのでかなり結果発表緊張する
- 結果発表。かなり待ったあとで B と D の large が通ったことを確認して一安心。残りは E-large がどれくらい解かれているか…
- 残る結果発表が E-large だけという状況になり、順に open されていく。何一つ通らず落ちていく。
- tourist ならあるいは…？と思って見ていたが tourist ですら通せていないようで、少し拍子抜けする
- その後も軒並み落ちていて、4 位以下の順位が確定し、入賞が確定する
- 暫定 3 位 scott_wu も通せていなくて、2 位が確定！！！！！
- 結局誰も E-large 通せてなかった
感想
今まで GCJ Finals には 5 回出たものの、最高で 10 位という結果で、一度くらいは入賞くらいしたいと思っていたが、今回ついに 2 位入賞できて、本当にうれしい
問題に対するコメント
- A がなかったら多分ペナルティで負けていて入賞できなかったからあまり悪口言いたくないんだけど、かなり嫌い。解法自体「ちょっと面倒なやるだけ」で、その時点でもうあまり Finals に置いてほしい問題じゃないのに、有理数や多倍長を要求してきたりと非本質的な面倒要素が多い。
- B は普通の問題だと思う、特段面白いというほどではないが特に悪印象もなし
- C は、(およそ普段のアルゴリズム系コンテストではやらないような) 特徴量エンジニアリングを使って無理やり点数を取っていて、なんでこれで点が取れるのかまったく納得できなくて腑に落ちていなかった。せめてこれが自分の頭が悪いだけで、ちゃんと考察すれば理論的に勝率の下界を出せるものだと思いたかったが、解説を見てもそういう議論はまったくなくて「experimentally to be the best value」ということが平然と書かれていて、かなりもやもやする – 真の勝率は確かに存在するわけで、十分多い回数試行した結果を見れば統計学的に真の勝率の信頼区間を出せる、などはそれはそうなんだけど、それを正当性の証明にしてほしくなかった – 実験的にしか確率を見積もれないとしても、得られた確率に対して 100% の信頼がおける評価ができるならそれでもいいんだけど、今回の実験的方法では (どんなに 100% に近いといっても) 100% 正しい、ということは言えないはず – B も乱択で、提出するコードは (実用上無視できる確率で) WA する恐れがあるけど、こっちは模範解答は最悪時間かければ 100% 正しいものが得られるという意味で決定的に違う
- D も普通の問題 (ちょっと典型度が高いかも)。D-large の 35 点は高すぎじゃないか？という気がしたが、結局上位全員解いているのでこの配点はそんなに重要ではないという見方もできる
- E はちゃんと考えれば面白いことになりそうな気はするんだけど、そこまでたどり着けなかった
なんというか、かつての (2015 とか 2016 の頃の) GCJ は今で言う AGC みたいにアルゴリズムパズル的な要素が強かった印象だけど、今回のセットは A や C に見られるように問うてるものが違ってきているように感じた。