ICPC 2020 国内予選 参加記

振り返ると私とkort0nで今年の頭にもう1人のメンバーを探しているときは偉そうに「この瞬間の実力よりもモチベを重視しよう」などと言ってRubikunに声をかけたが、これは大正解で成長曲線の傾き的には今まさに抜かれようとしているあたりで、そうならないように頑張りたいところ。

なんやかんやで睡眠調整に失敗してかなり眠い状態で本番を迎えることになってしまい、普段は飲まない魔剤を買って臨む。

開始直後のページにアクセスできない焦りが収まってきたあたりでぬるっとコンテストが始まり再び焦る。

ABCは1問ずつ分担する方針だが自分は簡単目な問題にハマることが多く、低難易度埋めもしていて安定感のあるRubikunにBを任せて、Aをやることにしていた。 どうでもいいがふざけてあらかじめ書いていたAの入力形式が当たっていた。

Bまでは普通に進んでいたがkort0nがCが解けないというかやたら実行時間がかかるというかで大変らしい。 概要を聞くと高速素因数分解ライブラリで殴ればどうにかなりそうな気もするが解法もよくわかってないしパッと書ける気がしなかったので引き受けるのを渋る(カス)。 結局引き受けることになってよくわからないままkort0nの言ってることをそのまま実装する。 バグらせながらもしばらくして何とか通るが後から振り返るとかなり頭がついていなかった。

pの3乗根以下のpの約数xを全探索してxとp/xに分けた後、どちらをさらに分けるかの2通りを試してまた約数を列挙して…などとやっていたがxを3数の最小のものと思えばxをさらに分ける必要はないしpの素因数分解がわかっているのだから改めてp/xの素因数分解をする必要もない。

後ろの問題の解法が出てるわけでもなくただただCで詰まっているという最悪な時間帯が存在してかなりヤバい雰囲気が漂っていた。 実際順位表を見たとき10位台後半でこのまま終わってしまうのか？と思った記憶がある。

直前に付け焼き刃の練習をして構文解析モチベが高まっていてDを考えるが非構文解析パートの解法が普通にわからない。 が、Rubikunが冴えていてE、Dと立て続けに解法を出していてすごかった。

Dの実装が何故か重いと判断してまあ分割も明らかなので分担を提案して、Eをkort0n、Dを私とRubikunで全員実装しているという状態になってどちらも大体開始1時間後くらいのタイミングで通る。 この辺りで安心はできないものの普通の空気に戻った気がする。

丁度FのACが出始めていて解くべきっぽい問題だと悟り全員で取り組む。 考察を進めると最近冷えて悔しい思いをした問題に似ているので思い出しながらお絵描きをして共有をする。 なんかこれがヒントになったらしくkort0nが解法を生やし、そのまま実装を任せることに。

結局木を作る前半パートと木上で問題を解く後半パートがあって、自分は前半パートの実装単体でも苦労したことがあったのでかなり大変そうだと思っていたのだが、結果的には想定よりかなり早く実装が終わっていて流石だった。 どうやら自分が理解しきれてなかった後半パートがそこまで重くはなかったらしい。 この間はサンプルを手で作ったり愚直解と突き合わせるためのケース生成コードなどを準備しながらGをなんとなく考えていた。

実装が大変な割にやたら通されていて簡単な解法があるのかと思っていたが愚直を書いて待つという手法が自分はすっかり頭から抜けていた。

ともかくFが通って通過を確信し緊張感が切れる。 GからLP双対系の波動を感じちょっと考えたりしていたがHの概要を聞き「流石に辺同士が接するとして良くて（良くないが…）あとは三分探索+最小包含円で良くね？」などと言い出し実装を始める。 他人のライブラリをペタペタして実装するもサンプルの最後が合わなくて図示をお願いするとヤバいケースの存在が判明する。

エスパーにエスパーを重ねて実装を続けるも今度は計算時間が爆発して大変なことになっているうちにコンテストが終了した。

感想

とりあえずほっとしています3