ICPC 2023/24 国内予選参加記(shobon 視点)

はじめに

ICPC 2023/2024 国内予選は noya2, shobon, ebi の 3 人で AMATSUKAZE というチームで参加しました。国内予選の結果は 6 問解いて 10 位、そしてアジア大会への出場権を得ました！

ebi 視点はこちら

noya2 視点はこちら

当日まで

チーム結成は結構古く今年の 4 月中旬くらいです。それから毎週火曜・金曜に国内予選・模擬国内のセットを計 21 回走りました。

東工大から highest 黄色以上からなる強いチームがたくさん出るので、host 校ボーナスで +1 チーム国内予選を突破できるとはいえ、良い順位でも国内予選が通らない場合があるなと感じていました。実際に、模擬国内では 10 位以内に東工大が 4 チーム入っていて怖さを感じました。

また、3 人で ICPC のためのライブラリを用意して当日までに印刷しました。自分はネタがなくてライブラリにフロー系と掃き出し法しか入れていませんでした。

さらに、予選突破後に US キーボードを使うということで、チームで US キーボードに統一することになりました。ebi さんとぼくは新たに US キーボードを買いました。コンテストでは ebi さんのキーボードを使っています（打ち心地がよすぎる！）

自分は AtCoder ではもともと Python/C++ の二刀流でしたが、US キーボードにしてからしばらく C++ でしか書けなくなりました。しかし現在では US キーボードでも Python に慣れて再び二刀流に戻りました。

当日（コンテスト前）

チームメンバーと「早寝するのがよい」などと喋っていたのですが、前日に競プロの感覚を思い出すために Codeforces の Div.2 を走り、結局 4 時に就寝することになりました。

睡眠不足は一番よくないと思って当日は 12 時に起きることにしました。12 時 20 分に起きた後、まいばすけっとでご飯を買って大学の教室で食べました。その後、会場の演習室に行き、リハーサルを進めながら他の ICPC 参加者と喋っていました。

リハーサルで分かったことですが、結構よくないミスなのが、答えを提出する際に Answer File があっているのに Program File の指定を間違えてしまった場合で、この場合テストケースを 2 個追加で消費してしまいます。（ただしペナは付きません）

D, E, F は予選通過の鍵になりますが、3人それぞれ構文解析、幾何、フローが得意なので「全部出ればいいな」と喋っていました。

当日（コンテスト中）

A, B

問題の印刷が届くまで時間がかかるので、作戦通り ebi さんが画面左側でテンプレートを書いている間に画面右側の A 問題を見ます。(0:02)

A 問題は自明だったので、noya2 さんに B 問題を見せます。自分も B を見ますが、問題文が長くて「これが B か…」と思いながら、計算量が重くても制約はやさしいから全探索が行けるな、と思います。noya2 さんも全探索の方針でいくらしいです。C の問題文を ebi さんと見ます。

テンプレートが書き終わったあと PC を交代して A を書きます。高速にコーディングしながらも、A 問題で万が一にでもペナルティを出さないように慎重にいき、通りました。(0:06)

B 問題の実装をする noya2 さんにパソコンを交代しつつ、C 問題はこんなものは偶奇性だと思って、左上、右下、左下、右下に分けて縦の座標, 横の座標の偶奇によってどのブロックに所属するかを決めると、これは妥当そうです。ebi さんにも「よさそう」と言われました。

D 問題を ebi さんと一緒に考察し、ebi さんが「1, 2, 4, 8, 16, 32, 64 ですべてカバーできる、これがかなり良い感じがある」と主張してなるほどと思いました。C 問題の実装が近いので詰め直します。

C, D

B 問題が通り (0:17)、実際に C 問題のコードを書いてみると、逆順列を考えるなどをする必要があり、想像以上に混乱して焦ります。（思えば逆順列すらいりませんでした）

バグりながらも、ブロックの所属先を決める箇所は合っているので、あとは行列 a を答えの行列に変換するだけです。ここで全然合わなくて結構焦ります（実際は合っていたらしい？）

