はじめに
IOI2023 に関わった全ての方々へ感謝を申し上げます。 自分にとって初めての完全オフラインの IOI であり、一生思い出に残る素晴らしい体験ができました。
また、Twitter (現 X) などを通して日本選手団へのたくさんの応援コメントを拝見しました。 皆様の応援が力になり、よい結果を出すことができました。ありがとうございます。
以下の内容は IOI2023 の問題に関するネタバレを含みますのでご了承ください。
8/27
羽田空港での壮行会 & 出発。SET で遊んだり、競技規則を確認したりした。飛行機が 11 時間 + 2 時間とかなり長く、きつかった。
8/28
ハンガリーに到着。飛行機で眠れず、7 時間の時差があったのでずっと眠かった。 去年のインドネシア大会ではホテルの食事が美味しいとは言えず衛生的にも心配だったが、今年のホテルの食事はかなり美味しかった。 今年はインスタント食品ばかり食べなくともなんとかなりそうだと思い安心した。
8/29
プラクティス & 開会式。前日に 4 問目の解法を他の選手と話し合っていたので、1,2 問目をさっと解いた後に実装してみたが、1 時間かけてもバグが取れなかった。 後になってプラクティスの順位表が公開されていると知り、2 時間で全完している選手が複数人いることに驚いた。
プラクティス 4 問目は次のような問題。
- 頂点に非負整数の重み S_1, ..., S_N が、辺に非負整数の重み W_1, ..., W_{N-1} がついた木が与えられる。
- 整数 i をちょうど S_i 回含み、先頭と末尾が 1 である整数列 P_1, ..., P_K に対し、P のスコアを i = 1, ..., K-1 に対する頂点 P_i, P_{i+1} の距離の総和と定義する。
- 「S_i を x に変更する」というクエリが Q 回与えられるので、各クエリに対し、それを処理した直後の P のスコアとしてありうる最大値を求めよ。
実装激重 Nlog2 N しか生えなかった。
帰り道に、木の頂点に重みがついていて重みの一点更新がある場合の重心の求め方を韓国選手に教えてもらった。オイラーツアー順に重みを並べたときに累積和が総和の半分を初めて超える位置を求めて、その頂点の祖先を見ればよいらしい。言われてみればという感じだが自分は見たことがなかった。
8/30
競技 1 日目。
A を早速誤読し嘘貪欲に 20 分使ってしまった。勘違いに気づき正しそうな 83 点解法を実装するも全く点が得られない。
ヤバいと思いつつ C に移るがこちらも嘘解法しか生えず、105 分経過時点でほぼ 0 点だった。未実装のものも含めて全く正しい解法が思い浮かんでいないので流石に焦った。
しかし B を見ると 15 分程度で 70 点の解法が見えた。少しバグらせたが 140 分経過時点で 70 点を取ることができ安心した。
その後 C に戻り、落ち着いて判定条件を考えるとようやく正しい多項式時間の解法を思いついた。190 分経過時点で 70 点まで伸ばした。
やっと A に集中できる状態になったので最初の 1 時間に書いたコードを見直すと、なんと簡単な場合分けを忘れていることに気づき、一瞬で 83 点まで伸びた。
残り 90 分、何か一つでも満点を取りたい状況。保険として C の 77.5 点を整理しておいてから、満点まで小課題が 2 つ残っている B を考える。償却でクエリが 2N 回になっていそうな解法を思いついたが、筋が悪く場合分けが多くなってしまい、1 時間かけても点数を伸ばせなかった。残り 30 分は C の 77.5 点を通すのと、A の満点を考えるのに使った。
悪くない順位だったが、1 問も満点が取れなかったことや、A の 83 点を木 DP ではなく満点のもとになる解法で取っていたにも拘らず満点がとれなかったことが悔しかった。
夜はメキシコの選手とビリヤードをした。一人かなり上手い人がいて凄かった。
8/31
エクスカーション 1 日目。
ハンガリーののどかな風景を楽しめた一日だった。しかし日本選手の 1 人が風邪で休むことになったので少し心配だった。
この日が卒業文集に載せる文章の期限だったので、日本時間の 23:59 ギリギリ (ハンガリーの 16:59) に完成させて提出した。
ふと思い出して IOI2018 のテーマソングである Euphoria を聴いていた。IA が実行委員をやってテーマソングをじんさんが手がけているのはかなり凄いことだと思う。曲はもちろん、歌詞もすごく好き。ボカロでは IA が一番好きなので、いつかの JOI 本選でもらった IA のクリアファイルは使わず家に置いてある。
IA / Euphoria (じん) (PARTY A GO-GO WORLD TOUR FINAL) 【LIVE MUSIC VIDEO】 - YouTube
9/1
競技 2 日目。
今までで一番緊張した。JOI 本選/春 のようにいい成績を取らないと次へ進めないということはないが、自分は 2 度 IOI で金メダルを獲っている。 誰かに「今年も金メダル期待しているよ」と明確に言われたわけでもないし、どんな結果でも周りの人は讃えてくれるのだろうが、やはりプレッシャーは重い。
最後の競技が始まった。A を読むとかなり部分点が多く、少なくとも M=2 や N<=200 は取らなければならない見た目をしている。 しかし開始 80 分後までに思いついた貪欲が全て嘘解法だった。N <= 10 の愚直解を書いてランダムケースで答えを比較するも全く反例が見つからない。 絶望して B に移る。愚直の 39 点を取り、しばらく満点を考えるが、A は多項式にすら落ちておらず、考察・実装ともに時間のかかりそうな C は手付かずという状況や、このままでは銀メダルになってしまうという焦りでパニックになってしまった。結局 65 点で妥協して、なぜか手付かずの C ではなく A に戻ってしまった。
残念ながら嘘解法が直ることはなく、結局小さい自明部分点を回収して 9 点→ 23 点にするだけで 1 時間使ってしまった。この時点で 23-65-0 で 100 点にすら届いておらず、問題文がかなり長く特殊な見た目をしている C が未だ手付かずという状況だったので、本気で絶望してしまった。応援してくれた人や惜しくも IOI に来れなかった人たちに脳内で謝ったり、呆然としてマスコットを眺めていたりした。 先に B の満点を考えるか C に手をつけるか迷ったが、満点に突撃するのは流石にリスクが大きいと考えようやく C に手をつけた。DFS を上手くやる方法を思いついたので実装して 34 点を取ってから、54 点がすぐに見えたつもりになって実装するも一向に通らない。ランダムケースを 1000 ケース試しても落ちず困惑し、残り 15 分程度になってハッとして A の残っている自明部分点に取り掛かった。結局 31-65-34 で、銀メダルに落ちたと確信して文字通り頭を抱えた。
なお C で 54 点が通らなかったのは、答えは常に合うが特殊なケースで操作回数が指数オーダーになるからだった。ランダムケースで落ちなかったことで気づくべきだった。
自分の弱さが出た日だった。これまで何度も 5 時間コンテストをやってきたし、春合宿や IOI2021 で大逆転も経験しメンタルは強くなったと思っていたのに、最後の最後にプレッシャーに負けて普段通りの考察力が発揮できず戦略ミスもしてしまった。今までの経験が自分の精神力に対する過信を生み、かえって足枷となってしまったような気がする。 本来ならまず B に取り掛かるべきで (この日だけなぜか最初に全ての問題文に目を通すということをしなかった)、C を手付かずで放っておくべきではない。後になって考えると当たり前のことができていなかった。 これからは (当分の間大きな大会はないが) この経験を忘れず自分の弱さに向き合っていかなければならないと思った。
しかし幸運なことに、なんと 21 位で金メダル圏内で耐えていた。絶対に銀メダルだと思っていたのでかなり安心した。さらに日本選手全員が金メダル圏内にいて 2 人が一桁順位を取っていた。2 年連続で全員金メダルなので、JOI 春合宿のレベルは相当高いのではないかと思う。
9/2
エクスカーション 2 日目。
午前はセゲド動物園へ行った。ミーアキャットが可愛かった。
午後は公園のようなところへ行って海外の選手たちと一緒にバレーボールをした。全くサーブが入らなかったし手首が内出血を起こしたが、体を動かすことができて楽しかった。
夜は懇親会やディスコみたいなイベントがあったが、体力的にきつかったので夕食だけ食べて早めに帰った。一緒に帰った日本選手に触らせてもらったゲームがかなり面白かった。
9/3
閉会式。
ニュージーランドの10歳の子が銅メダルを受け取ったときの歓声が一番大きかった。10歳でメダル獲るって相当凄いし、なんとあと7回もチャンスがあるらしい。
IOI2024 の予告映像も流れた。来年はエジプトのアレクサンドリアで開催されるらしい。2025 はボリビア、2026 はウズベキスタンという噂も耳にした。 ハンガリーは予想以上に環境が良かったので来年以降どうなるかな。
9/4
日本へ向けて出発。ブダペストを観光…するはずだったが、日本選手の一人がリュックを紛失するという事態に。 結局見つからず、予備のメダルを受け取ったらしい。
ブダペストは綺麗な街だった。ドナウ川は思っていたより汚かったけど…
そして、この日に 18 歳になった。誕生日に金メダルもらいたいね、という話を事前に家族としていたので、実現できてよかった。 中高を競プロとともに過ごして、競プロを通して大人になったような感覚がある。
9/5
日本到着。日本の米と肉を求めてたどり着いた先はなんと焼肉屋だった。久しぶりの日本食だったので白米だけで既に美味しかった。
さいごに
IOI2023 で金メダルを獲得しました。IOI2021, IOI2022 に引き続き 3 度目の金メダルとなり、安堵と達成感でいっぱいです。
競技の内容や 21 位という順位に関しては悔しさが残る部分もありますが、ここで競技プログラミングを辞めるのは嫌だと思える結果でもありました。 この悔しさは、今後も競技プログラミングに取り組むためのモチベーションに変えていこうと思います。今回見つかった自分の弱さをしっかりと見つめ、より強い選手を目指して今後も努力します。
情報オリンピックは僕にとっての青春で、そこには様々な感情と思い出があります。情報オリンピックがなければ今の自分はないだろうし、全てが今後の人生を形作っていく経験だと思います。 情報オリンピックへの最大の感謝をもって、筆をおくことにします。
