情報オリンピックとは

１．国際情報オリンピック

　現在、高校生以下の生徒を対象とする次の６つのサイエンスオリンピックがあります（そのうちのいくつかはUNESCOの提唱で始まりました）。

• 数学　・・・　1959年から（日本は1990年から参加）
• 物理　・・・　1967年から（日本は2006年から参加）
• 化学　・・・　1968年から（日本は2003年から参加）
• 情報　・・・　1989年から（日本は1994〜1996年参加、2006年から参加再開）
• 生物　・・・　1990年から（日本は2005年から参加）
• 天文　・・・　1996年から（日本は未だ不参加）

このうち、国際情報オリンピック（International Olympiad in Informatics, IOI）は1989年にブルガリアで第1回が開催されて以来、2006年のメキシコ大会で18回を数えます。
　IOIの目的は、IOIの規約に

The main objectives to be accomplished by the IOI are:

• To discover, encourage, bring together, challenge, and give recognition to young people who are exceptionally talented in the field of informatics.
• To foster friendly international relationships among computer scientists and informatics educators.
• To bring the discipline of informatics to the attention of young people.

　競技は個人選で、１日５時間で３問を解くことを計２日行ないます。
　与えられた問題を解くためにアルゴリズムを考え、それに基づいてプログラムを書き、実際にコンピュータ上で実行させて出力した結果の正しさを競います（プログラムを書かない問題が出題されることも、アルゴリズムの効率の良し悪しにより相対的に評価される問題が出題されることもあります）。使用メモリ量および実行時間に厳しい制限があり、思いつくままに書いたプログラムでは時間内に答が出ないような問題がほとんどであり、良いアルゴリズムを設計するための高い数理的能力がプログラミング技能以上に求められています。 実際、 IOIの規約では「Informatics (情報学)」のスコープが次のように定められています：

In the scope of the IOI, the concept "Informatics" means the domain that is also known as computer science, computing science and information technology, but not the domain computer engineering.

　使用できるプログラミング言語は、2005年度までは C/C++, Pascal だけでした(それ以前は、BASIC や Logo が使えた時期もありました)。2006年度からは C/C++, Java だけになることが決まっていましたが、2006年も結局、C/C++, Pascal だけでした。

過去の開催国と将来の開催予定国

２００５年 ＩＯＩ ポーランド大会参加（選手派遣）国
Albania, Argentina, Armenia, Australia, Austria, Azerbaijan, Belarus, Bosnia and Herzegovina, Brazil, Bulgaria, Canada, China, Chinese Taipei, Colombia, Croatia, Cuba, Cyprus, Czech Republic, Denmark, Egypt, Estonia, Finland, France, FYR of Macedonia, Georgia, Germany, Great Britain, Greece, Hong Kong China, Hungary, India, Indonesia, Iran, Ireland, Israel, Italy, Kazakhstan, Korea, Republic of Kuwait, Kyrgyzstan, Latvia, Lithuania, Luxembourg, Macau China, Mexico, Moldova, Mongolia, Netherlands, Norway, Poland, Portugal, Romania, Russia, Serbia and Montenegro, Singapore, Slovak Republic, Slovenia, South Africa, Spain, Sri Lanka, Sweden, Switzerland, Syria, Thailand, Turkey, Turkmenistan, Ukraine, United Arab Emirates, United States, Vietnam.

　（ＩＯＩのフラッグ）

• ＩＯＩの公式ウェブサイト
• オランダ アイントホーヘン大学内の非公式サイト
  （ＩＯＩに関する豊富な情報のアーカイブがありますが、 2007年を最後にメインテナンスが行われていません。）

２．日本情報オリンピック

