１．はじめに
第35回国際情報オリンピック（IOI2023）ハンガリー大会に参加してきました。この大会は僕にとって2回目の IOI で、競技者として参加するのは最後となります。
去年の参加記では観光や国際交流など、主に競技以外のことについて書いたので、今年は競技に関することを中心に書こうと思います。IOI の雰囲気について知りたい方は他の方々の参加記をお読みください。
２．競技に向けてどんな対策をしたか
IOI で高得点を取るために重要なのは「考察力・実装力・戦略」の3つだと僕は考えています。
最初の2つに関しては大会の直前数週間でどうこうできるものではなく、今までの競プロへの取り組みの積み重ねという側面が大きいと思います。ただ、最近日本の選手たちのレベルが急激に上がってきているため、日本の代表選考を突破した選手なら少なくとも IOI で金メダルを獲るのに十分な考察力・実装力は持っていると言えるはずです。僕はこの2つの対策としては、今年は特に新しい問題を解いたりすることはなく（去年の段階で IOI の過去問をほとんど解いていたので）、直前の飛行機などで忘れがちな考察テクの復習をしたり必要最低限のライブラリ（BIT・セグ木・CHT・SCC など）の確認をしたりしただけでした。
考察力・実装力と同程度に重要なのが「戦略」です。何を目的とするかによって様々な戦略が考えられますが、僕は既に一度金メダルを獲得しているので、多少メダルの色が落ちるリスクも背負いつつ、今年の目的を「優勝する確率の最大化」としました。今年は特に中国の選手が強く（Codeforces の世界ランクが当時 tourist に次ぐ2位の選手もいました）、その選手たちに勝つことは簡単なことではありませんが、自分のCFのレートが3070（全参加者の中で4番目）だったことや過去問を解いたときの感触からして、問題セットの特徴次第では（例えば僕が得意な Communication 課題の段階的配点で差が付けることができ、かつ、中国の選手がぎりぎり解けるような高難易度 Batch 問題がない、IOI2020 のようなセットだった場合）優勝できる可能性もあるのではないかと考え、これを目的として戦略を立てました。
まず過去数年の得点分布を見ると、優勝するには590点程度必要であることが分かりました。つまり、優勝する確率の最大化において80点以下の小課題は無駄ということになります。
そこで、僕はまず次のようなルールを作りました。「90点以上が得られる目途が立つまでその問題の実装をしない」。例えば $O(N\log N)$ の満点解法が分かった後で正当性の確認として $O(N^2)$ のコードを書いて提出することは可だが、満点解法がわからないのに $O(N^2)$ を実装することは禁止する、というルールです。満点解法につながりそうにない小課題に関しては考察すらしません。
次に、僕の今までの春合宿の経験から最後に解く問題の考察の質が極端に低いことが分かっていて、これは先に解いた問題の実装やデバッグで集中力を持っていかれることが原因だと考えたので、次のようなルールを作りました。「すべての問題の考察が終わるまでキーボードを触らない」このルールを設けることによるメリットは他にもあって、各問題について考察と実装の間に時間が空くので頭が一旦リフレッシュされて実装前に嘘解法に気づきやすくなる、ということです。コンテストの時間を無駄に消費する最大の原因が嘘解法の実装なので、このメリットは大きいです。もちろん実装前に解法を忘れてはいけないので、ちゃんと紙に細かい実装方針を書いておきます。
ここまで僕がとった戦略の紹介をしてきましたが、一つ注意しておきたいのが、最適な戦略は人それぞれだということです。この戦略は端的に言ってギャンブルです。解けない問題が1問でもあると破滅します。IOI では非本質で独立な自明小課題を集めると50点を超えるが満点をとる難易度は非常に高いという馬鹿げた問題も少なくなく、このような問題で0点を取ってしまうのは非常に痛いです。IOI は難易度11弱の小課題を全て集めれば金メダルを獲れるように出来ている（要出典）ので、金メダルを獲る確率の最大化を目指すならこのようなギャンブリングな戦略を決して真似てはいけません。ただし、もし難易度12弱程度の問題を解ける自信があり中国の選手たちに一矢報いたいと思っているのなら、この戦略も一考に値するかもしれません。
僕は中国の代表研修で用いられた5時間セットのうち2つでこの戦略を用いたところどちらも全完できた上、IOI の直近2年の過去問はどちらも580点程度とれたので本番もこの戦略を用いることにしました。
以降、今年の IOI の問題のネタバレを含みます。
３．競技1日目
競技は朝10時に始まりました。封筒を開け、1問目を読みます。面白そうな見た目をしていますが、最適化典型テク「解の候補の削減」を用いて真面目に考察をするとギャグなので解けます。ここまでで30分弱です。実装も軽そうなのでとりあえず実装時間を20分と見積もって次の問題に移ります。
2問目を読みます。ハミルトンパスのようなものを求める必要があり不可能に見えるので、グラフの性質が実はきれいなのだろうと推測します。その方針で考えるとクエリ回数 $N\log N$ の70点解法が分かります。これは明らかに無駄なパートがあり、ここを削減して $2N$ 程度にすれば85点、$1.5N$ 程度にすれば100点が得られるのですが考えが上手くまとまらないので一旦飛ばします。ここまでで1時間半程度です。
3問目を読みます。グリッドにおいて極大の長方形の個数は $O(HW)$ であると聞いた記憶があったのですが証明方法を思い出せません。とりあえず状態量 $O(N^2)$、各状態量について遷移 $O(N)$ のDPが思いつきます。$N\leq 500$ で70点、$N\leq 2000$ で100点が得られるのですがグリッドにおけるよく分からないDPは $O(N^3)$ のつもりで書いたら実は $O(N^2)$ だったみたいなことがよくあるので、今回もそれを疑います。証明はできませんが反例も思いつかないのでとりあえずそれを書くことにしますが、書く前に2問目の考察に戻ります。ここまでで2時間強です。
2問目をちゃんと考察するとクエリ回数を $2N$ 回に削減できることが分かりました。こちらも最悪ケースが思いつかず、ジャッジが adaptive でないため実は満点が得られるのではないかと疑います。ここまでで2時間半です。
次に実装する順番ですが、とりあえず一番重そうな3問目から実装していくことにします。メモを見てその通りに実装していくと30分程度で実装できましたが、サンプルを試すとよく分からない答えが返ってくるので一旦飛ばして1問目の実装をします。こちらは15分程度で実装が終わり、投げると一発ACが返ってきます(3:15:19)。次に2問目の実装をします。投げるとなぜか15点が返ってきます(3:37:17)。とりあえずランダムケースを生成して確認するとバグの場所が分かったのでもう一度投げると85点が返ってきます(3:57:25)。小手先の改善をしても満点が得られないので一旦飛ばして3問目のバグを探します。「バグが見つかります→修正します」を繰り返すとサンプルが合うので投げると70点が返ってきます(4:10:19)。この時点での得点は100+85+70=255点です。
2問目と3問目の考察を交互に繰り返していると2問目の解法が分かりました。1つの頂点を追加するとき、成功すれば1回、失敗すれば2回のクエリが必要なのですが乱数を用いると成功する確率が50%なのでクエリ回数の期待値は $1.5N$ で、ジャッジが adaptive でないことと辻褄が合い、安心して実装します。無事100点が返ってきます(4:41:04)。残り20分弱なので、もし3問目の満点解法が思いついたとしても実装が間に合わないだろうと考え、非本質な部分点7.5点を回収します(4:55:28)。最後の4分半はやることがないので China が全完していないよう祈っていました。
４．競技1日目終了後
Chinaは3人が全完していて、自分は277.5点で単独4位でした。明日全完したところで22.5点を巻き返せるかどうか微妙なラインなので厳しい気持ちになりました。開始3時間15分後まで何も提出しなかったため、団長や順位表観戦していた人たちに体調不良や機材トラブルの心配をされていたようで申し訳ないです。
帰りのバスで解けなかった3問目の考察をしていると、コンテスト中に書いたコードでは $O(N^3)$ かかってしまうが小手先の改善で $O(N^2)$ に落ちるようなテストケースが思いつきました。TLE したときの鉄則「最悪計算量になるようなテストケースを考える」をコンテスト中にしなかった自分が情けなくなりました。何より、残り20分では実装できないと決めつけて満点を諦めたことが情けなくなりました。例え1％でも望みがあるならそれに賭けるべきでした。僕の4年間のOIへの取り組みの集大成とも言えるこの大会で途中で勝負を投げ出すとは何事でしょうか。「絶対に全完する」という強い意志が僕には足りていなかったのだと思います。
翌日エクスカーションから帰ってくると oj.uz のジャッジが立っていたので実装すると100点が返ってきました。ゼロから実装しても20分しかかからなかったので、もしコンテストで諦めていなければ全完できた可能性も多少はありました。明日は絶対に最後の1秒まで諦めないと心に決め（フラグ）、次の競技に臨みました。
５．競技2日目
2022-Day1,Day2,そして2023-Day1全てにおいて、1問目が簡単枠で3問目が勝負枠というセットが続いているので、今日もそうなるのではないかと考え、この日は3問目を最初に読むことにしました。やはりこの問題はかなり難しく、1時間半が経過したところで満点解法が分かりました。
どうせ1問目は簡単枠だろうと思いながら（全ての敗因）、問題文を読むと設定がかなり複雑で、まともに解いていては絶対に解けないような見た目をしています。去年のDay2-Aを思い出し、こういう問題はどうせギャグなのでその方針で考えるとそれっぽい解法が浮かびます。証明はできませんが反例も思いつかないのでとりあえずそれを現状の解法として2問目に移ります。この時点で2時間強です。
2問目は真面目に考えると20分ぐらいで解法が思いつきました。残り2時間半で3問実装すればいいだけなので勝ちを確信します。
とりあえず一番自信のない1問目を実装します。サンプルが落ちます。なんと嘘解法でした。落ちたサンプルを考えると、時間稼ぎのようなものを見落としていることに気づきます。どう考えてもやばいのでやばいです。よく見たら小課題が10個ぐらいに分かれているのですがなんと自明小課題が1つもありません。何かがおかしいと気づくべきでした。ここで一から考察する余裕は残っていないので他の2問を先に実装することにします。
3問目を実装しようと思いますが、実装する前に嘘が発覚します。この時点で3時間半が経過していました。この3時間半での僕の実質的な進捗は2問目の満点解法と3問目のちょっとした考察だけです。本当にやばいです。とりあえず100点だけでも確保して精神を安定させようと2問目を実装し投げます(3:44:25)。0点が返ってきます。もうまともな思考回路は働いておらず、Day1終了時点で4位だった人がDay2で0点をとって銀か銅に落ちたら歴史に残りそうだなとか考えてました。提出したコードを読むと、焦りからか普段はしないようなミスをしていたことに気づきます。一旦落ち着いて書き直して提出すると無事100点が返ってきます(3:53:11)。
1問目を考え直しますが、やっぱりよく分からないので3問目に全力を注ぐことにします。使う色の数を6色以下に抑えれば満点が得られるのですが、少し妥協して9色使って90点ぐらい取る解法を思いつきます。提出すると5点が返ってきます(4:29:19)。これまた嘘解法であることに気づきます。最後の掃除をサボっても各小課題の半分の得点が得られるそうなので、さらに妥協して9色使って掃除をサボる解法を提出します。53点が返ってきます(4:55:05)。
悲しいことに、このままでは最初の方の独立した非本質小課題をすべて回収した人と得点が同じです。残り5分弱ですが、僕にはまだ二つの選択肢がありました。1問目の5点ぐらいの小課題を回収するか3問目で掃除をサボらない解法を考えて90点ぐらいにまで伸ばすか。昨日の反省点を活かし、後者を選択しました。妥協して13色使えば掃除ができるような気がしました。
残り3分強なので、立ち止まって解法の正当性を確認する暇すらありません。僕はこの1％の望みに賭けて、OI 人生正真正銘最後の3分間、全力でコードを書きました。書き終わったときには競技時間は残り5秒強です。コンパイルする暇もありません。Chrome のタブを連打し「ファイルの選択」ボタンを連打し提出するファイルを連打し「提出」ボタンを連打しました。
一瞬画面が真っ白になり、普段と CMS の反応が違ったため提出が間に合わなかったのかと思いましたが、数秒経った後画面が更新され、僕の提出が競技終了1秒前に受理されたことが分かりました。そもそも正当性を確認していない上、色の数値を全部ハードコーディングで書き込んでいたため一つでもずれていたら正しい解が出ないので、正直この提出にはほとんど期待していませんでした。ジャッジの結果が出る前に退出許可のアナウンスが流れたので席を離れて他の日本代表たちと話します。みんな100点台で僕と同じように頭を抱えてました。
５．競技2日目終了後
競技会場を出て団長たちに会いました。
めんだこさん「1秒前提出、やりましたね！！」
「？？？」
予想と違って団長たちは全然お通夜ムードではなく、逆に若干テンションが高いように感じられました。全く状況が理解できないので、とりあえず順位表を見せてもらうと、なぜか自分の点数は 0+100+80 になっていて、全体順位は4位でした。どうやら最後の提出が通ったようです。予想の遥か上を行ってました。去年の IOI で30点解法を投げたら90点が返ってきた時以上に驚きました。
競技終了5分前の提出で12位→5位に上がり、1秒前に5位→4位に上がったらしく、宇宙情報オリンピック地球代表に滑り込みました。自分以外の日本代表も全員金メダルで嬉しい限りです。次の日色んな国の選手たちに3時間半潜伏した理由や終了1秒前提出の背景について聞かれました。「メダルの色なんて気にしない、ただただ順位表を荒らしにきただけの IOI エンジョイ勢」だと思われていたそうです（半分合ってますが）。競技で変なムーブをしておくと話題のネタが増えて楽しいです。CF のブログも作られてました。
６．雑多な思い出
- 2ヶ月前に参加した IPhO で韓国の選手が世界地図の書かれた下敷きを持ってきて各国の選手たちに自国の位置にサインしてもらっていたので、今回は僕もそれを真似して羽田空港で世界地図のクリアファイルを買って持っていきました。41カ国103人のサインを集めることができました。世界制覇ができなかったのは残念ですが、外国選手と話す最初のきっかけになったので良かったです。
- エクスカーションで rainboy に会ったので今年も声を掛けてみたところ、僕のことを覚えてくれてました。"What's your current CF rating?" と聞くとニッコニコの笑顔で "expert!（青色）"と返されました。ちなみに彼は一昨年の IOI で世界5位をとっています。
-
いたずらで色んな人のリュックにこっそりコアラの小さなぬいぐるみをつけて回っているオーストラリアの選手がいました。日本チームで被害(?)に遭ったのは双子とめんだこさんとぺんぎんでした。僕も欲しかったです。
-
エクスカーションの自由時間に中国の選手とトランプをして遊びました。中国の選手たちは皆競プロが異次元に強く、IOI に命を賭けていると聞いていたので話しかけるのが少し怖かったですが、実際話してみると皆面白くて優しかったです。4人のうち3人が day1 で全完していたので、残りの時間何をしていたのか聞くと、暇だったから Python document を読んでいたと言ってました。これが格の違い…
-
JOI の春合宿の問題はやはり世界的に見ても良問の宝庫だそうで、多くの上位層の選手たちが JOI の問題を練習に使っていたと言っていました。ある韓国の選手は Flights（JOI 春合宿2022の問題）が大好きだと言っていました。ちなみに、大会期間中に韓国の選手とかなり仲良くなり一緒に街中を散策したり、インスタを交換したりしました。僕が唯一知っていた韓国語「폼 미쳤다（ポム ミチョッタ）」（若者の間の流行語で、「やばい」みたいな感じ）を言うとウケました。あと代表研修で解いた KOI の問題の議論とかで盛り上がりました。問題の説明で「朝昼夜の3つのフェーズがあって〜」と言うと全員に伝わって、みんな悪夢を思い出したみたいな顔をしてて面白かったです（問題概要）。その後その天才問題の writer を名乗る韓国の随行員と話す機会があり例の世界地図にサインしてもらって一緒に写真も撮ったのですが、帰りの飛行機で世界地図を見返しているとなんとその人物が ko_osaga 様だったことに気づきます。やべ〜〜
７．最後に / 引退報告
中学2年生の時に競技プログラミングに出会ってから5年間、このコミュニティには本当に色々とお世話になりました。この5年間を振り返ると多くの紆余曲折があり、色んな記憶が蘇ってきます。競プロの実力が上がったのはもちろんですが、それよりも、これから先長い人生を歩んでいく上で大切となることを学べた気がします。
僕は今まで、失敗すれば努力は無意味になると思っていました。目標を実現するために努力するのであって、実現できなければその努力は無意味だと。でも、その考えは大きな間違いでした。10年後、20年後に振り返った時に思い出すのは、努力の日々です。ある一時に成功したか失敗したかなどということではありません。僕はこれまでいくつかの成功を収めた一方で数え切れないほどの失敗も重ねてきましたが、それらは今となっては全て些細なことです。そもそもいくら努力したところで失敗するときは失敗するので、成功に執着しすぎては長く続きませんし、目標などというものは努力するためのモチベーションに過ぎません。僕が今まで目標のために努力すると思っていたのは逆で、本当は努力するために目標を作る、というのが正しいのだと気づきました。努力をすれば結果がついてきたりついてこなかったりします。もちろん他人は結果を見て自分を評価するでしょう。しかし、親密な関係の人ほど、結果よりも努力を評価してくれるはずです。その最たる例が自分自身で、努力しないで成功したとしても自信には繋がりません。自分の努力を一番よく理解しているからこそ、努力が自信につながるのです。僕は5年間競プロに没頭し、ようやくこのことに気づきました。
5年間何かに没頭できたというのはとても貴重な経験で、僕は本当に環境に恵まれていたと思います。改めて、ずっとライバルとして(?)お互い切磋琢磨し続けてきた Kodaman、一緒にチーム戦に出てくれた AItale、文化祭コンと ARC で一緒に作問してくれた PCT 君、同年代競プロerとして個人的に想い出深い kaage・define・anmichi、競プロを始めた頃から個人的に勝手に憧れを抱かせていただいている snuke さん、僕が直接会ったことのある競プロerの中で最も面白い人物(?)である yuto1115 さん、他にも、僕が競プロを始めるきっかけになった方々や初心者だった僕に親切に競プロ知識を教えてくださった方々、恐らく一般人が見てもよく分からない僕の趣味を受け入れ応援してくれた家族や友達など…ここに書き出すとキリがないですが、今まで僕と関わってくれた全ての人にこの場を借りて感謝申し上げます。
競プロの競技者としては来週のパソコン甲子園を最後に引退することを決意しました。ずっと雲の上の存在だった AtCoder 銅冠や Codeforces LGM を何とか達成できたので、あまり悔いはありません。もしパソコン甲子園で僕を見かけたら声掛けてくれると喜びます！それともしかすると JOI のチューターとかやるかもしれないのでその時もどうぞよろしくお願いします〜