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

プログラミングの国際大会「国際情報オリンピック」に行ってきます。

Programming IOI

8月14日から8月21日にかけてカナダのWaterloo大学で開催される「第21回国際情報オリンピック」に日本代表として参加してまいります。

f:id:qnighy:20100811224901p:image

情報オリンピックについて

情報オリンピックは、数学オリンピックや、化学、物理、生物、天文学オリンピックなどと並ぶ、「科学オリンピック」の1つです。
ちなみに科学オリンピックは基本的に高校生を対象としています。

数学オリンピックでは、数学の問題が出題され、その問題の答え(証明)を記述し、証明の正確さを競います。
情報オリンピックでは、問題を解くプログラムを書き、それを提出して、正しく解けたか、効率よく解けたかを競います。

情報オリンピックに要求されるのは、「情報科学」とか「計算機科学(コンピューターサイエンス)」とか呼ばれる分野の知識と、それを応用する力です。もちろん、プログラムが書けなければ話になりませんが。

f:id:qnighy:20100811224902p:image

情報オリンピックでは、ソフトウェアの開発技法よりも、プログラムのロジックを重視しますから、プログラマでも、自分は関係ないなと思う人が多いかもしれませんが、そんなこと言わずに興味を持っていただければ嬉しいです。

国際情報オリンピック

国際情報オリンピックは20年前にブルガリア大会から始まりました。今年は第21回を数え、カナダのWaterloo大学で開催されます。

http://www.ioi2010.org/ ちなみにタイトルスポンサーはBlackberryらしいです。

今年は80を越える国から、300人以上の参加者が集まります。(各国から最大4名派遣できます。)

国際情報オリンピックでは、参加者の上位1/12に金メダルが、続く1/6に銀メダルが、続く1/4に銅メダルが与えられます。
2006年から2009年までの間に日本は金を6つ、銀を3つ、銅を5つ獲得しています。
f:id:qnighy:20100811224903p:image

国際情報オリンピックのルールの変更点

今年はルールに2つの大きな改訂があり、結構大きなチェンジとなりそうです。

今まではこんな感じでした。
f:id:qnighy:20100811224904p:image
つまり、

  • 参加者はプログラムを作り、提出します。
  • コンテストサーバーはプログラムに直接データを入力し、出力を判定します。
  • 結果はコンテスト終了後にわかります。

これがこう変化します。
f:id:qnighy:20100811224905p:image

  • 全てのプログラム自分で入出力を書かず、用意されたインターフェースを用いて解答を行います。
  • N回分の提出について、全ての採点結果がわかります。
全ての提出プログラムの入出力の廃止

これによって、以下のような問題が出題される可能性が示唆されています。
f:id:qnighy:20100811224906p:image


すなわち、2つのプログラムを協調動作させなければならないということです。

面白そうですが、今までにおそらく存在しなかったであろう形式の問題なので、どちらかというと恐ろしいです。

全ての採点結果のフィードバック

おそらく、このフィードバックによって問題が簡単になるということはありません。
効率の良いアルゴリズムが見つからなければ、試行錯誤しても無駄だからです。

では何故これが採用されたかというと、「バグの抑止」が目的ではないかと僕は考えています。

TopCoderなんかだと、バグが点数を大きくわけますが、IOIでは「バグを埋めこまないこと」ではなく、「効率のよいプログラムを思いつくこと」を重視したいという考えがあると思われます。
つまり、「効率の良いアルゴリズムは思いついたのに、小さなバグのせいで点数を半分以上失った」ということはできればあって欲しくないと思います。
こういう場合、採点結果がフィードバックさればバグに気付くことができますから、安心です。
今年から競技環境にValgrindがインストールされるのも同じ流れかもしれません。

なのでこれは結構必然の流れかもしれません。

IOIまとめ

とにかく、無理せず頑張ります。目標は銀です。

あと楽しんできます。

日本情報オリンピック

さて、国際情報オリンピックの日本代表は、情報オリンピック日本委員会によって運営されている日本情報オリンピックによって選抜されます。

つまり、日本情報オリンピックは、高校生に対する情報処理の啓発と、国際情報オリンピックの日本代表の選抜と、それからアルゴリズム好きのためのオフ会を兼ねてるわけです。

選抜の手順はこんな感じ。
f:id:qnighy:20100811224907p:image

つまり僕はこの選抜をくぐり抜けてきたわけですね。

プログラミングが少しでもできる高校生なら参加できますから、ぜひ http://www.ioi-jp.org/ を参照してください!

おまけ

画像を作ったはいいものの説明するのが面倒くさくなったやつ

こんなことしてます

f:id:qnighy:20100811224908p:image

楽しい問題

f:id:qnighy:20100811224909p:image

宣伝