第19回日本情報オリンピックの本選に参加してきました。
本来はてブロとかに書くような内容なんですが、僕はQiitaがだいすきなのでQiitaに書きます。
日本情報オリンピックとは
日本中の中高生が国際情報オリンピックへの出場枠4つをかけて争う、国内最大の中高生のためのプログラミング大会です。
英語のJapanese Olympiad in Informaticsを略して、よくJOIと呼ばれます。
アルゴリズムを考え、正確に実装する力が求められます。
毎年12月上旬に予選が行われ、2月上旬に本選、そして3月中旬から下旬にかけて行われる春期トレーニング合宿で、最終候補4人が絞られます。
今年からは予選が2段階に分かれ、9月から11月までに3回開催される1次予選と、12月に開催される2次予選の2つが行われるようになりました。
本選には約80人、春期トレーニング合宿には約20人が参加します。
本年度の実施概要はこちらです。
今回は、この日本情報オリンピックでの自分の成績を振り返りながら、本選の参加記とします。
1次予選
1次予選は、予定が合わなかったため、11月に開催される最後のものだけ参加しました。
ただし、前年に予選Bランク以上の成績を取っていれば2次予選には無条件で参加できます。
1次予選は、基本的なプログラミングができれば通過できます。
2次予選
2次予選からが本番です。今年は5問の問題が出題され、各100点の合計500点のうち、350点以上を取るとAランクで通過、となりました。他にも、指定校制度やブロック制、女性参加者奨励制度などで本選に招待されることもあります。
今年の2次予選は、昨年度までの予選と比べても非常に問題が易しく、4問目を解かないと350点以上を取ることは難しかったです。また、5問目の傾向が例年と大きく変わりました。
自分は4問目を解いて安心してのんびり5問目を解いていたら時間が無くなり、400点という結果になりました。少し悔しいですね。
本選
さて、ここからが今回のメインです。
本選は、茨城県つくば市のつくば国際会議場で行われました。
当日の流れから詳細に記したいと思います。
Day 1
1日目は、9時ごろ秋葉原駅に集合し、つくばエクスプレス線でつくば駅まで向かいました。
やはりつくばエクスプレスは速いですね。値段だけ異様に高いですが。
さて、この日は集合時刻の15時の前に、11時半からJAXAの見学ツアーの予約を入れていたので、JAXAに行ってきました。ここでのことは本選と関係ないので省きます。興味があれば行ってみましょう。
見学が終わり、会議場の近くに戻ったときは13時くらいでした。
昼食を食べる場所に困っていたので、会議場のすぐ近くにあったショッピングモール的ななにかに入ってみたら（フードコートを期待していました）、店が2つしかないフードコートがあったのでそこで食べました。
来年以降本選に行く人は昼食を食べてからつくばに来るか、昼食の場所をちゃんと探すかしましょう。
会議場に入ると、12:45ごろから2階で受付が始まりました。
名前と学校名の書かれた名札と書類を受け取り、待合室に向かいました。ここで灘や開成など、他校の人たちとの交流ができました。（ほんとか？）
プラクティスは16:00から始まりました。
本選で使う本番用のPCに触れ、5問の簡単な問題を解きます。
競技用PCに入っているエディタに、自分が使い慣れているGeanyがあったので多少安心できました。
VimやEclipseも開いてみましたが、やはり使い慣れているものが一番です。
問題自体は簡単で、一部JOIの過去問もあったので、すぐ解き終わりました。
問題をすぐ解き終わってしまったので、最終確認としてBIT,SegmentTree,UnionFindなどのデータ構造を試しに実装しました。
プラクティス中は割と自由行動に近く、多くの人が確認を終えて席を立ち、交流していました。
プラクティス終了後は短めの講演を聞き、夕食を兼ねた懇親会です。
一人一言ずつ自己紹介を求められ、名前順が極端に早い自分は何も準備できないまま前に立ちました。
本名も、アカウント名も、学校名も、TwitterIDも明かさない適当な自己紹介をしてしまいました。
Twitterで有名な絵を描いたりツールを作っている人たちと会えたのはよかったです。
他校の人たちと交流しているうちに割とすぐ懇親会は終わりました。
宿泊会場に移動した後は、入浴して、交流をして、就寝をしました。
特に言うことはありませんが、一つ言うとすれば大浴場が狭かったです。
特に更衣室の気温が尋常ではないほどに高かったです。
寝るのが少し遅くなってしまったのでちょっとだけ翌日が心配でした。
Day 2
2日目の起床は6:00です。寝るのが少し遅かったのもあってかなり眠かったですが、朝食を食べているうちに目は覚めました。
前日に荷造りをしておいたのに助けられ、定刻にバスに乗り込むことができました。
2人ほど寝たままの人がいて、バスの出発が遅れていました。
競技会場に向かうバスの中で、本選への意気込みツイートの予約をしました。めちゃくちゃどうでもいいですが、スマホでTweetDeckは使いにくすぎますね。
競技会場に着くと、前日と同じ待合室に通されました。待合室にいる時間はそこまで長くなく、すぐに本選会場に通されました。
飲み物と食べ物と小さなマスコットの持ち込みが認められていましたが、先述したように小さなマスコットを忘れたのでちょっと残念でした。
他には、競技直前に物理好きさんが魔剤を一気飲みしていたのが面白かったです。
競技本番
9:00ちょうど、本選競技が開始されました。
実は1問目を最初の数分間誤読していて、気づいてそこまでの考察が全部飛びました。
とはいえ、基本的な方針は変わらなかったので、解法の証明をしたあと実装し、すぐに満点を取りました。
2問目はもはや1問目より簡単かと思うレベルで、かなりのスピードで解けました。
2問目で詰まることを危惧していた自分にとっては悪くない問題セットでした。
3問目、本選での勝負と言ってもいい問題です。
3問目が解ければ春合宿にほぼ確実に進出でき、3問目が解けなければ、2問目の簡単さも相まってかなり進出が厳しくなることが明らかでした。
緊張しながら問題を開くと、いかにも怪しい制約が見えます。
DPか？と思ってOverview Sheetを見てみると、メモリ制限が明らかに他の問題より大きいです。
DPだということはほぼ確実で、あとはどんなDPをするか考えるだけです。
この問題の満点解法がここで高速に思いついたのはかなり頭が冴えていたと思っています。
確信を持ちながらほぼバグなく実装し、提出して満点が得られたのは、開始から54分後のことでした。
3問目が自分にちょうどいい難易度で、早く解けたことから、この時にはもうすでにかなりの自信がありました。しかし、3問目が解ける人はそれなりにたくさんいるはずなので、この後部分点をしっかり取り切るまで気は抜けません。
ここからは4問目と5問目を交互に考察していくことになります。
4問目でも最初誤読をし、難しそうなグラフ問題だったのでとりあえず5問目から考察を始めていくことにしました。
小課題3までは、SegmentTreeを使えば簡単に取れる部分点でした。
ここで前日に練習しておいたSegmentTreeの実装が役に立ち、バグなく素早く実装できました。
小課題4がすぐには分からなかったので、14点を取ってひとまず撤退しました。
4問目の問題文をよく読んでみると、誤読に気づきました。
小課題1は愚直に解けることがすぐ分かりましたが、実装がかなり重く、実装し終わったころには競技開始から2時間が経っていました。
5問目をもう1度見に行きましたがやはり分からないので、4問目に戻って小課題2の考察を始めました。
ここで、小課題2が意外と簡単に解けそうなことに気が付きます。考察を詰めようと思った瞬間、急にトイレに行きたくなって少し焦りましたが、2時間も残っていたのである程度安心することができました。
トイレに行って気づいたことは、かなり多くの人が競技中トイレに立っていたということです。行って戻ってくるまでに、4人もの本選参加者を見つけました。
塚本さんが「煮詰まったら1度トイレに立ってみてリフレッシュするのも手」と言っていたのも思い出したので、時間を無駄にした、という感覚も焦りもあまりありませんでした。
4問目の小課題2の考察が詰められたのは、開始から2時間20分ほど経ったころです。
実装もかなり重かったので結構時間がかかり、バグも多く埋めて、最終的に点を取ったのは終了40分前でした。
あとは4問目の小課題3と5問目の小課題4の考察です。
配点を考えると明らかに後者の方が簡単そうなのでそちらを考えていましたが、考察の方針を完璧に間違えており（bitset高速化をしようとしていました）、他の参加者にここでは後れを取りました。反省します。
結局、330点を取った状態で競技を終えました。
競技直後
競技が終わるとすぐに、解析の時間が始まります。
テストケースがコンテストページを通じて配布され、おかしい点などがないかチェックします。テストケースにおかしい点を見つけたら、異議（アピール）を出すことができます。
自分はソースを持ち帰るためのUSBメモリを持っていなかったので、知り合いに借りました。
他の参加者と話して立ち位置を知れるのも、この解析の時間です。
特に5問目などは、SegmentTreeに変わった演算を載せれば解けるような雰囲気がしていたため、他の参加者が4完しているのが少し怖かったですが、多くの人は3完+部分点で、30点以上の部分点を取っている人はほぼ見かけなかったため、ここでとても安心しました。結果としても、4完しているのは全参加者中2人だけでした。
灘勢とずっと点数の話をしていたら、委員会の人に早く昼食会場に行けと怒られました。ごめんなさい。
昼食を食べている間は、ずっと春合宿ボーダーの相談をしていました。300点より高いだろう、というのが多くの人の予測で、中には200点台になると言っている人もいました。
昼食を終えると、解説が待っています。
部屋がかなり暑かったので眠気と戦うのがつらかったですが、かつっぱさんの渾身のギャグで目が覚めました。
解説の途中で、3問目を解いた人が23人いるとわかり、ボーダーが300点を超えるのがほぼ確実だとわかりました。
そのあと、「情報科学の達人」の説明を聞きました。中学生なので参加できないのが残念です。
ここで解散の時間となり、電車で家まで帰りました、とさ。
おわりに
春合宿に行けることが確定しました。頑張ります。
この記事は、来年以降本選に行きたい人向けに書いています。
本選はとても楽しいので（特に交流が）、ぜひ精進して本選へ行きましょう！！！