　日本情報オリンピック（Japanese Olympiad in Informatics, JOI）は、日本の高校生以下の生徒の中から情報科学的な能力の豊かな生徒を見出し、その才能の育成を助けるとともに、国際情報オリンピックに日本代表選手として派遣するために、特定非営利活動法人 情報オリンピック日本委員会（略称：IOI日本委員会）が主催している事業です。活動母体であるIOI日本委員会は、この事業を軸としつつ、それにとどまらず、数理情報科学に関する調査、研究、普及、啓発活動を行ない、日本の将来にとって必要不可欠である情報産業を支える人材養成に寄与する活動を行なっています。
　現在のIOI日本委員会の前身は、(財)数学オリンピック財団の協力の下に1993年に設立されたIOI日本委員会です。同委員会は1994年から1997年までの4年間、IOI国内予選（JOI）を開催し、1996年までの3年間に延べ6名の選手をIOIへ派遣し、金メダル1、銀メダル2、銅メダル1を獲得しましたが、バブル崩壊の影響で1997年以降休止状態にありましたが、2005年から独立行政法人科学技術振興機構の支援を受けて活動を再開しました。

３．参考資料

（ａ）日本情報オリンピックの選抜方式
　2007年度（JOI2007-2008）は以下の日程で選抜試験を行なう予定です。

（ｂ）試験問題例

　IOI 2005ポーランド大会の問題6問のうち1問だけを例として示します。日本情報オリンピックの予選や本選の問題には、このレベル（よりやや易しい）問題が含まれています。

　2005年度の場合、使用コンピュータは Intel Celeron 1.1 GHz (RAM 256MB，256kB cache)でした。

競技第２日の３問題のうちの１つ （メモリ使用制限：３２ＭＢ．実行時間制限１秒）

　Byteland王国の国土のほとんどは森と河川で覆われている．小さな川は合流してより大きな川となり，それらがまた合流して，ついにはすべての川が合流して１つの大河となってBytetown町近くの海に流れ込んでいる．
　Bytelandにはn個の伐採業の村があり，それらの村々のどれも川の近くにある．Bytetown町には１つの大きな製材所があり，王国で伐採された木材すべてを加工している．木材は村々から筏を組んで川下のBytetown町の製材所に送られている．木材の筏による輸送コストが大きいため，Bytelandの王様は村々のうちのどこかk箇所に製材所を新たに建設することを決めた．それによって，木材はBytetown町まで筏によって輸送する必要がなくなり，川下の最も近い製材所で加工することができるようになる．もちろん，製材所がある村の近くで伐採された木材を川下へ輸送する必要はない．Bytelandの川はどれも分流していないことを注意しておきたい．したがって，どの村にとっても，自分の村からBytetownまで川を下る道筋は一意的である．
　王様の主計官は各村で毎年どれだけの木材が伐採されているかを計算した．毎年の筏による輸送費用の総計を最小にするにはどこに製材所を建設したらよいかを決定したい．筏による輸送費用は，１本の木材を１キロメートル輸送するのに１セントかかる． 次のことを行なうプログラムを書け：

• 標準入力から村の数，各村の近くで伐採される木材の本数，および川についての記述を読み取り，筏を使って輸送するのに必要な費用の最小値を計算し，それを標準出力へ書き出せ．
• 入力の１行目には整数n (2≦n≦100) --- Bytetown町以外の村の数 --- とk (1≦k≦50 かつ k≦n) --- 新たに建設すべき製材所の数 --- が書いてある．これらの村々は1, 2, …, nと番号づけられていて，Bytetown町は番号0で表わされている．それに続くn行のそれぞれには３つの整数が１つの空白で区切って書いてある．第i+1行には次のものが書いてある：
  • w_i (0≦w_i≦10,000) --- 村 i で毎年伐採される木材の本数．
  • v_i (0≦v_i≦n) --- 村 i の川下で最も近い村（の番号）
  • d_i (1≦d_i≦10,000) --- 村 i から村 v_i までの川の距離（キロメートル）．
  • １年で伐採されるすべての木材をBytetown町の製材所に筏によって輸送するのにかかる費用は 2,000,000,000セントを超えないものとする．また、テストデータの50%ではnの値が20以下である．
• 標準出力に，１行に１個の整数，すなわち，筏による輸送費用の最小値（単位はセント），を書き出せ．

（ｃ）情報オリンピック日本委員会の概要