国内予選 | ICPC 2020 Asia Yokohama Regional

ICPC Prelim < Challenges | Aizu Online Judge

結果

振り返り

序盤？

さあ、国内予選通過に向かってコンテスト開始だ！とあなたは意気込んでいるところかもしれないが、ちょっと待ってほしい。一つだけ先に忠告しておくことがある。それはコンテストに潜む謎の人物、サーバエラーのプロ・database broken の存在だ。

ということで、開始 10 分くらいコンテストサイトを閲覧できないというトラブルが発生していた。 Twitter 開いて「こどふぉった」とかツイートしたくなったが、反則なので耐えた。 しばらく待つと問題が見られるようになったので、若干動揺しながらもコンテスト開始。

序盤

模擬国内同様「ABC をさかなとおくらに任せて、D 以降を僕が読む」という作戦でいった。

AB は気がついたら通っていた。 C は特に高速な解法は出なかったが、$A, B$を約数全探索してもコンテスト中には間に合うだろうということで、さかなが実装。 ちょくちょく高速化をした結果、1 ファイル 3 分くらいで終わっていた気がする。

一方僕はというと、D も E も解法が浮かばない。D は順列なので bitDP か？と思ったが、上手く行きそうにない。 唸っていると、B を終えたおくらが D に合流。すると「結果の値$x$を固定して、$x$以下の集合を全探索すれば良くね？」と、すぐに解法が投げられる。 それを聞いた僕が実装して AC。FA だった。

D が終わってしばらくして、C も実行が終わって無事 AC。この時点では 1 位と、順調な滑り出しとなった。

中・終盤

3 人で EF に取り組む。

E はグリッドっぽいグラフの独立集合の個数を数え上げる問題なのだが、幅が$30$なので解ける気がしない。 「真ん中辺りを決めるとグリッドが分割されるんじゃね」みたいなことを考えていたがよく分からず、さかなに任せることに。

F はグラフの連結成分云々の問題で、E よりはなんとかなりそうだったので僕はこっちに集中する。

まず「連結成分のサイズの最大値が半分以下になるのは$\log N$回」ということに着目して、部分永続 UnionFind による解法を考える。しかしこれが上手くいかないことにすぐに気づく。 その後もしばらく考えていると、分裂していく過程を木で表現することを思いつく。 そうすると根(全部連結の状態)から BFS で分裂途中の集合を探索することができ、線形時間で問題が解ける。

色々詰めてからそれを実装したのだが、結構実装が重いのと頭が疲れていたのもあって苦戦。 それでも気合で実装を終え、もったいない 2 ペナを吐きつつなんとか AC。いいムーブではなかったが、コンテスト中に解けてよかった。

F が通った時点で残り 15 分ほどしかなく、さかなの E のデバッグを見守るしかなかった。 順位表を見ると 12 位で「今年も届かなかったか」と落胆していた。 が、よく見ると 10 位以上に東大が 2 チームしかいないことに気づき、東大の他のチームが上がって来ないことをずっと祈っていた。 結果として終了まで 12 位をキープし続け、国内予選通過となった(正式な発表はまだだが)。

反省

• 生活習慣を治そう。
• 今回の A-D も良いムーブだった。
• F が通せて本当によかった。
  • ちなみに後 8 分遅かったらボーダー落ちしてた。
• しかし E 以降はまだまだ改善の余地があると感じた。アジアまでにもっと力を付けたいところ。