ICPC2022国内予選・Kite_kuma(チームSPJ)視点 - クマーの競プロ精進日記

無念の11位敗退から1年．今年こそは，である．

チームメンバー

nok0

東大工学部物理工学科3年．アカウント名はノックゼロと読む(嘘)．タイピングがチームで最も速く，主に重実装問題を担当する．最近だとABCやARC140のwriterをやっていたりして，3人の中では一番名前が知られてそう．最近デスクトップPCを購入し，競プロ全力なのかと思いきやよくAp〇xをやっているところをDiscordで目撃されている．3年になってからは大学で物理学の実験を楽しそうにやっている．

zkou

AtCoder: zkou (黄色, max: 橙)

Codeforces: zkou (薄橙)

東大工学部計数工学科3年．アカウント名はズコウと読む(嘘)．チーム内で唯一メイン使用言語がPython．最近はC++で書くのも頑張ってるけどまだ不慣れな様子．もともとあまり実装しない立ち位置だったが，最近の作戦会議の結果全く実装をしないことになった．この人とつちのこが協力して数え上げをやると仕事が本当に速い．学業ド真面目勢．閃き一発の構築問題がかなり得意だがICPCにあまり出ないのが辛いところ．しかし…？

クマー

AtCoder: Kite_kuma (橙)

Codeforces: Kite_kuma (薄赤)

東大工学部計数工学科3年．アカウント名はキテクマと読む(嘘)．筆者．Kita_masa氏とはアカウント名が似ているだけで特に関係はない．3人の中で最もAtCoderのレートが高く，かつコンテストの爆死が最も少ないので一応安定枠っぽい感じの人．構文解析と幾何を担当する．幾何の実装時にぼっちになりがち．日本語を読むのが苦手なので(?)ICPCの難読問題はあまり好きじゃなかったりする．実装速度は普通~ちょっと遅いくらい？学業はゆるふわ勢．

記録

2週間前あたりからずっとICPCのことを考えていて，眠れなかったり授業やレポートに集中できなかったりしていた．特に今週後半は特にひどく，ほとんど全ての授業が上の空だった気がする．

当日．体力温存のために昼まで寝てから家を出た．大学に着いて，3限が上の空になりながらリハーサルを済ませた．今年の鎖中経路チャレンジは20分くらい．これやっぱ実装難易度がほどほどでいい幾何問題だよな．こういうの本番でももっとくれ．ここで昼食をとっていないことに気付く．3限が終わり，事前に借りておいた部屋に移動した後，パンとおにぎりを買いに行って食べた．これが15時すぎくらい．競技開始が16時半だから，腹が満たされて眠くなったりしたり嫌だなとか思ったりもしたが，腹が減ると全く集中できない人間なので仕方なく食べた．

本番前最後の作戦会議をした．自分たちより格上っぽいチームを列挙したら10チーム以上あって普通にげんなりした．~~(へのさんいつまでいるんですか？)~~特に今年の東大は層が厚くて，模擬国内で東大内順位が5位以内のチーム(我々は東大内6位だった)との争いが苛烈になることは必至に見えた．冷静に状況を書き出してみると少し自信が減退して，通過率は3割くらいかなーと思い始めた．具体的なチームの動きを確認した後にちょっと横になったりしながら開始を待った．

16時30分．どうせ今年もサイトが落ちるんだろうな…と思って完全にそのつもりでリロードしたら，なんと普通にトップページが表示されている．逆に面食らってしまった．今年からサーバー強化したとかならそう言ってくれよ(逆ギレ)．予定通りnok0がA，私がB，zkouがCを見る．ババ抜きのシミュレートで，もう見るからにめんどくさい．もう少し易しい日本語で書いてほしいと思った*1．計算量がO(N²)で収まっているのかが少し怪しい愚直が思いついた*2．このあたりでつちのこが慎重にAを通してCでzkouと合流していた．Bの計算量だが，3乗になっていたとしても $N\le 1000$ で定数倍も軽く，国内予選ルールならさっさと回すのが早いと思ったのでその方針で書き始める．Cも2人の会話を聞く限りほとんど出来ていそうだ．私はBの実装を続ける．B問題だし大した実装量ではないが，ペナを生みそうでかなり緊張した．しょうもないミスを挟みながらもなんとか15分くらいで通した．さすがにCは2人で十分と言われてDに行く．日本のICPCで $998244353$ が $\mathrm{mod}$ に使われたことに驚きつつ*3，今年審判団に入ったDEGwerさんのことを思い出す．解法の方はというとすぐには分からなかった．考えているうちに2人が合流して，順位表がCで固まっていることからも，このD問題で早くも3人投入することが良いということになった*4．色々具体例を試して考えてみる． $s,t$ を前から見ていくと，区切りを入れなければいけない場所，区切りを入れては行けない場所が分かる．この情報はどうせ使うのでつちのこにその判定を書いてもらう．ではそれ以外の場所は任意に区切りを入れて構わないのだろうか？zkouと話す間に，それが正しいことが分かった．ここまでくればO(N²)のDPは自明だ．実装も簡単なので，nok0とzkouにEに行ってもらって私はDの実装を始める．制約がN<=10⁴で50ケースくらいあったので20秒くらい待った*5．ヒヤヒヤしながらも一発でAC．このとき開始から1時間弱であった．順位表を見たら一応暫定圏内だった気がする*6．順位表を見るとほとんどが4完以下で，2人はEで苦戦していそうだったので，私も合流することにした．問題を把握して，あまりにもAtCoderっぽい内容だったので笑ってしまった*7．やっぱりICPCの出題傾向かなり変わってないか？そんなことはどうでもよくて，解法に全く見当がつかないので困った．じわじわEとFのACが増えてくるうちに，Fに行った方が良いのでは？ということをnok0が言い始める．Gは幾何らしく，とりあえず簡単かどうか私が確認したほうが良いだろうということになる．10分ほどGを考えて，おおまかな方針は分かったものの，細部について詰められなかったし，実装で沼って結局4完止まりになってしまう未来が容易に想像できたので切り上げてEに戻った．しばらくしてzkouが，文字列AとBの先頭と末尾が全て0の場合は構築可能であることを示していた．しかし他のケースについては分からず，16通り場合分けをするのは困難であるように見えた．私とnok0はこの辺りでEに難色を示しており，Fに行っていた．zkouはEに残って考えていた．私とnok0がFでDPができるかもという話をしていたところ，zkouからEが解けたと言われる．えっ…？このときは40分以上全く進展がない状況だったので，藁にもすがる気持ちで解法を聞いた．確かに全てのケースが尽くされている．少し私が実装方針に注文を付けつつ，得られた解法は以下の通りだった．

