第 21 回日本情報オリンピックの春合宿に参加しました。
この記事は問題に関するネタバレを含むのでご注意ください。
誤字脱字はきちんと確認していません。
Day 0
去年と同じホテルに宿泊。春合宿の人数が増えただけでなく、JOIG も同時開催だったので、ホテル勢が 10 人以上いて驚いた。
Library Checker を埋めて心を落ち着かせようと思ったら、二重連結成分分解をバグらせた。与えられるグラフが連結だと思い込むいつものミスだった。
Day 1
ヨルシカの曲を大音量で体に流しこんでから出発。会場に着いたらいつものメンバーがいて懐かしさを覚えた。「今年こそはずっと 4 位以内を維持して代表になるぞ！」と意気込んで競技開始。
全問 Batch だった。去年のように一問目に Output Only が置かれていなくて安心。全問読んで、とりあえず設定が単純で部分点の付け方が雑な kyoto に取り掛かる。とりあえず自明 10 点を取る。小課題 2 の配点が 30 点と大きめなのでまずこれを取ろうと考えるが、一向にわからない。某難易度 12 のように DP の差分を取れば速くできるんじゃないか？などと思ったが、後から考えるとこの方針で進んだのが運の尽き。
解けないので数え上げの misspelling を読む。とりあえず与えられた条件を言い換えるとかなり単純になった。後ろから DP すればとりあえず部分点は取れるので実装した。その次の小課題の意味が全くわからないので、DP のコードをじっと睨んで高速化できないか考える。色々試行錯誤した上で満点が取れた。ひとまず安心。
jail を読む。見た目的に難易度 11 以上だろうと思った（が、結果的にはそうではなかったらしい）。トポロジカルソートのようなことをしたくなったが詰められず、26 点で止まった。
その後 kyoto と jail を反復横跳びしながら考察したが、一点も伸びなかった。悪い予感を抱えて競技終了。
実際ひどい結果で、jail に関しては下から数えた方が早かった。安心できる成績で代表になりたいとか言っていた人が 10 位を取ったらしい。 代表ボーダーとは約 60 点差だったが、去年 100 点差をひっくり返した経験があるのでそこまでメンタルはやられていなかった。
解説を聞いた後に言うのも変だが、jail は解けただろ
Day 2
2020 の Day 2 では 4 点、2021 の Day 2 では 42 点という悲惨な思い出があったので、今年こそは Day 2 でも成功したいと思った。
競技開始後、まずは全問を読む。team が簡単そうなので取り掛かる。とりあえず Θ(N2) を通して、しばらく考えると満点がわかった。一時間もたたずに一完することができ、大喜び。
Communication 課題である flights に取り掛かる。少し考えると 62 点解法がわかったので実装し、少しバグらせた後に取る。その後 copypaste3 の 30 点を取り、二問を反復横跳びしつつ flights を小手先の改善で 67 点まで伸ばした。75 点まではわかっていたつもりだったが、合わせることができず競技が終わった。
総合順位は 5 位と悪くなかったが、copypaste3 を解いている人が 5 人ほどいたことに驚いた。解説を聞いた後は確かに可能枠だと感じたが、競技中は全ての問題が難易度 12 に見えるので普段なら解ける問題も解けない。
copypaste3 と team は JOIG との共通問題で、なんと JOIG に team の満点がいたらしい。強すぎる
Day 3
去年 Day 3 で大成功したので今年も頑張るぞ〜と思いつつ競技開始。
二問目が木クエリ問なので取り掛かる。log のついた犯罪臭のする解法が頭をよぎったが、少し考えると計算量が良く実装も激軽な解法が浮かんだので実装する。前日に引き続き一時間も経たないうちに一完できたので安心する。
次に小課題が多めの device2 に取り掛かる。一時間以上考えても 10 点しかわからず、やばい。とりあえず 10 点を取って sugar を読む。小課題 2 までは取らなきゃいけないやつかな〜と思って考えるが、小課題 1 しかわからない。なんとその 6 点を取った後は一点も伸びなかった。合計三時間半くらい椅子を温めていた気がする。火事になってしまう
終了後順位表を見ると、device の 40 点や 80 点を取っている天才を除けば上位勢とほとんど点数が同じで安心した。しかし、激ムズセットでは点差が縮まらないため順位は 5 位のまま。代表ボーダーと約 40 点で最終日を迎えることとなった。HELP
夜に推しの歌ってみたが投稿されたのでループしながら寝た。
Day 4
あまり緊張せず競技に挑めた。根拠はないがなんとなく行ける気がしていた。追う側は失うものがない
全問読んだ後、dango3 を考えると 2 分で解法がわかったので実装。20 分で満点が取れた。 これは今年の春合宿を通して一番簡単な問題だろう、と思い、実質 200 点分で 40 点差を返さなければならないと考えて少し焦った。
fish2 を考える。考えなければいけない区間が O(N) 個しかないといういつものやつで 25 点までは取れた。
その後 reconstruction を考える。まず Q <= 20000 を通し、次に M <= 1000 を変な解法で通した。これだけで二時間使ってしまった。 しかし、よく考えると小課題を解くときに仮定していたことが実は必要ないとわかり、満点の解法を思いつくことができた。 100 分ほど残して 200 点を取ることができた。
その後は fish2 とタイマン。取得クエリしかない場合はなんとなく解けていたので、残り一時間になっても進まなかったらそれを詰めて実装しようと考えていた。実際残り一時間になっても進んでいなかったので、48 点まで伸ばして終了。
なんと Day4 単体では 1 位。総合 3 位に返り咲き、無事（？）代表になることができた。
結果
Day 1
jail : 26
kyoto : 10
misspelling : 100
Day 2
copypaste3 : 30
Flights : 67
Team : 100
Day 3
device2 : 10
sprinkler : 100
sugar : 6
Day 4
dango3 : 100
fish2 : 48
reconstruction : 100
Σ 697、総合順位 : 3 位
無事 IOI の日本代表になることができました。
感想
良かった点 :
全体を通して実装が簡単な方針を選ぶことができた。
メンタルがバカ強かった。
悪かった点 :
一日目から本調子を出すことができなかった
今年の問題は（易化したとはいえ）多くの参加者に解かれていて、実力のインフレを感じた。多分来年も今年と同じかそれ以上に緊張して挑むことになると思う。
APIO / IOI 頑張ります。
