ICPC2020国内予選参加記 - 橋梁管理日誌

NOSSさん（参加記）、まつしたさん（参加記）、まほろば（ぼく）の3人でチームChabashiraとしてICPC2020国内予選に参加した。

開始前

ネットに転がっている他人のライブラリをダウンロードしたり、サイコロを手元に用意したりしていた。チームメイトにModIntを投げておいた。

本番

ICPCがこどふぉった。結局10分遅れでスタート。

まつしたさんがA、自分がB、NOSSさんがCを担当。

Bは接触確認アプリの接触履歴と1人の感染者が与えられるので、感染者、感染者と濃厚接触した人、その人と濃厚接触した人、さらにその人と濃厚接触した人・・・の人数を数える問題だった。解法ガチャでなぜか最初にダイクストラ法が出てきたので実装を始めた。今思えば履歴を前から見ていって接触者たちをsetに入れていくだけで十分だったなあと、反省。

Bの実装中にまつしたさんがAを通し、やや苦しそうだったNOSSさんのCのヘルプに入っていた。

間もなくしてBを通すことができたので、チームメイト*2と相談して自分はDを読んでおくことにした。

Dは $n \leq 16$ 種類のアルファベットと2本の式が与えられて、その2つの式の出力を一致させるようなアルファベットの全順序の付け方の種類数を答える問題だった。制約的に $2^n$ 系の何か（いい線行ってた）か階乗の半分全列挙（全然違った）かな？とか思いつつ、解法をすぐには生やせずにいた。また、構文解析があるので嫌な気持ちになり、Eも少し読んでおいた。

Cで詰まっていたNOSSさんにDの概要を話し、自分はCに移った。少ししたところでNOSSさんがDの解法を生やしてくれて、問題なさそうなのでそのまま（ちょっと複雑になりそうな）実装に移ってもらった。

C問題は、正整数 $p < 10^{15}$ が与えられて、 $w \times d \times h = p$ を満たす整数 $(w, d, h)$ の組であって、 $w+d+h$ を最小化したときのその値を出力する問題だった。まつしたさんが既に遅い愚直解を回していた。その解法は、 $p$ の約数を列挙し、 $w$ を全探索、 $p/w$ の約数を更に列挙し $d$ を全探索する、というものだった。

Cは考えても考えてもわからなかったので、愚直解法を高速化する方針をとった。 $p/w$ の約数は全て $p$ の約数であるので、ここの列挙を飛ばすことにより若干高速化できると考えた。コードを書いているとNOSSさんが「Dの・・・」と言ってきたので、複雑だしバグったのかなあとか一瞬考えていた（失礼）ら「サンプルが合ったので投げます。」と言ってきた（！！）。D、AC。

Cの続きを書いて実行したら遅々として進まなかった。そこで $d$ の探索は $\sqrt{p/w}$ で打ち切るという枝刈りを入れた。さらにコンパイルオプションを-O2から-O3に変え、PCに向かって3人で感謝の言葉をかけたところめちゃくちゃ爆速になって笑いながらCを通した（想定解は何だったんですかね？）。1時間15分36秒で4完になったので、自分の中ではいいペースかなあと思っていた。

もしかしたら5完できるかも？という淡い期待を胸にEを考えることにした。Eは60行60列のグリッドから桂馬の位置（？）を同時に選ばないマスの選び方を数える問題だった。桂馬の位置の性質上30行30列の問題4つに分割できるね、もう半分になるとbitDPできるね、ってところで考察はストップ、Fに移ることにした。

Fは考察が行ったり来たりしながら計算量結局落とせてなくね？みたいな話をしつつ結局進まず。終了数分前にそれっぽいナニカを書いて投げるも合わず、そのまま終了した。

結果はABCD4完で全体33位、学内1位で（何事もなければ）予選突破です！

終了後

学内の他チームのメンバーやコーチ、今回参加しなかった部員等を交えて感想戦っぽいものをした。学内の他のチームも2完以上しててよかった。C問題は他チームもゴリ押しで通したっぽい。高度合成数とか約数の個数は意外と少ないみたいな話をして、だからICPC国内予選では許されるくらいの速さにはなるのかなどと話していた。ツイッターに流れていたE問題の解法をみんなで吟味しながら天才か？とか言い合った。

感想

しっかりと各々が力を発揮できそう、解けそうな問題を担当するような動きが結果としてできていたと思う。Cで詰まったのがちょっと痛かったが、そこからのリカバリーがうまく行ってよかった。自分はとりあえずBをさっさと通し、Cも結果的に自分の力で（要出典）通せたのでチームに貢献できたということにしておく。チームメイトがどう思っているかは知らない（）

そして何より、めちゃくちゃ楽しかった。~~曲がりなりにも~~4完になった瞬間の喜びや、5完行けるかも？と思いつつ最後の最後まで取り組み、Fのコードをなんとか書き上げたときの熱さはとてもよかった（結局Fは通せなかったが）。アジア横浜大会はぜひオンサイトでやりたい、来年度もまた参加したいと思えるようないい大会だった。

p.s.
チームメイトのみなさん、一緒に戦ってくれてありがとうございました。アジア横浜大会でもよろしくお願いします。