$A, B$ の末尾と先頭 $a_1, a_n, b_1, b_m$ に着目する．
- このうち3つ以上が1であれば，構築不可能である．
- $a_1 = b_m \neq a_1 = b_n$ のケースは構築不可能である．
- $a_0 = b_0 = 0$ のケースは左上を $-$ で埋めて，中央で市松模様を作ったりすると構築可能である．
- $a_n = b_m = 0$ のケースは上手く対称性を使用することで上のケースに帰着される．
- それ以外のケース，すなわち $a_1 = a_n \neq b_1=b_m$ のケースは，上と同じように頑張ると構築可能である*8．

理屈は難しくはないが，書く量が多いので添え字の1つでもずれたら修正に時間がかかる．時間がないので急ぎつつも，ペナは絶対に出せないので正確に慎重に書くしかない．この時点で残りは1時間強くらいしかなかった．VSCode Live Shareで3人で共有し，私が上記の場合分けの前半部分を，nok0が後半部分を，zkouが全体のコードの監督をするという3人同時実装を行う．zkouには大量に書き間違いを指摘されたし，理解があやふやな部分を教えてもらったりもしていた．nok0は実装が速くて，一瞬で自分のパートを終わらせていた．私ももたつきながら実装を終わらせて，サンプルを試す．RE．え，そんなことある…？と不思議に思っていたら最初の入力順序を間違えていることに気付く．この土壇場であまりにもしょうもないミスの修正に1~2分使ってしまった…．修正してサンプルを試すと，合わない．nok0の実装した部分が少し間違っていたようだ．nok0が直している間に，私は自分が書いた部分に誤りがないかもう一度確認する．抜けがあることをzkouに指摘されて，少し加筆する．nok0の修正も終わり，サンプルが合うことを目視で確認する．しかしサンプルが弱いため，私の実装した部分をチェックできるケースが入っていない．ペナは絶対に出せないので適当にケースを追加して試してみる．見えている範囲では正しく動いているようだ．緊張で高鳴る胸の鼓動を感じながら入力ファイルをダウンロードし，submitする．AC．興奮で少し叫んだ．nok0とzkouはここで順位表を見ていたが，私の動揺を避けるために私には何位か伝えないでいてくれた．冷静に残りを見ると30分強．ここまでノーペナで通し切ったのは大きいが，すでにDのACから90分が経っており，リードが守れているかかなり怪しい．高い確率でもう1問必要だろうと思った．解法が詰められるか不明だが実装量が並程度かもしれないFと，解法はほぼ分かっているが並列実装がしづらく，実装が重いG，そして全く手を付けていないHからの選択．Gのほうがマシだと私が言って，3人でGに行くことになった．しかし心の中ではこの残り時間で通せたら運が良すぎるとも思っていた*9．Gでやるべきことは単純で，2点の位置のペアを状態として持って適当に探索すればよい．幾何は他の2人が全くやらないので私1人の実装だったが，あまりの焦りから簡単な添え字ミスを2人に大量に指摘された．実装が一応終わって，サンプルを実行したらREになったり，答えが全部0になったりなどを繰り返しているうちに，zkouから冷静に終了を告げられて，コンテストは終わった．

Gが通せなかったことの不甲斐なさと，通過しているか分からないことによる不安でいっぱいになりながら順位表を開けた．

気付いたら叫び声を上げて，nok0と大はしゃぎながら喜びを分かち合っていた．Eの大部分を考えてくれた天才が，普段は声がでかいくせに，俺たちを見て静かに嬉しそうにしているのが印象的だった．5完最速なので，結果的には序盤のリードは守れていたようだ．

片付けたあとは渋谷でThe Raspberry Candiesの方々，DELIAIRのお二人，noimiさん，seguramuの人たちと喋った．ネット上だと分からないチームの結成秘話とか他のチームメイトの珍エピソードとかを聞かせてもらってすごく楽しかった．同じ趣味を通じて得る同志は本当にいいものだなと思う．

終電1本前で帰宅したら寮で先輩が祝ってくれて，そのまま先輩と朝5時半までドミニオンで遊んでから寝た．

というわけで悲願の通過となった．昨年がひどい落ち込み方をしていたのもあって，お祝いの言葉をたくさん頂いた．アジア地区までにもっと強くなって，東大代表争いに食い込めるようにしたい．

*1:今見るとこの内容を簡潔かつ厳密に書くのは無理なので仕方なさそうである

*2:今冷静に見たら普通に2乗だった．冷静じゃなさすぎる

*3:たぶん今回が初めてだと思っているが，直近2年のアジア地区の問題を見ていないのでそこでは登場しているかもしれない

*4:これは今振り返っても好判断だった

*5:あとからDPではなくて普通に二項係数の和を計算するだけで $O(N)$ であると聞き，当時は本当に緊張していたんだなと思ったりした