IOI 2018 に参加してきました.全体的には,よい大会だったと思います.コンテストの日は 9/3 と 9/5 の 2 日あり,両日ともコンテストの開始時刻・終了時刻が遅れていましたが,問題の質はとても良かったので楽しめたし,海外の選手ともそこそこ話せたのでとてもよい日々をすごすことができました.
自分は夏休みにはかなり予定 (アメリカに行ったり,JOI/JMO 夏季セミナーに出たり) を入れていたのと,IOI 以外の競技プログラミングの問題を解いていたことから,IOI の過去問は半年分 (IOI 2015 Day 1) しか解くことができませんでした.IOI の日本選手団は 8/31 の午後に東京に集まり,ここで IOI の過去の問題の解説がありましたが,あまり理解することができず,自分は IOI で本当にメダルを取れるのだろうか・・・ と思いました.ただ,問題をよく見ると少し考えれば解ける部分点もかなりあったので,金メダルを目標にしてもいいのでは,と思いました.また,ここでは IOI に関する説明もありました.例えば,「今年から選手に 『ID バッジ』 なるものの着用が義務付けられる」 ことや,「IOI シラバス (IOI で出題されるアルゴリズムの範囲) についての説明」,さらには「宿舎にはシャワーの数が少ないから,日本選手団は (日本風の) 風呂を使ってね」 などということも言われました.また,IOI の競技前日の 18 時頃から競技終了まで選手はインターネットが使えない 「Quarantine」 (インターネットに接続されたら即アウトという噂もある) というルールがあるということも言われました.宿舎の Wi-Fi はこの間使えなくなるのですが,日本選手団は携帯で容易にインターネットを使えてしまうので,この間は携帯を機内モードにするなりした方がいいということです.(競技は 2 日あるので Quarantine も当然 2 回なのですが,そのうち 2 回目でかなり怖いことが起きました・・・)
9/1 に日本選手団はつくば市へ移動しました.午後は海外選手と交流しましたが,どの海外選手とも会うのが始めてなのでかなり交流する難易度が高かったです.トランプで遊んだり,過去の IOI についての話を聞いたり,例の 「りんごのマスコット」 を投げあったりもしました.過去の IOI の問題で絵しりとり (しりとりで書く単語を言う代わりに,これに対応する絵を書くというもの) をしていた人もいて面白かったです.IOI 選手の宿舎は 「NITS (独立行政法人教職員支援機構)」 と 「KEK (高エネルギー加速器研究機構)」 がありましたが,日本選手団の部屋は NITS の 7 階 (最上階) の一部でした.KEK で泊まる人も朝食・夕食は NITS で食べるので,朝早い / 夜遅いバスに乗ってさらに移動しなければならないので,KEK の人は大変だなあと思いました.
9/2 にはオープニング・セレモニーがありました.オープニング・セレモニーでは,IOI 2018 JAPAN のテーマキャラクター 「IA」 が,IOI 2018 JAPAN テーマソング 「Euphoria」 を歌うというのがありました.「赤く光る星を追っていた,それの一つになりたかった」 という歌詞が含まれていて,これは 「レッド・コーダー (世界に数百人単位でしかいない競技プログラミングの実力者)」 や 「ターゲット (Topcoder レーティング 3000 以上の,世界に 20 人くらいいない競技プログラミングの実力者)」 を追いかけて,これを目指す自分 (あるいは,IOI 参加者全体?) というのがいるのだなあ,と思いました.また,国がアルファベット順 (開催国の JAPAN は最後) にどんどん呼ばれて行って,前のスクリーンにこの国の選手の顔写真が映り,この国の選手が立つという感じで開会式が進められていきました.ここに顔写真が映らなかった選手は,私たち 「IOI 2018 特別参加選手団 選手」 4 人だけであり,逆に面白かったです.その後,実機演習 (コンテストで使うコンピューターやコンテストシステムに慣れるためのコンテスト) があり,Road Service という JOI 2018 春合宿でも出題された Output Only 形式の問題で 98 点を短い時間で取ることができたので,IOI の競技への自信が少し高まりました.Quarantine が始まり,最後に 「さよなら世界」 (“Hello World” にあやかっている?) とツイートしていた人がいたのが面白かったです.夕食の後は 「Fun Time」 というものに参加し,いろいろ遊びました.
9/3 は競技 1 日目です!競技はつくばカピオという場所で行われました.会場に入って自分の席に着くと,「DO NOT TOUCH ANYTHING」 という紙が置いてありました.ANYTHING はコンピューターや問題が入った封筒のことを指していると思いますが,アナウンスで “Do not touch ANYTHING. Do not touch laptop, do not touch envelope, do not touch mascots, and do not touch bananas.” と流れ,周りの席の人の間で “Do not touch bananas” という文がジョークみたいだと話題になっていました.そして競技開始予定時刻の 9 時になりました.その直前に, 「見ること即ち支配すること」 という格言 (IOI 2017 の高谷悠太さんの参加記を参照) に基づいて会場の周りを見渡すと,なんと半分くらいの席が空いていました.9 時 10 分になっても,20 % くらいの人が会場に入れていなかったようです.そして競技が始まったのはなんと・・・ 9 時 40 分でした!
競技が始まりました.まず,問題 1 (Combo)から見ました.なぜか知らないけど問題文を読むのに 7-8 分くらいかかりました.自分は部分点から着実に取っていく戦略でやったので,開始 26 分で 30 点の部分点を取り,続けて開始 46 分で 問題 2 (Seats) の 11 点を取りました.その後,問題 3 (Werewolf) の 15 点を開始 77 分で取りました.つまり,この時点で 56 点の点数を取っていて割とよい感じでしたが,次に点数を更新するのは開始 179 分のことでした.
Werewolf の小課題 3 (小課題 1, 2 と合わせて 49 点) は,グラフが直線状になっている場合です.15 分くらい考えると解法が思いついたので,これは簡単に解けると思ってすぐに実装に入りました.かなり実装が重かったので,気合で 30 分くらいで実装してデバッグしたら,入力例で答えがマッチしたので,実装できたと思って提出しました.そうしたら,「15 点」 と返ってきました.バグっているケースを探すのは容易だったが,デバッグをするのがとても難しかったです.実装量が多いせいでデバッグに手を付けるのも難しそうであると結論付けたので,別の方法で実装を試みました.セグメントツリーやスパーステーブルを使わないで二分探索木 (C++ なので,std::set) を使って解く方法を思いつき,最初よりは楽に実装できました.そして,デバッグも簡単に終わらせていざ提出してみると,「0 点」 と返ってきました.デバッグを繰り返しても,最終的に 「実際の答えとは違う答えが出るような入力」 を見つける難易度が上がるだけなので,この問題は一旦保留にして Combo に取り組むことにしました.100 点は割とすんなり思いつき,開始 179 分で正解しました.つまり,合計 20 分くらいしかかけませんでした.その後,Werewolf に関して 「自動で小課題 3 の入力になり得そうなテストケースを生成し,小課題 1, 2 のグラフのサイズが小さい場合の解法と照合させる」 という自動解答チェッカーみたいなものを自分で作ることを決意しました.最終的に,開始 246 分で 49 点を取ることができました.(この問題に約 3 時間かけていることになります) Seats の 31 点は割とすぐにわかったので,最後の力で実装し,開始 284 分 (終了 16 分前) で正解することができました.終了 15 分前を過ぎると 「1 分に 1 回しか提出できない」 制約がなくなる影響でジャッジが返らなくなる可能性があり,この前に Seats の 31 点を取れたのでよかったです.合計点数は 180 点で,暫定順位は 62 位でした.しかし,この 6 点上を取っていた平木康傑選手は 21 位だったので, †順位の差† を感じました.その後,会場で IOI のライブ放送をしていた高橋直大さん (IOI のスポンサーをしている,AtCoder という会社の社長) と会ったり,IA の絵 (?) と一緒に写真を撮ったりしました.関連がない話だが,「25 年に 1 度の勢力で上陸する台風」 がちょうど近づいていたので,つくば市に影響が出ないかとても心配でした.
9/4 はエクスカーションで,つくば市内を観光しました.JAXA の宇宙関係の展示は見ましたが,日本選手団は JAXA に行ったことがある人が多かったので,売店みたいなところにある机で 「ワードバスケット」 というカードゲームをやったりもしました.その他には 「WARP STATION EDO」 などという場所にも行きましたが,日本選手団は 「JAPANESE-STYLE CASTLE」 を知っていたのであまり新しい知見などは得られませんでした.でもまあ楽しかったです.バスの中ではほかの選手と話したりしましたが,台風が心配だったので台風情報を見ると徳島県に非常に強い勢力で上陸したり,神戸市の近くで再上陸したり,アメダスを見たら関西空港の最大瞬間風速が 58.1 m/s になってたり,Twitter を開いたら,関西に住む JOI や競技プログラミングをやっている人の 「家が風で揺れる」 や 「ガラスやプラスチックがバキバキ揺れる」 などのツイートを見て,とても心配になりました.しかしその後少したって午後 6 時頃,Quarantine が容赦なく始まり,インターネットは使えなくなり,台風の状況・情報も含めて一切インターネット上の情報が得られなくなってしまいました.夜の Fun Time などでジャグリングとかをやりましたが,台風の影響で 20 時前には Fun Time が強制終了されました.外は雨が降っていなかったが,風は強く,最大瞬間風速 24.2 m/s がつくば市で観測されていました.(Quarantine 中なので,当然この数値も知りませんでした) ためしに宿舎の自分の部屋の窓を開けると,7 階という高い場所というのもあって,風がすごい勢いで入り込んでいき,ドアを開けるのに全体重をかけるほど力強かったです.その日は 23 時頃に寝たが,翌日の明け方 5 時 11 分頃に茨城県沖で発生した最大震度 4 の地震で起こされてしまいました.つくば市は震度 3 だったらしい (この震度の情報も Quarantine 中なので得られなかった) ですが,7 階にいたので揺れがさらに強く感じられました.幸いこの後に余震 (あるいは,本震?) はほとんど起こらなかったが,怖すぎてこの後全然寝られなかったから,コンテスト 2 日目直前の睡眠時間は結局 6 時間くらいと,ガチコンテストの前にしてはかなり小さい値になってしまいました.
いよいよ 9/5 になり,競技 2 日目です.1 日目の競技がかなり遅れたので,2 日目も遅れるのかなあと思ったら,10 分 「しか」 遅れずに競技がスタートしました.まず,問題 2 (Highway) から見ることにしました. Highway はインタラクティブ問題なので,僕がかなり得意とする問題だと思ったから, これを最初に手を付けたのです.しかし問題文を読み終わるまでに 10 分もかかってしまいました. 最初に簡単な 12 点解法を 10 分弱で考え終わりましたが,コンテストシステムを見たら正答率の分布が 「33% - 0% - 67%」 (これは,問題 1 の Doll で 2 点を取っている人が 1 人,問題 2 で正の点数を取った人はおらず,問題 3 の Meetings で 4 点を取っている人が 1 人,と容易に予測できた) から 「11% - 67% - 22%」 に変わっているところを見ました.これは,Meeting の 12 点を取っている人が 1 人出たということです!僕の双子の米田優峻選手は,競技前に 「ある問題で最初の部分点を取りたい」 とか 「インタラクティブ問題が得意なので,インタラクティブが出たらメインで手を付けようかなあ」 と言っていたので,この 12 点を取った人は米田優峻選手であると確信しました (これは本当にそうでした).自分は 12 点を取るのに 40 分くらいかかってしまいました.その後, 開始 72 分で 「そこまで難しくない」 Meetings の 19 点を取りました.その後,Doll に手を付けましたが, 16 点を実装するか, もっと良い解法を考えるか迷った結果, 後者の方を選び,53 点解法 (スイッチの個数が最大で 2N になるもの) が思いつきました.実装が少し大変だったけど,開始 141 分で 53 点を取ることができました.その次に,Meetings の 36 点が解けそうに見えたので手をつけました.多少バグを埋め込んだせいでデバッグを時間がかかりましたが,開始 214 分 (3 時間 34 分!) で解きました.Highway の 18 点も開始 237 分で解きました.Highway の51 点は思いついたのですが,それと同じ頃に Doll の 78 点以上が取れることが保証される解法 (実際には 86 点を取れた) が思いつき,どっちを選ぶか迷いました.しかし,実装がきつくなくて安定して解けそうな感じの後者を選びました.まだ 60 分近く時間があったので,ゆっくり実装方針を考えることができました.そこで,木を構築するのに queue で幅優先探索を使った方が実装が圧倒的に簡単になることに気づきました.実装するアルゴリズムの一部を紙に整理してから,プログラムを書きました.80 行程度で実装でき,バグもほとんどなくすぐに正解することができたので,とてもうれしかったです.正解したのは終了約 13 分前のことだったので,もう点数を伸ばせる問題はないなと思ったのと,コンテストでずっと問題を解いていてかなり疲れ切っていたこともあって,競技終了後まで 「Doll の 86 点が取れたことに対するうれしい気持ちで心を埋めよう!」 みたいな感じになっていました.しかし,競技終了 1 分前に突然 Doll の満点解法が思いついてしまったのです!
コンテストが終わりました.前のマケドニアの選手が Highway を 69 点を取っていたりして強かったです.コンテスト会場を出て順位表を見ると,”Hirotaka Yoneda” の横に 「42」 と書かれていました.これは自分の順位を表していたので,自分は銀メダルを獲れたが,金メダルはあと 1 歩 (厳密には 2 歩) のところで獲ることができなかったなあと感じました.また,ほかの日本選手団の結果を見てみると,井上航選手が 6 位で金メダルでした.彼は本当に天才だと思いました.2 年前の情報オリンピック春合宿からのライバルで,現在は Open Cup という世界的な競技プログラミングのチームコンテストでも自分と同じチームに入っています (ちなみにもう 1 人は僕の双子です) し,自分の人生において大きく関わっている一人だと思っています.また,米田優峻選手は 17 位で金メダルでした.彼が得意とするインタラクティブ形式の問題である Highway で 90 点を取っていたのが印象的でした.自分は日本選手団 8 人の中では,その次の順位 (42 位, 銀メダル) でした.
昼食が終わり,井上航選手などがメディアのインタビューを受けていました.彼は 「金メダルは獲れると思います」 (この時には順位表が公開されていて,彼は世界 6 位だった) と答えていて,本当にすごいなあと思いました.昼食が終わった後,コンテスト会場に戻り,海外選手と問題の解法を教えあうなどいろいろ交流もしましたが,午後 4 時 30 分から Doll の 100 点の続き (先ほど書いた通り,この時点では方針は分かっていたので,考察を詰めるのと実装するのと) をやりました.すると,考察は割と簡単に詰められ,実装も Doll の 86 点のコードを少し変えるだけだったので,合計 7 分 30 秒で解けてしまいました!改めてコンテストを振り返ってみると,コンテストの問題やシステムで少し分からないところがあったら質問をするというスタンスでいたので,これに合計 10~15 分くらい費やしてしまったり,トイレに行くのに合計 10 分くらい費やしてしまったり,そして最後は 13 分間も何もしていなかったので,これを合計するだけでも 30 分はあることから,Doll の満点 (点数が +14 される) はコンテスト中に通せるはずだったのになあ,もしこれが解けてれば 30 位で金メダルまであと 2 点だったのに・・・ と思いました.
9/6 はエクスカーションで茨城県を観光しました.9/7 は 「ナレッジフェア」 という,IOI のスポンサーをしている企業が色々やってました.1st PLACE という会社は IA のライブみたいなのを流していました.サイリウムは初めて見たので,面白いなあと思いました.また,Preferred Networks という会社の秋葉拓哉さん (過去に IOI の選手だった) が面白い講演をしていました.国立情報学研究所 (NII) の人も来ていて,いろいろ話したりもしました.「情報犬ビットくん」 という NII の公式キャラクターとも会いました (
https://twitter.com/NII_Bit/status/1037940105799823360).マレーシアの選手の Zi Song Yeoh さん (自分と同じ年に生まれた金メダリストで,前から存在は知っていた) とも会うことができましたので,競技プログラミングや IOI についていろいろ話したほか,NII の人からもインタビューを受けていました (
https://www.nii.ac.jp/news/2018/0911.html).
閉会式では特別参加選手団にはメダルは渡されませんでしたが,この後に IOI 選手と同じメダルを受け取ることができたのでよかったです.SAYONARA PARTY は世界の選手と一緒に夕食を食べながら交流しよう!みたいなイベントですが,この間に特別参加選手団はメダルを受け取っていたので,SAYONARA PARTY では思ったほど交流できなくて残念でした (来年の IOI はこういう時間をもう少し取ってほしいなあ).9/14 に 「表敬訪問」 というイベントがあったのですが,日本代表だけが行き,特別参加選手団は行きませんでした.
結論から言うと,IOI は銀メダル,さらにその中の上の方を取れてとてもうれしいのですが,やはり金メダルは獲れたのに,とも思っています.特に IOI では,コンテストの 5 時間をどのように使うかというのが,よく考えればかなり重要になってきます.競技 1, 2 日目両方ともミスったところは明らかで,1 日目は Werewolf に 3 時間もかける可能性があるような実装の計画 (?) は立てるべきではないというところ,2 日目は質問を書くのに 15 分かけたり最後の 13 分何もしなかったりとかなところが明らかな失敗だと思っています.競技に対する姿勢というものは重要である,というのはすべてのスポーツマンが知っている話ですが,IOI ではさらに競技の †戦略† や †時間の使い方† というのが重要になってくるので,これはやはり慣れるのが一番早い気がしてきました.しかし,IOI の過去問を実際のコンテストと同じ 5 時間で解くみたいな練習をして慣れたら,金メダルを獲れる可能性が大きく上がるとはいえ,金メダルが最終目標にはしてはいけないという使命は感じているし,やはり 「問題を解くアルゴリズムを,どのくらい速く探せるか」 や,「適切に実装方針を選び,どのくらい速く実装できるか」 というような根幹の部分も忘れてはいけないので,これからの練習する余地はまだあるなあと感じています.
読んでいただきありがとうございました!自分はあと 2 年 JOI に出るつもりですが,来年のみなさんの JOI の結果も期待しています!