※この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの２日目の記事です。
IOIにあまり興味が無い方は、下の方の僕が出題した問題の方だけをお読み下さい。
IOIとは
IOIとは"International Olympiad in Informatics"の略で、日本語で言うと「国際情報オリンピック」のことです。
IOIの大会としての特徴は以下のとおりです。
- 高校生以下が対象の世界大会
- 1989年から開催されており、2016年に第28回が行われた
- 各国で国内選抜があり、日本はJOIが選抜を行っている
- 日本から選手団が派遣されたのは1994~1996と2005~現在
- 2018年に日本（つくば）で開催予定
競プロのコンテストとしての特徴は以下のとおりです。
IOIへの問題の応募
毎年、その年の公式サイトに「Call for tasks」という形で問題募集の情報が公開されます。
今年のものはここです。
近年は問題の集まりがあまり良くないらしく、毎年応募期限が延長されています。
今年の期限は12/15に延びたので、まだ間に合いますよ！
IOIは時間ペナルティなどのないコンテストなので、部分点が多い問題が求められています。
簡単枠ならその限りではないかもしれません。
また、５時間３問なので、実装は重くてもOKです。
ただし、シラバスの範囲内からしか出題できないので注意してください。
IOIで求められている問題の傾向は以下のとおりです。（多分）
- 意味のある部分点の多い難しい問題
- 部分点はそれほど多くないが、面白い問題
- 変わった形式の面白い問題（ここ２年は出題されていない）
- 簡単枠の面白い問題（恐らく競争率が高い）
- 汎用的でかつ珍しめのテクニックを使う問題は好まれる傾向にありそう
応募する際に送る必要のある情報は以下のとおりです。
問題に自信があれば、なるべく親切にいろいろなファイルを作っておくと採用率が上がって良いのではないかと思います。
- 問題文（英語）
- 運営がストーリーを変えたりすることもあったりするので、原案を伝える程度のもので大丈夫だと思います。
- 過去問が公式サイトで公開されているので、構成はそれを参考にすると印象が良くなるかもしれません。
- 自分はmarkdownファイルとそれをpdfにしたものを用意しました。（txtでもなんでも良いと思います。）
- 解説
- 部分点を含めた解法を書いた文書を用意する
- 解答ソースコード
- IOIの形式は少し特殊なので、過去問のデータを取ってきてそれに合わせて書くと良いでしょう。
- テストデータ
- 必須ではありませんが、あるとかなり印象が良くなると思うので用意することを推奨します。
- ジェネレータも置いておくとなお良いと思います。
- プロフィール
- 作問者が何者なのかを書きます。協力者がいる場合はその人も。
- 連絡先、氏名、所属、国籍、情報オリンピックにおける立場（選手のトレーナー/委員会の役員/無関係等）を書きました。
- readme
- フォルダ構成を書いておくと親切だと思います。
もし実際に応募する場合は公式サイトを読んでもらうのが良いと思います。
応募を真剣に検討している方は、僕に声をかけてもらえれば、参考として僕が送ったファイル類を渡します。
IOIに問題が採用された時の流れ
2015にも１問送ったのですが、落ちました。落ちた場合は何も連絡は来ないので少しさびしかったです。
去年秋のある日大学に向かうバスで思いついた問題が自信作で、部分点もある程度つけられそうだったのでIOIに送ってみることにしました。
この年のCall for tasksの期限は年始すぐくらいで、帰省中にも作業してたような記憶があります。
1/11に提出し、しばらく経っても音沙汰がなかったので少し落胆していると、5/31に採用通知が来てめちゃくちゃ嬉しかったです。
問題が採用されると、shortlistという9問くらい(?)の問題候補の中に入ります。
実際に使われるのはこのうちの6問くらいで、残りは予備・来年に繰り越しになります。
問題が採用されてshortlistに載ると、IOIに招待され、IOIにguestとして参加することが出来ます。
もちろん、断ることも出来ます。
現地では特に仕事がないので、日本選手団と行動するなり、guest用の観光に行くなり、自由にしていればいいです。
ただし、問題が実際に使われて公開されるまではあらゆる情報が秘密なので注意が必要です。
現地に行く場合は、現地についてから「え、なんでいるんですか？おっ、writerか〜？」となるのは仕方ないので問題なしです。
IOI 2016に採用された問題
Code Festivalの本戦の問題を作ろうと、風船釣りを元ネタとした問題を作ろうとしていたときに原型が出来ました。
結局これは風船が全く関係ない問題になり、その後風船ツリーが出来ました。
その後、少し問題設定をいじると、自作問題の中でも 1, 2 を争うくらい好きな問題になりました。
さて、送った問題ですが、ドラえもんのガリバートンネル（とスモールライト）を知っていると理解しやすいと思います。
問題
ガリバートンネルが N 個あります。
トンネル i の入口のサイズは A_i、出口のサイズは B_i です。
snuke君はこれらのトンネルを１列に並べ、順番に通り抜けていこうとしています。
トンネルの入口に入るには、体のサイズが A_i より小さくなくてはなりません。
トンネルの出口から出てくると体のサイズはちょうど B_i になります。
snuke君の体のサイズは最初 1 です。
snuke君はスモールライトを持っていて、これを 1 秒使うと体のサイズを 1 減らせます。
トンネルの並べる順番を工夫したときの、スモールライトを使う必要のある秒数の最小値を求めて下さい。
実際に出題されたときは、ジェットコースターの侵入速度制限付きのレールユニットを組み合わせる設定になりました。
制約
- 2 ≦ N ≦ 200,000
- 1 ≦ A_i,B_i ≦ 10^9
入力例
4 1 7 4 3 5 8 6 6
(1,7) (6,6) (4,3) (5,8) の順で並べれば、１個目→２個目で１秒、２個目→３個目で２秒使えば良くて３秒で済み、これが最小なので答えは３。
体のサイズは、1-tunnel->7-light->6-tunnel->6-light->4-tunnel->3-tunnel->8 という感じで変化していくことになります。
部分点
1. (11点): 2≦n≦8.
2. (23点): 2≦n≦16.
3. (30 点): 答えが 0 かどうかだけ判定すれば良い
4. (36点): 満点
解説は別記事で紹介します。
また、ここのday1の２問目でonline judgeが利用できます。
IOIの大会中のコンテスト以外のイベント
1. 到着日
2. register、開会式
3. コンテスト１
4. エクスカーション１
5. コンテスト２
6. エクスカーション２
7. 閉会式
8. 出発日
というスケジュールです。
１週間と長いですが、あっという間です。
毎年、JOIから問題文の翻訳等をするための随行員が派遣され、各コンテスト日の前日夜に問題文の翻訳をします。
あと、大会期間中何度か開催される全体会議にも出席したりします。
僕はIOI 2015の随行員で、カザフスタンに行っていました。
そして今年はguestであって随行員ではなかったのですが、暇なので翻訳のお手伝いをしました。
大会期間中撮りためた写真をtumblrにまとめたので、IOIの様子が気になる方や、わふれるかが見たい方はどうぞ。
JOIの写真速報もあります。
IOI後
IOI2016の優勝者jcvb氏と帰りの空港で会ったので少し話しました。
結構前なので記憶が曖昧ですが、名前の由来についての話題をきっかけにして話しかけた気がします。
"jc"は本名のイニシャルで、それだと短すぎてIDが取れなかったので適当に2文字つけたと言っていたと思います。
出題の件に関しては「ロシア人が作ったのかなと思っていたが、コーチから日本人が作ったらしいという話を聞いた」みたいなことと、問題に関する良好なフィードバックがもらえて嬉しかった憶えがあります。
その数ヶ月後、CodeFestival 2016でksun氏に「are you snuke？本戦のwriterだよね、reverseの問題良かったよ。」的な感じで話しかけられました。
ksun氏はIOI2016にもカナダ代表で来ていたのでIOIの話題を振って「IOIの問題も書いたよ。」「ま？あの問題面白かった。本番中は解けなかったけど後で解いたよ。」的な話ができて嬉しかった。
IOIへの出題は、こんな風にIOI後に海外勢と話すときに話題に出せるという特典もありますよ。
