読者です 読者をやめる 読者になる 読者になる

高校生がアルゴリズムで世界に挑んできます

2011年7月22日から29日にかけて、IOI2011 (詳細は後述) がタイで開催されます。
以下の4名が日本代表として参加します。

  • 村井 翔悟 (開成)
  • 原 将己 (筑駒) ←自分です
  • 今西 健介 (八千代松陰)
  • 城下 慎也 (灘)

以下では、IOIに関してひと通り説明したあと、今年行われるライブ映像の配信とスコアボードの公開について説明します。
ぜひ見てね!

国際情報オリンピック(IOI)とは?

国際情報オリンピック(IOI)は、高校生向けの国際科学オリンピック*1の一つで、数理情報科学(Informatics)*2に関する知識、アルゴリズムの洞察力やプログラミングの能力を競うコンテストです。

ありていに言ってしまえば、TopCoderやICPCに代表される「(競技)プログラミングコンテストの一つと言えます。

日本では日本情報オリンピック(JOI)が実施され、選抜合宿で最も成績の良かった4名がIOIに派遣されます。

意外(?)なことに、日本の成績は毎年良く、USA、China、Russiaと並ぶレベルです。

出題内容

IOIでは、一日3問、合計6問の問題が与えられ、それぞれプログラムを書いて提出し、その正確性と速度で競います。

速度といっても、「何々というようなプログラミングテクニックを用いて63%高速化する」といった内容よりも、効率のよいアルゴリズムを考えることでオーダーを下げるといった内容が中心となります。

つまり、例えば、10万個のデータが与えられて、何か処理をしなければならないとき、そのうち2つの組み合わせ全部を試すと100億回のループを回さなければいけないところを、うまく工夫することによって、10万×17回程度のループで済ませるといったテクニックを競います。

また、去年は目新しいタイプの出題がありました。特に面白かったのが次のような問題です。

Wikipediaの記事の冒頭部が与えられたとき、その記事がどの言語のものかを当てるプログラムを作成せよ。

ただし、実行時は言語の番号と文字コードをシャッフルする。つまり、事前に学習させておくことは難しい。

その代わり、一個答えるごとにその正答が与えられるので、それを利用して学習することはできる。

次のような問題も出題されました。

収穫の終わったトウモロコシ畑を踏みつぶして迷路を作ることを考える。

トウモロコシ畑には障害物があり、障害物のない所は踏みつぶすことが出来る。

できた迷路の深さ(入り口から一番遠いところの距離)ができるだけ大きくなるように迷路を作りなさい。

今年の抱負

僕は去年のカナダ大会に引き続いての参加になります。
そこで、二つの目標を掲げたいと思います。

  1. 友達100人作ること。(まあ100人は無理だけど)つまり、他国の選手と積極的に交流していきたい。
  2. 去年に引き続き金メダルを維持すること。

動画・ライブ映像配信のスケジュール

どうやら、今年は http://www.ioitv.com/ライブ映像が配信されるようです。
そこで、http://www.ioitv.com/photo/time.php にある予定をここに転載します。

7月22日(金)
タイ時間 日本時間 プログラム 内容 備考
19:00 - 19:15 21:00 - 21:15 IOIにようこそ 夕食と各チームの到着、登録がリポートされる オンデマンド
7月23日(土)
タイ時間 日本時間 プログラム 内容 備考
8:45 - 10:00 10:45 - 12:00 開会式 ライブイベント ライブ
10:00 - 11:00 12:00 - 13:00 開会式 ライブイベント ライブ
独占インタビュー オンデマンド
13:00 - 13:30 15:00 - 15:30 実機練習 ライブ
18:00 - 18:15 20:00 - 20:15 こんばんはIOI 今日のハイライト オンデマンド
7月24日(日)
タイ時間 日本時間 プログラム 内容 備考
7:45 - 8:30 9:45 - 10:30 コンテスト一日目(開始) ライブイベント ライブ
13:00 - 13:15 15:00 - 15:15 コンテスト一日目(終了) ライブイベント ライブ
15:00 - 15:30 17:00 - 17:30 自由時間 選手を訪問(宿、食事、organ.) オンデマンド
18:00 - 18:15 20:00 - 20:15 こんばんはIOI 今日のハイライト(クラー、コンテスト、一日目の結果) オンデマンド
7月25日(月)
タイ時間 日本時間 プログラム 内容 備考
9:00 - 9:15 11:00 - 11:15 おはようIOI 昨日のハイライト(コンテスト、会合、一日目の結果) オンデマンド
12:00 - 12:30 14:00 - 14:30 自由時間 リーダー達を訪問(宿、食事、organ.) オンデマンド
18:00 - 18:15 20:00 - 20:15 こんばんはIOI 今日のハイライト(総会、旅行) オンデマンド
19:00 - 20:00 21:00 - 22:00 総会(stock record) オンデマンド
7月26日(火)
タイ時間 日本時間 プログラム 内容 備考
7:45 - 8:30 9:45 - 10:30 コンテスト二日目(開始) ライブイベント ライブ
13:00 - 13:15 15:00 - 15:15 コンテスト二日目(終了) ライブイベント ライブ
13:00 - 13:30 15:00 - 15:30 自由時間 visitorを訪問(宿、食事、organ.) オンデマンド
18:00 - 18:15 20:00 - 20:15 こんばんはIOI 今日のハイライト(コンテスト、二日目の結果、総会) オンデマンド
7月27日(水)
タイ時間 日本時間 プログラム 内容 備考
9:00 - 9:15 11:00 - 11:15 おはようIOI 昨日のハイライト(旅行、コンテスト、一日目の結果、総会) オンデマンド
12:00 - 12:30 14:00 - 14:30 自由時間 主催者に会う(宿、食事、organ.) オンデマンド
18:00 - 18:15 20:00 - 20:15 こんばんはIOI 今日のハイライト(IT exhibition showcase) オンデマンド
7月28日(木)
タイ時間 日本時間 プログラム 内容 備考
9:00 - 10:00 11:00 - 12:00 おはようIOI 昨日のハイライト(旅行、会合) オンデマンド
15:00 - 16:00 17:00 - 18:00 表彰式 ライブイベント ライブ
16:00 - 17:00 18:00 - 19:00 表彰式 ライブイベント ライブ
17:00 - 18:00 19:00 - 20:00 表彰式 ライブイベント ライブ
18:00 - 19:00 20:00 - 21:00 夕食パーティー ライブイベント ライブ
19:00 - 20:00 21:00 - 22:00 夕食パーティー ライブイベント ライブ

スコアボード

今年も去年に引き続き、競技中インターネットでリアルタイムのスコアボードが見られる見込みです。

今年のスコアボードは http://www.ioi2011.or.th/results です。是非覗いてみてください!

写真速報

日本チームによる写真速報は http://www.ioi-jp.org/ioi/2011/quickreport.html にあります。

*1:国際科学オリンピックには他に、数学、化学、物理、生物学などがある。

*2:この用語の扱いについては議論の余地がある。