第28回国際情報オリンピック(IOI 2016) ロシア大会 参加報告

日本選手団 団長 劉鴻志

  1. 概要
  2.  第 28 回情報オリンピックロシア大会(IOI 2016)は 2016 年 8 月 12 日から 8 月 19 日まで,ロシアのカザン市で開催された.
     開会式,競技,選手・随行員の宿舎は Universiade Village であった.一部のゲストは Korston Hotel に宿泊した.閉会式は Pyraimid complex で行われた.
     IOI 2016 には 80ヶ国・地域から 308 名の選手が参加した(公式参加者数).競技は 8 月 14 日と 8 月 16 日の 2 日間にかけて行われた.各競技日の競技時間は 5 時間であり,出題された課題数はそれぞれ 3 題(2 日間で合計 6 題)であった.競技結果に基づき上位者には金・銀・銅のメダルが授与された.全参加者の約半数にメダルが授与され,金・銀・銅の割合はおよそ 1:2:3 と定められている.今年は金メダルが 26 名(全参加者の約 8 %)に,銀メダルが 51 名(全参加者の約 16 %)に,銅メダルが 77 名(全参加者の 25 %)に与えられた.
     IOI 2016 における日本代表選手の成績は,金メダル 2 個,銀メダル 2 個であった.全員が銀メダル以上の結果を残した上,同じメダルの中でも上位の順位を獲得し,メダル獲得数・合計点ともに 4 位という去年を上回る結果を残すことができた.
     
    IOI 2016 日本選手団
     日本代表選手
    金メダル  井上卓哉 開成高等学校3年
      金メダル 髙谷悠太 開成高等学校2年
      銀メダル 川﨑理玖 筑波大学附属駒場高等学校2年
      銀メダル 増田隆宏 筑波大学附属駒場高等学校3年
     日本選手団役員
      団長 劉鴻志 東京大学理学部情報科学科3年(IOI 2012, IOI 2013 選手)
      副団長 三谷庸 東京大学理学部情報科学科3年(IOI 2013 選手)
      随行員 熊﨑剛生 東京大学理学部情報科学科3年(IOI 2013 選手)

     IOI は個人戦であり公式データとしての国別順位は存在しない.公表された成績に基づいて算出したところ,メダル獲得数による日本の国別順位は 4 位である.総得点による日本の国別順位も 4 位である.



  3. 競技について
  4.  IOI は数あるプログラミングコンテストのうちの 1 つであるが,同時に数ある科学オリンピックの 1 つでもあり,中高生を対象としていること,必要な知識を最小限にとどめ柔軟な思考力を問うこと,代表選手が世界各国から集うという特徴がある. 競技では,与えられた開発環境を用いてプログラム (C/C++, Java または Pascal) を作成してソースファイルを競技サーバから提出する.提出したプログラムは競技サーバ上でコンパイル・実行され,その実行結果に基づき得点が与えられる(過去の IOI ではこれ以外の採点方式の課題が出題されることもあったが,IOI 2016 では出題されなかった).実行時の時間・メモリに制限があるため,効率の良いアルゴリズムを設計することが重要となる.早く提出することによるメリットや,誤った解答を提出した場合のペナルティは無い.選手には,高度な課題に対して,5 時間の競技中にじっくりと取り組むことが要求される.
     競技時間内であれば解答の再提出も可能である (提出回数の制限は各課題ごとに 100 回であるが,通常この制限を超えて解答を提出することはあり得ず,実質的に提出回数は無制限と言える).
     IOI 2016 で出題された課題は以下の 6 題である.
               
    IOI 2016 競技課題
     競技 1 日目    分子の検出 (Detecting Molecules)
      ジェットコースター (Roller Coaster Railroad)
      近道 (Shortcut)
     競技 2 日目 お絵かきパズル (Paint By Numbers)
      バグの解読 (Unscrambling a Messy Bug)
      宇宙人 (Aliens)

     いずれも数理的思考力が問われる良問である.各課題はいくつかの小課題に分割されている.小課題の中には,単純な実装で得点が得られるものから,高度なアルゴリズムを実装しないと得点が得られないものまで含まれている.従って 1 つの課題を丸ごと落として 0 点になってしまう可能性は少ないが,満点を取るのは難しい.  また,すべての問題の満点の配点は同じため,比較的簡単な問題では満点を取りたいところであるが,他のプログラミングコンテストと違い,選手はコンテスト中に順位表を見ることはできない.このため,選手は問題の難易度も一人で判断し,コンテスト中の時間配分を考えなくてはいけない.  IOI はプログラムの作成技術を競う大会ではない.技術力があるに越したことはないが,それよりも IOI で重視されるのは数理的な思考力・洞察力である.競技では課題の本質を見抜く力が問われ,(気づけばそこまで難しくはないものの) 一見して何をしたらいいか分かりづらいような問題も出題された.

     (1) 競技規則の変更 : IOI の競技規則は毎年少しずつ改訂されている.IOI 2016 における大きな変更点は以下に挙げるものである.

      ・以前は,ある問題に対する得点が,その問題に対する提出の得点の最大値であった.IOI 2016 では,問題の小課題に対する得点が,その小課題に対するすべての提出の得点の最大値として定義され,問題に対する得点はすべての小課題に対する得点の合計に変更された.

     今までの採点では,例えば小課題ごとに別の解法を適用するといった場合,無関係の解法を 1 つのプログラムの中に埋め込むような形となっていた.新しい採点では,このような場合ではそれぞれの解法に対し別のプログラムを書き,提出することで同等の点数が得られるようになった.この変更によって,無関係な解法の間で変数名が衝突してしまうといったことを考慮する煩わしさが解消された.
     また,以下のルールの追加が提案されたが,GA meeting の結果却下された.

      ・選手は提出に対するフィードバックを観察することで,入力の内容を解析し,採点に使われるテストデータにのみ正答するプログラムを提出してはいけない.

     この提案は問題に対する考察・数理的思考を行うことなく,採点用データとそれに対する正解のみを知ることで得点することを防ぐためのものであったが,以下の意見もあり却下された.

      ・何が不正に当たるのか判断が難しい.例えば,解法の中でいくつかの場合分けをしていたが,そのうちのあるケースに該当するテストデータが存在しないことが提出により偶然判明した場合,そのケースに対する実装を放棄することは正当なのか?正当でないとすると,得点が改善しない上フィードバックも変わらない実装を選手は行わなければならない.正当だとすると,不正との違いを明確に定義するのは難しい.

      ・IOI 2013 で出題された Artclass という問題は,テストデータの特徴を解析し,フィードバックにより得点の上下を見ながら満点を獲得していく問題だった.コンピュータ科学においては入力の特徴の把握も重要であり,このような解法は不正とみなされるべきではない.

     (2) 競技実施方式 : 去年に引き続き,IOI 2016 で出題された課題の形式は,与えられたデータを処理する関数(プロシージャ)を実装したソースファイルを提出する方式 (プロシージャ方式) である.出力ファイルのみを提出するような特殊な形式の問題は,今年は出題されなかった.
     提出されたソースファイルは競技システム上ですぐにコンパイル・実行される.競技参加者にフィードバックが返され,自分の得点を知ることができる (現在の競技規則では,すべての提出に対して完全なフィードバックがあることが明記されている).満点でなかった場合は,どの小課題で失点したかを知ることができる.
     競技の途中経過はスコアボードとしてリアルタイムに全世界に公開された.日本から観戦した人も多くいたようである.ただし,先述のように競技時間中はスコアボードは選手には公開されない.選手が競技時間中に知ることができるのは,自分の得点だけである.
     去年と同様に,プログラム中で実装すべき関数の仕様を言語ごとに説明する「実装の詳細」節は問題文から省かれた.一方で,今年から「実装上の注意(Implementation notice)」が配布され,その中で配列・8 byte 整数の問題文中での表現と,それが各言語での構文にどう対応するのかが明記された.このため,問題文を簡潔にとどめつつ,より実装すべきことがはっきり定義できる表現になったと思われる.

     (3) 競技システム : 競技時間中,選手にはノート PC が 1 人 1 台与えられた.選手の PC には開発環境と,競技システムにアクセスするためのウェブブラウザがインストールされている.また,席を間違えないよう各PCの壁紙画像に各選手の顔写真が埋め込まれた.
     競技システムは,ここ数年の IOI とは違い,PCMS が用いられた.これは日本が本選・トレーニング合宿で用いている CMS とは異なるものであるが,完成されたシステムで両日通じ提出したプログラムの実行とそのフィードバックに関するトラブルはほとんどなかった.また,CMS との違いとして,全てのテストケースに対して提出したプログラムを実行するのではなく,不正解となったケースがあると以後のテストケースに対しては実行しない仕様となっていた.これにはプログラムの実行にかかる時間が削減できるメリットがある.インターフェースは簡潔で,その使い方については選手が自ずと理解できたようである.

     (4) 翻訳 : 競技日の前日の夜には副団長・随行員により問題文の翻訳が行われた.
    今年の翻訳システムは Markdown 形式のもので,すべての編集がサーバー上に保存され,システム上から印刷を要求できるなど,使いやすいものであった.1 日目には翻訳システムの仕様からサーバーが応答しない問題で合計 1 時間ほど待たされてしまったが,2 日目は修正されており,トラブルなく翻訳を終えることができた.日本語フォントについては,1 日目は去年同様若干の違和感を感じる程度であったが,2 日目には若干の違和感すら改善されとても自然なものになっていた.技術委員の努力には敬意を払いたい.

  5. その他・感想など
  6.  今年の IOI は,大会としての不備はほとんどなく,全てが順調に進み,無事に全てのイベントを終えることができた.例えば,競技は両日定刻に始まり,競技システムのトラブルもなく,観光や開会式・閉会式のスケジュールも概ね守られていた.これは選手・役員の宿舎と,競技の会場・GA meeting のホールが 1 つの施設に収まっていたことが大きい.隔離のため選手の宿舎・競技会場と役員の宿舎・翻訳会場は施設の反対側に配置されていたが,それでも徒歩で問題ない距離で移動の手間はとても少なかった.衛生面も問題なく,選手・役員が皆体調を崩すことなく大会を終えることができて大変安心している.


  7. おわりに
  8.  今年は金メダル 2 個,銀メダル 2 個と,すばらしい成績をおさめることができました.今回,IOI 2016 への選手団派遣を無事に終えることができましたのは,日頃より情報オリンピックの活動にご支援をいただいている皆様のお陰です.この場を借りてお礼を申し上げます.どうもありがとうございました.日本は IOI の開催を 2 年後に控えており,今後は今まで以上にお世話になることも多いと思います.今後ともよろしくお願いします.