この時点で ICPC の優勝候補である Speed Star というチームが C で WA を出しまくっているのを確認しています。 D はまだ考えてるらしいので、ebi さんと協力して C の実装を詰めると、思った通りに動くようになりました。他のチームはぽつぽつ C を AC し始めました。(0:35～0:50)

本当に条件を満たしているかどうか assert が欲しいと言われ assert を書き始めますが、これがどうにも上手く詰められません。書き進めようにも全ての変数のつながりが切れたように感じて進行不能になってしまいました。

ここまでで ebi さんに何度も落ち着けと言われますが、shobon の頭はすでに破壊されています。コード自体は思ったことができているので assert を書く時間より解答を出す方がよいのではと思い、解答を出しましたが WA が出てきました。終わりです。(0:40～0:55)

よく見ると、 $n$ が奇数の場合は OK ですが $n$ が偶数の場合でダメなことが確認できます。これを回避するために $n$ が偶数の場合の解法を探します。その間に ebi さんに assert を書いてもらいます。

ebi さんが assert を書いている間、noya2 さんが D 問題の解法を見つけたみたいなので、 C 問題のコードを印刷して D 問題を任せます。

$n$ が偶数の場合のかなり妥当な解法が生まれました。行列の上半分と下半分に分けて、(縦+横) の偶奇で別々にグループに振り分けます。横方向は確実に OK で、上半分と下半分の境界も OK です。そう言っているうちに、noya2 さんが D 問題を通します (1:10)

天才 noya2 さんありがとう…と思いながらぼくが C のコードを書いてみると、assert で落ちます。実際に解法がまたバグっていて、横方向が OK ですが境界以外の縦方向がダメでした。assert を書いていなかったら 2WA しているところなので助かりました。

解法を少し考え直すと Cの解法_最新決定版ver2確認済ができたので書くと assert が通ります。そのまま C を提出すると通って、とりあえずは安心しながらとても申し訳ないと思いました。(1:22)

E, F

この時点で 4 完しており、順位もそれなりです。E より先は強いチームでも少ししか通ってなかったのでかなり難しそうということが分かりました。

F 問題は幾何なので得意な noya2 さんに任せるとして、E 問題が後半の中でかなり通されているので見ます。問題を読んだあと、自分は誤読率が高いので念のため ebi さんに問題の概要をチェックするとやっぱり誤読していました。誤読のプロ

G 問題を見た方がよいと ebi さんに言われるので読んでみると、問題文がよくわかりません。 ebi さんから問題について聞かれて、ebi さんが誤読していることが分かりました。問題を理解したあと、いろいろ考察するも全然分からないので E に戻ります。

E 問題は制約が $O (N^{2})$ で解けと主張していますが、よく分かりません。そのあと ebi さんから E の $O (N^{3})$ 解法が説明されます。

d p [i] [y] [x] = i 番目まで決めたとき, その値が (x, y) となるときの操作回数の最小値

で、確実によいです。ぼくは $y$ に対して $x$ のとりうる値が高々 $x_{i}$ と $n - 1$ の高々2通りなのでは？と主張し、そのわけを ebi さんに説明します。そうすると map を利用して $O (N^{2} lo g N)$ です。

解法が結構いい感じでパソコンも誰も使ってなかったので、ぼくが E の実装に取り掛かります。しかし遷移をまだ詰めていなかったため、遷移で悩んでいました。このときに noya2 さんが F 問題の確実性の高い解法を思いついたらしく ebi さんと会議をしていました。

E 問題の遷移が詰めきれていないということで、F 問題を通すことにしました。ライブラリ寿司打担当であるぼくは凸包を写しました。バグなく書けてよかったです。その後はパソコンを noya2 さんと代わり、F 問題の実装を任せます。(1:40ごろ？)

E 問題の考察に戻ると、 $y$ に対して $x$ のとりうる値が高々 $2$ 個は嘘で、 $3$ 個以上にもなることが分かりました。これで E が白紙に戻りました。

