ICPC2016国内予選参加記

はじめに

チーム t9qmib としてnikollson, nola_suzと一緒にICPC国内予選に参加しました。結果は4完24位で、正式なアナウンスはまだですがアジア地区筑波大会への参加権を獲得できているはずです。

A問題

A問題の担当でした。2つ目の出力ファイルの作成時間を見ると6分でACしたようです。問題文の印刷が終わらないうちにACしてかなり良い調子。

B問題

nikollsonの担当。30分経過時点で通っていなくて嫌な予感がする。nikollsonの実力でこの時間にAC取れてないのはおかしい。途中でコーダーを交代して51分ごろにAC。図らずもB問題の担当になる。

C問題

素数定理を知っていたので、エラトステネスの篩みたいに書けば計算時間的には問題なく終わることに気づく。最大ケースが与えられていたことにはサンプルを通す段階で気づいた。B問題で詰まっていたので代わってもらい37分でAC。私がコーダーでした。

D問題

問題の概要を説明された時に「これ、TDPCで見た問題だ！」となる。TDPCのiwiの解法の方針は覚えていたものの、細かいところが記憶になかった。もやっとした方針を nola_suz 説明すると「区間DPってこと？」と言われ、そのまま nola_suz が漸化式を立ててコーディングすると64分でACした。強い。自分がiwiを書いたときバグに苦しんだ記憶があったから、バグが出て1時間ぐらいかかることを覚悟していた。

E問題

共有部分の表面積を辺の重みとしたグラフを作って、辺の重みの合計が最大になるような、連結な部分グラフを求める問題。ああでもないこうでもないと言いながら解法が立たずに苦しんでいた。コンテスト終了後にblue_jamさんがやってきて「いやぁ、E問題のEはEASYのEでしたね。」といわれる。一つの立方体は最大でも二つの立方体としか共有部分を持たないという制約を読み落としていたことに気づく。チームメンバーのうち2/3が制約を読み落としていた。

F問題

実装が重いやるだけ問題というnikollsonの直感。根付き木の同型判定を効率的にやる方法を知らなかったが、nola_suzが「ノードを訪れるときに '(' を、ノードから親に戻る時に ')' を文字列に追加するようにして、子から上がってきた文字列を辞書順にソートして親に上げれば良い感じに同型判定できるんじゃない？」と言って効率的に根付き木の同型判定ができることが分かる。完全にプロ。効率的な根付き木の同型判定のアイデアが出た時点で、E問題の解法が立たずに1時間何もしていない状態だったので、何もしないよりは書いていたほうがいいだろうという判断で実装に入る。この時点で残り1時間。途中、H問題の解法が分かったという声が上がったが、その時点で残り30分少々。チームメイトに残り20分時点までに一通りの実装が完了するが、残り20分でデバッグが完了する見込みは薄いことを伝えるが、F問題を解き続けたほうがいいという判断になった。結局間に合わず。1時間PCを占領したのに申し訳ない結果になってしまった。

ちなみに説明された解法はこんなの

G問題

よんでない

H問題

やるだけじゃないかという意見が出たが、この時点でコンテスト終了まで残り30分ということで、F問題を書き続けるほうがいいだろうという判断でコーディングせず。

感想

どう見ても5完セット。あわよくば6完狙う感じでやらなきゃだめだった。
A問題の実装、図らずもB問題の実装、C問題の実装、間に合わなかったF問題の実装を担当していました。チーム中レーティング最弱なのになぜこうなった。