ICPC 2022 Asia Yokohama Regional 参加記

優勝しました。すばらしい！

チーム編成

goodbaton さんが引退し、potato167 に新たに入ってもらった。 to 要素があったためチーム名は tonosama で続投。

開催まで

　12/5 の AGC で tatyam と potato が成功し、tatyam は自由色に、potato は noshi の rating を超え僕がチーム内最下位となってしまった (えー)。 12/26 (2 日前) の AGC で noshi が成功し、他 2 人も rating を増やして全員 3000 以上で本番を迎えることになりめでたい。予選の時と比べると僕以外の 2 人は目に見えて rating を伸ばしていて、チームパワーでガンガン押して行けそうな感じがする。

前日、リハーサル

　競プロオンサイトで常々思っていたことなのだが、他人が Twitter でいうところの誰なのかが分からないので、事前に Twitter で打ち合わせた人以外と会話するのが難しい。そこで、大きな厚紙にアイコンをプリントした紙を張り付けて、それをゴム紐で 2 枚繋ぐことでゼッケン風のものを自作した。 noshi91 と会話したいと思った人は助かったのではないだろうか。しかし会話はほとんどなかった。不思議ですね。

コンテスト

コンテスト中の時系列順にやったことまとめ。すでに記憶が前後しはじめていて、一部滅茶苦茶になっているかもしれない。

B

tatyam が環境構築、potato が A を読んでいる間に B を読んでいた。桁毎に二分探索するだけで行けそうだけど $x = 10 ^ {18}$ だけ何とかしないとなと思いながら実装を開始すると、 $x \lt 10 ^ {18}$ だった。 leading zeros ができてしまうので $\texttt{stoll}$ で上手くやってくれるか不安だったが tatyam に聞いたところ行けるらしい。テストを書いてみると盛大にバグっていたので直した。あぶね～ AC (0:21)

C

$\texttt{S,T,U}$ が外周にあるという条件を見落としたまま考察をする。最初最小カットを考えてコストが Monge で勝ったなと思ったが $\text{S,T}$ が連結という条件を表現できていないことに気付き停止。 $\texttt{S,T}$ と $\texttt{U}$ を分断するようなサイクルを 2 本引く問題と思い、 $\texttt{ST}$ パスと偶数回交わるなどの条件を付けて最小費用流を流そうとする。始点を全部試すと TLE なのでなんとかしたいなあと思いつつよく分からないので諦める。(今思い返すとサイクルが自己交差するという問題もありそうだ。しかし誤読しているのでそれ以前の問題である。)

F

tatyam から問題を言い換えたものを聞く。複数の数を 4 つのグループに分けて、全部奇数個で、合計が等しいペアを 2 つ作れるか？知っている問題ではなかったので少し考えて分からない旨を伝える。 tatyam は D を解くために 2 次元パターンマッチングをするべく FFT を書き始めていた。

G

potato から E や I や K や G の概要を聞く。 E は解法が分かったが、実装が面倒そうなので放置。 G を一緒に読み直したりしていると、グラフが木になるという制約も付いているらしい。じゃあどうせ簡単じゃね？→やっぱり簡単でした。 tatyam が D を AC (1:19) したのち、potato が G を書き始める。

F

tatyam が D を実装して potato が G を詰めている間、C に戻ってみたり他の問題を読んだりウロウロしていた。 D を AC して戻ってきた tatyam に、合計が半分になる集合を 2 つ作って交差させると 4 分割できるという考察を伝える。あとはそれぞれのグループが奇数個になればいいのだが、ランダムに取ってきたら上手く行くのではなど考えるが自信が無い。問題の言いかえ部分を詳しく聞きつつ考えていると、8 の字形にやれば全部奇数の代わりに全部偶数でも行けることに気付く。 potato が G をバグらせて一旦離れ、その間に tatyam が F を書いて通す (1:49)。そのまま potato もバグを直し、G を通す (1:52)。

E

チームメイトの実装中に残っている問題を並行して考えていたが大した進捗もなく、E を書くしかないということになる。 K の dp のそれっぽい方向性が分かってきたので potato に伝えて考察してもらいつつ、E を実装する。サンプルが合わないので一旦実装を渡して考えるが、数分で誤りを発見。修正すると通る (2:27)。

K

tatyam が H の考察を終えており、実装を始めている。 K を考えていた potato と考察のすり合わせをして、 $\Theta(m ^ 2 3 ^ n n)$ までは分かる。しかしギリギリ通らなそうな雰囲気なので考察を続行。左右に詰めるイベントは別々に考えてから合わせればよいと potato が気付き、計算量が $1 / n$ くらいになる。これで通りそうということで、また potato に実装を任せる。実装を任せすぎだが、noshi は実装がかなり遅いので最適な戦略なのではないかという気がする。

H

tatyam がサンプル 1, 2 を合わせるが 3 が合わないらしい。考察を聞いてみるが特に誤りは見つからず、別の問題の考察を開始。 potato が K の実装を詰めたりデバッグしたりするのと tatyam が H のストレステストを書くのとで PC を行ったり来たりする。 potato が K を AC (3:44), tatyam が H を AC (3:51)。連続 AC で一気に順位を上げ安堵しそうになるがまだ 2 問通す気持ちで頑張る。

I

実装を放棄した noshi は誤読したままの C に時間を溶かしまくっていた。しかし流石に無理な雰囲気を感じて I の考察に切り替える。 potato から多項式に言い換えたものを聞いていたのだが、自分でも式変形して確認。綺麗に書けたので想定解は多項式か、多項式で言いかえできるだろうと思う。自分を除く積みたいなのが欲しくなるので多項式補間のような分割統治以外の選択肢が無さそう、と思って考察すれば分割統治を導出できる。 tatyam が D で使った FFT を流用して実装。サンプルが通らずかなり焦燥するが直して通す (4:37)。

J

家を回る順番は多角形に現れる順でいいだろうということはほとんど確信していたので、noshi が I を書いている間に tatyam potato が J の実装を考えていた。 I を通した時点で残り 24 分、行けないこともないか？という気もしたが、家を反時計回りに並び替えたりで時間がかかりコンテスト終了。

その他のこと

腕時計とスマホ禁止なのに会場に壁掛け時計がないのヤバすぎだろ！お手洗いに行って戻ってきたらコンテスト説明始まりそうになってて焦った。
「お菓子はそんなに食べないつもりです」と potato に話していたのだがコンテスト中食べまくっていた。問題が思うように解けないとストレスで暴食してしまう。
途中に配られた弁当に味噌おにぎりがあったので齧ったところ味噌ではなく梅干しだった。梅干しの酸っぱさで目が覚めたが残り半分は廃棄した。すみません。

コンテスト後

　Yes/No で Time Manipulators が J を通して暫定 1 位に浮上したことでかなり動揺した。仮に通っていてもペナ差で勝っているだろうというのは確認していたが、それでも tonosama の I がオープンするときは心拍数と足の震えがすごいことになっていた。

みたいなことをざっくり優勝者コメントで話そうと思っていたのだが特にそういうコーナーは無かった。 1, 2 年前はあった気がするのだが、消えたか？

スポンサーと交流する時間でコンテスタントとも交流をする。ゼッケンの効果があったのか色々な人と山ほど会話をした。

帰宅

本番前はしばらく一人で生活していたのだが、本番後は実家に直帰した。実は私の父親は ICPC の順位表を観戦するのが好きで、今回も息子の勇姿を見守っていたらしい。ありがとう。

noshi91のメモ

データ構造のある風景