その後、ebi さんから「遷移は『何もしない、 $x$ を変える、 $x$ と $y$ を変える、 $y$ を変える』の4つがある」ということを伝えられます。

これは当たり前ながら結構いい見方で、ぼくはそれぞれの遷移の先として最適なものが決められる（具体的には条件を満たしつつ辞書順最大なものにする）と主張します。場合分けがやや複雑ですが、ここは確実に整理できると思いました。

しばらくして、ぼくは DP を $d p [i] [(x, y)]$ として見ると、 $d p [i]$ の取りうる状態数が高々 $O (N)$ オーダーなのではないかと主張しました。その理由として、 $(x, y)$ の状態には $i$ 以前の $(x_{j}, y_{j})$ が少なからず関わりますが、それが高々 $O (N)$ 個しかないからです。

DP の遷移を少し詰めたあと、F 問題がバグったらしいので、印刷してもらい E 問題を改めて書くことにしました。半分くらい書き終わると、演習室に戻ってきた noya2 さんが「貸せ貸せ貸せ」と言いながらパソコンを奪います。F のバグの原因が分かったらしいです。すぐにサンプルが合い、提出すると通りました（天才！）(2:25)

E 問題に戻り、DP が完成するもサンプルが合いません。DP がバグっているので印刷して 3 人でデバッグします。しばらく試行錯誤して正しい遷移が完成し、サンプルが合ったのでテストケースを試しますが、 $n = 500$ の時点でかなりの時間がかかります。というのも実は「 $d p [i]$ の取りうる状態数が高々 $O (N)$ オーダー」は嘘だったようです。悲しい(2:42ごろ)

パソコンの席に座っていた ebi さん（天才）が DP の値ごとに辞書順最大を取ればいいのでは？と主張し、ぼくがそのとき考えていたことと偶然一致します。ebi さんが書くと言うので任せて見ていると、とても簡潔な実装ですごかったです。DP遷移自体は一緒なので、元のコードとの差分は少しだけでした。(2:48ごろ)

実行してみると、 $n = 500$ はすぐに終わり、最大ケースでも高々 15 秒くらいで終わります。最大ケースも高々 10～15 個なので合計 3 分くらいで実行が完了し、提出すると Correct Answer が出たので盛り上がります。(2:51ごろ)

2個目のテストケースを祈りながら実行していると、再び 3 分後に終わり提出すると AC でした！(2:54)

その後は時間がないので撤退し、雑談をしました。順位表を見てみると、AMATSUKAZE は 10 位です。前々から「10 位以内に入って無条件で予選通過する」ことを目標としていたので、その後 6 分間は「誰も通すな」と祈っていました。時計が 19:30 を指してコンテストが終了し、順位表は 10 位のままでした！

当日(コンテスト後)

コンテスト後は演習室内にいた ICPC 参加者と解法を共有したり喋ったりしました。noya2 さんが noshi さんにサインを貰いにいってました。

夜ご飯は 10 人でカレー屋に行きナンを食べました。おいしかったです。

反省

バチャをいっぱい重ねましたが、本番の緊張は本番にしか再現できません。本番では頭を回転し続けることが重要ですが、同時に冷静になることも必要です。冷静になる方法は分かりませんでした！いかがでしたか？

それでも構築の問題は条件を満たすかどうかの assert を書くべきです。頭が真っ白で何も書けないときはチームメンバーに書いてもらうことも手でした。人間が三並列いるということがチーム戦では重要ですね。

感想

ICPC のスタッフのみなさん・東工大のみなさんにはとても感謝です。

国内予選は 2022 に突破できなくて、今年初めて突破しました。とても嬉しいです。

今回はチームメンバーにたくさん助けてもらう形でしたが、これからは実装力、考察力と知識をより多くつけていつでも安定した強さを持ちたいと思いました。

国内予選のあとは何があるか分かりませんでしたが、11 月にアジア予選があるらしいです。楽しみです！