|
|
IOI 2008 競技規則
|
IOI 2008 の競技規則の IOI 2007 からの主な変更点は以下の通りです:
この競技規則は競技手順 (Competition Procedures) や採点手順 (Judging Procedures) を含んでいる． この規則は最終版ではなく， 変更される可能性がある． 最終版は IOI 2008 の最初の総会 (GA; General Assembly) の際に配布する．
代表団の団長 (leader) は， 代表団の全メンバーにこの規則を完全に理解させ従わせる責務を負っている．
IOI 2008 の全ての課題は，
本質的にアルゴリズムを設計するものである．
課題によっては効率が重要である．
アルゴリズムの効率が重要な課題では，
test case は効率が異なる解法を識別できるように設計されている．
最も小さな test case は，
(効率はともかくとして)正当な解を出力する妥当な解法であれば
その課題の制約の中で正解を出力できるように，
設定されるであろう．
よって，
競技参加者が
大きなテストケースに対して制約内で正解を出力する解法がわからない場合も，
課題に取り組む価値はある．
課題には次の３つのタイプがある:
課題ごとにメモリ制限が指定される． この制限は，実行コード，スタック， ヒープを含む全ての使用メモリに対するものである．
選手が作成するソースプログラムは１つのソースファイルにまとめられないとならない． 課題の記述は次の要素から構成される：
選手が作成するソースプログラムは１つのソースファイルにまとめられないとならない． 選手には， 自分の解答で実験するための単純な「対戦相手 (opponent)」ライブラリが与えられる． しかし， 採点時には選手のプログラムは別のライブラリと共にコンパイルされる． 課題の記述に次のことが明確に書かれている：
入力データが競技参加者に与えられ， 解である出力データを作成することだけが競技参加者に要求される課題が 競技に含まれているかもしれない． 選手が出力データを決定するのに補助プログラムを書いたとしても， 解答と一緒にそのプログラムを提出してはならない． 入力データは ASCII テキストファイルで与えられる． このような問題では， 課題の記述に次のことが明確に書かれている：
選手は出力ファイル（だけ）を zip か tgz でまとめた書庫ファイル (archive) を提出しないとならない．
全ての課題において， 入力ファイルも出力ファイルも１行あるいは複数の行から構成される． （最終行も含めて）各行は行の終端 (end-of-line) を表す文字で終る． Linux では， 行の終端 (end-of-line) は単一の文字 '\n' (ASCII コードでは 10) で表される． 各行は， １つの要素 (item) か， 空白で区切られた複数の要素 (item) で構成される． 各要素は， 空白文字ではない印字できる文字 (ASCII コードでは 33 から 126 にあたる)からなる文字列である． 各要素は， 整数を表すこともあれば， 一般的な文字列を表すこともある． 各要素の意味は課題の記述の中で与えられる．
入力データと出力データのフォーマットおよび制限は課題の記述の中で与えられる． 出力データのフォーマットは， 課題の記述中の指示に厳密に従っている必要がある． ほとんどの場合，出力ファイル中で要素を区切るのに使う空白文字の厳密な個数や種類は無関係である． しかし， 可能な限り正確に出力の仕様に従うことを推奨する．
競技日は2日設定されている． 競技日ごとに5時間で3つの課題に取り組む． 競技日程は公式競技Webサイトで公表される．
最初の競技日より前に2時間の練習ラウンド (practice competition) が実施される． この練習ラウンドの目的は， 全選手が競技環境と競技手続きに慣れることである． 練習用の課題は， IOI 開催に先立ち公開される． 選手は紙に印刷した練習課題の解答を持ち込むことができる． 選手は練習ラウンドに参加することが推奨される．
課題内容が漏洩しないように， 直接と間接にかかわらず選手と団長の間の接触や通信は， 各競技日ごとに， 競技日前日の総会 (GA meeting) で構成員に課題が提示されてから， 競技日の5時間の競技が終了するまで， 禁止される． この間， 選手は， いかなる手段を用いようとも間接か非間接かを問わず総会の構成員や 課題を見た者と連絡を取ることは許されない． 総会の構成員は， 総会の構成員以外の者に課題に関連する情報を伝えることは許されない． 選手，総会の構成員，および，課題に触れた者は， IOI 会場の特定の場所への立ち入りを制限したいかなる指示にも従わねばならない．
選手がこの隔離に関する規則を破った場合は， その選手は失格となることがある． 選手以外の代表団あるいはその関係者が隔離に関する規則を破った場合には， 当該する代表団の全選手が失格となることがある．
不正行為の容疑をかけられないように， 隔離期間中， 選手と団長は携帯電話を使用するべきではないし， 全ての機器の無線機能をオフにするべきである．
全ての競技用マシンは Linux がブートするようインストールされている． Microsoft Windows は競技用マシンで利用できない． 以下のパッケージがインストールされている:
ハードウェア仕様 (Hardware specification):
課題を翻訳するために， 団長達に多言語対応の Microsoft Word が利用可能なコンピュータが供給される． それに加えて， 団長が持参したノートPCを接続するためにイーサネットポートが利用可能である．
競技会場において， 計算用紙と筆記用具が支給される． 競技日においては， 競技参加者は次のものを除いて競技会場に何も持ち込むことは出来ない:
選手が競技にキーボード， 小さなマスコットや英語の辞書を持ち込みたい場合には， 練習ラウンド (practice competition) の間に技術スタッフ (technical staff) に提出しないとならない． これらは全て検査され， 問題がなければ第１競技日に選手に手渡される． さらに， これらを第２競技日にも使用したい場合には， 第１競技日の競技終了時に使用したワークステーションの側に残していかなければならない． これらは再び検査され， 問題がなければ第２競技日に選手に手渡される． 第２競技日の競技終了後に， 選手はこれらを持ち帰らないとならない．
これら以外の物品を競技会場に持ち込もうとすることは不正行為とみなされる． 特に， 競技開催中に以下の物品を持ち込むことは厳格に禁止されている:
選手は競技開催中に組織委員会から供与された電子機器や印刷物を使用しても良い (例: 競技システムのユーザガイド， 競技環境にインストールされていたり競技サーバで利用可能な電子的なドキュメントやレファレンスマニュアル)．
競技日においては， 朝食終了後直ちに選手は競技会場に移動する． 選手は競技中ずっと組織委員会が用意した名札 (ID badge) を着用しないとならない． 選手は割り当てられたワークステーションを使用しないとならない； この情報は競技日の朝に通知される． 選手は競技開始5分前までに指定位置に着席しないとならない． 選手は競技用コンピュータに向かう途中で， 競技会場に持ち込みを許可されていないものを持っていないか検査される． 小さなマスコットと辞書類は， 練習ラウンド中に技術スタッフ (technical staff) に提出しなければならない． 競技用品 (Competition Supplies)」の節を見よ． 選手は割り当てられたコンピュータを見つけ， 着席し， 次のものに触れることなく待機しないとならない:
競技の開始は音による開始合図で知らされる． 開始合図があった後に上記の物品を使用することができる．
競技開始後最初の２時間30分間に限り， 選手は競技課題における曖昧な点や明確にすることが必要な事項について， 質問を記述して提出することができる． この時間を過ぎてもコメントが受領されることがあるかもしれないが， 回答されることはないだろう． 質問とコメントは， 配布される質問用紙 (Clarification Request Forms) に母国語（我々の場合は日本語） か英語で書き提出する． 必要に応じて， 質問が提出された後で科学委員会 (Scientific Committee) に送付される前に， 団長は選手が提出した質問を英語に翻訳する． 科学委員会は， 選手から提出された全ての質問に応答する． この過程には時間がかかるので， 選手は自分が提出した質問に対する回答を待つ間， 解答を続けるべきである． 選手は， YES/NO による回答が意味を持つような質問をすべきである． 質問に対する回答は， 次のいずれかである．
選手は自分の質問に関する議論に参加したり， 議論を傍聴したりすることはできない． しかし， 科学委員会が選手が課題内容を理解していないと判断した場合には， 課題の理解の補助となる英語の文章が回答に付け加えられ， 必要に応じて， 代表団リーダーが質問が書かれた言語に翻訳することがある．
IOI 競技は分散環境で実施される． 各選手は開発とテストを行う個別のワークステーションが与えられる． 採点および評価は， 選手のワークステーションと同様の実行環境を有する競技サーバ上で実施される． しかし， 競技サーバのハードウェアと選手のワークステーションのそれは異なる．
各選手のワークステーションには， Linux だけがインストールされている． ソフトウェア開発環境も利用可能である． これらのツールは競技課題の解答プログラムを開発するのに利用する． ワークステーション上で， プログラムを編集， コンパイル， 実行する回数に制限はない．
ワークステーションは， 競技サーバ， ドキュメントを提供する Web サーバ， 課題に関連するデータ， 印刷・テスト実行・解答の提出などの機能にネットワーク経由でアクセスできる．
競技サーバが提供する機能については， 次に記述されている． この記述は競技規則のすべてと同じように競技サーバ上オンラインで利用できる．
ワークステーションから， 相互に通信することはできないし， インターネットにアクセスすることはできない． 他の競技者のコンピュータやインターネットへアクセスしようとすると， 不正行為とみなされる． URL を変更してサーバを調べるなどの競技サーバを破ろうとする試みも不正行為とみなされる．
選手は，競技中にテキストファイルのみ印刷が許されている． 選手がドキュメントの印刷を要求すると， サポートスタッフ (support staff) が選手に印刷結果を届ける; 選手は印刷結果を入手するために席を離れてはならない． できるだけ早く印刷結果の配布するよう努めるが， 印刷要求が集中した場合は遅れることもある． 印刷ドキュメントの制限は 10ページかつ 50KB である． 制限を超えた印刷要求があった場合は， 最初の 10ページまたは50 KB だけが印刷される． 選手は， 各競技日ごとに高々30 ドキュメントの印刷が可能である．
選手は Web ブラウザを通して競技サーバに解答を提出する．
選手が使用した言語は解答ファイルの拡張子によって決定される:
解答はいつでも提出できる． 解答としてプログラムを要求する課題では提出される各ソースプログラムは C, C++, Pascal で書かれていなければならない． それらは 100KB 未満でなければならず， 評価サーバが 30 秒未満，メモリ 512MB 以下でコンパイルできなければならない． 上で挙げた以外の拡張子は受理されない． これらの条件を満たさない提出は採点システムから拒否 (reject) される． 課題記述中の入力例について正解を出力しないプログラムや 計算資源の制約を満たさないプログラムでも， 受理されることに注意せよ． 解答として出力ファイルを要求する課題では， 課題記述中の課題受理のための条件に違反していない限り， すべての提出が受理される． 選手がひとつの課題について2つ以上の解答を提出した場合， 最後に受理された提出が採点される． この規則は出力だけの課題でも適用される， つまり， 最後に提出した書庫ファイル (archive) が採点対象となる． 課題ごとの提出回数の上限は（拒否された提出も含めて） 50 回である．
解答としてプログラムを要求する課題では， 選手はテストインタフェース (TEST Interface) を通じて評価環境上でプログラムを実行することができる． この機能を利用するには， 選手はプログラムと入力ファイルをこのインターフェースに供給する． プログラムソースコードには提出インターフェースと同様の制限が適用される． 入力ファイルは高々 2MB である． しかし， 解凍した入力ファイルが20MB未満であれば， 圧縮したファイル （一つのファイルを含む gzip または zip 書庫ファイル (archive)） を提供することができる． テストインタフェースは個々の課題の計算資源の制約に従いプログラムを実行する． 供給された入力ファイルをプログラムに渡し， そして， 出力の最初の 100KB （エラー出力(error stream)は含まれない） を収集 (capture) する． 実行時間， 収集した出力とエラーメッセージを表示する．
テストインタフェース (TEST Interface) を使うことにより， コンパイルオプション，時間とメモリの制限なども含めた評価環境における 自分のプログラムの正確な振舞を選手が知ることができる．
各競技日ともに， 競技時間の最後の30分間はテストインタフェース (TEST Interface) を使用できない．
競技中， 選手は競技サーバを利用してファイルのバックアップをとることができる． 選手は定期的に解答のバックアップを作成するのが望ましい． 各競技日ごとに 100回までバックアップを作成することができる． 一つのバックアップのサイズ制限は 100KB である．
選手はいつでもサポートスタッフ (support staff) に手助けを求めることができる． スタッフは課題に関する質問には答えないが， 質問用紙 (Clarification Request Forms) や 印刷結果を配布したり， トイレや飲食物の場所を教えたり， コンピュータやネットワークの障害対応を手伝う． 選手が許されているネットワークの利用は， 指定された競技サーバに Web ブラウザでアクセスすることだけである; たった１回 'ping' コマンドを実行することでさえ， 厳格に禁止されている． 選手は自分自身で， コンピュータやネットワークの障害を 「修正 (fix)」したり， 「デバッグ (debug)」したり， 「調査 (check)」したりしてはならない; その代わりに， 補助を頼まなければならない．
競技終了の15分前，5分前，1分前に注意がある． 各注意は音による合図で知らされる． 競技終了は， 口頭と音による合図の両方で知らされる． 競技終了の通知後， 選手はただちに作業を止め， コンピュータを操作したり机上の他の物品を触れたりせずに， 机に着席したまま待機しなければならない． 改めて， 机から離れ競技会場から退室することについて指示が出る．
第１競技日の終了時には， 練習ラウンド時に提出した物品で 第２競技日においても使用したいものはワークステーションの側に 残しておかなければならない． 課題冊子を含むその他の物品は競技会場から持ち出さなければならない． 第２競技日の終了時には， マスコット，辞書類， その他の事前に提出した物品を含む全ての物品を持ち出し， 何も残してはならない．
出力のみの課題においては， 出力ファイルは上述の通りに提出し， 課題の記述中の説明通りに点数が与えられる．
解答としてプログラムが要求される課題に対しては， 提出されたソースファイルは， ソースファイルのサイズとコンパイル時間・メモリの制約のもと Linux 上でコンパイルされる． 次のコマンドが課題の解答をコンパイルするのに用いられる (課題名を abc としている):
提出された解答が正しくコンパイルされると， その後， 採点システムは， 課題に応じた実行時間とメモリに対する計算資源の制約の元でいくつかの入力に対してコンパイルされたプログラムを Linux 上で実行する．
解答は複数の異なる入力に対して実行されるが， それらの１つの入力に対する1回1回の実行のことをテストケース (test case) という． 各テストケースに対して， 計算資源の制約が課される． プログラムが計算資源に関する制約のいずれかを超過すると， プログラムは終了され， そのテストケースはどのような出力を生成するかにかかわらず不正解 (incorrect) となる．
課題に応じた計算資源の制約内でプログラムが出力をすると， その出力の正当性が検証される． 出力に応じてこのテストケースに対する得点が決まる． テストケースごとに配点が異なることもある．
計算資源制約の超過のためか， 正しくない出力をしたためかにかかわらず， テストケースが不正解 (incorrect) であった場合は， そのテストケースはゼロ点となる．
課題によっては， テストケースの結果に応じて部分点が与えられることがある． 部分点が与えられる場合は必ず， 課題文の中で明確に述べられている．
プログラムは停止する際に exit code 0 を必ず返さないとならない. 採点システムは他の exit code を失敗と解釈し， そのテストケースに対しては点は与えられない．
テストグループ (test group) は１つ以上のテストケースからなる． テストグループの得点は， そのテストグループを構成するテストケースに対する得点の最低点と定義する．
テストグループの目的は， 信頼性があり堅牢性がある方法でプログラムの明瞭な特性を評価するためである． これらの特性は， 例えば， 効率や特別な境界条件に焦点を合わせている．
全ての課題において， 少なくとも１つ「やさしい」テストグループが用意される． その要件は課題の記述中に独立して書かれる．
各課題の得点は， その課題のテストグループの得点の合計である．
採点システムに提出され受理された解答のみに対して得点が与えられる．
課題によっては， 詳細な反応 (detailed feedback) を利用することができる． 詳細な反応を利用可能な課題においては， 全ての受理された提出に対して詳細な反応が用意される． 提出された解答は評価の待ち行列 (queue) に入れられる． 解答プログラムは数秒から数分待ち行列に留めおかれることに注意． 順番が来ると， 選手の解答がいくつかの公式テストケースで評価される． 評価が終了すると， 競技サーバ (Competition Server) は， 実行されたテストケースの結果の概要 (summary) を選手に表示する． 概要は， 実行されたテストケースの総数と以下の起こりうる結果ごとの該当するテストケース数を含む:
テストケースをどのように組み合わせてテストグループが構成されているのかや， 各テストケースの配点といった情報は選手には知らされない． ただし， 各テストグループに対して， そのうちの１つのテストケースが詳細な反応を得るため実行されるのであれば， 同じテストグループに含まれる他のすべてのテストケースも実行される． (訳注: 各テストグループは完全に実行されるかまったく実行されないかのどちらかであって， １つのテストグループの中の一部のテストケースだけが実行されることはない， ということである．)
実際のデータや選手の解答が生成した出力やその他の実行時の詳細は，
選手には知らされない．
競技終了後，
解答は全てのテストケースについて再度評価される．
公式結果はこの再評価に基づく．
選手の解答が決定的 (deterministic) でない場合は，
詳細な反応と最終結果が一致しないこともある．
提出されたプログラムは以下を行ってはならない:
上記の行為は不正とみなされ， 失格という結果をまねくことがある．
提出された解答は， 問題記述中に与えられる仕様に適合したデータを用いて採点される． このデータは競技中は選手には秘匿されている．
これらのテストに基づいた採点結果の暫定版が，
競技終了後まもなく準備が整い次第，
団長のメールボックスに配られる．
採点に用いられたデータは，
競技会場で電子的に取得できる．
選手と団長は，
競技用用ワークステーションを用いて，
正しく採点されているか検証できる．
団長は抗議記入用紙 (Appeal Form) に記入することにより抗議を提起できる．
抗議記入用紙は，メールボックスの近くで配布しており，
必要事項を全て記入した抗議記入用紙を
競技結果配布後6時間以内に "Appeals" と表示のあるメールボックスに提出する．
全ての抗議は科学委員会が検討し，
科学委員会の決定は当該団長に通知される．
全ての抗議とそれらに対する処置は
当該競技日の最後の総会 (GA meeting) で報告される．
ある課題の採点において誤りが発見された場合には， その課題の受理された全ての提出解答を， その提出解答について抗議がなされたかどうかにかかわらず， 採点し直し，得点を付け直す． 再採点の結果， 選手によっては得点が上がることもあれば下がることもあることに注意せよ． すでに配布された結果から再採点によって誰もが得点の変更の可能性があるので， 新しい結果が印刷され，配布される．
第２競技日以降IOI表彰式前に， 科学委員会はメダル割当てを提示する． 選手の得点に基づきメダルが授与される． 各メダルに対して， 科学委員会はそのメダルを獲得するのに必要な最低点を提示する． 各メダルはそのメダルの最低点以上で１つ良いメダルの最低点には達しなかった選手に授与され． メダルの境界は次のルールで決定される:
どの選手も
のいずれかを行うと不正とみなされ，
失格の対象となる．
プログラムの禁止事項に違反した場合も不正とみなされ，
結果的に失格になることがある．
上述 (「採点」の節の「不正行為」の項) の不正とみなされ結果的に失格になる禁止プログラムのリストも参照せｔ．
不正は非常に重大に取り扱われ，
規則は厳格に適用される．
どのような種類であろうとも不正を行った者は，
国際科学委員会の裁量で， 直ちに失格になる．
団長が彼らの選手に不正に関する注意を行い，
どの選手も不正をすることがないように指示・教育し，
規則を説明し，
全選手が完全に理解していることを確認することがとても重要である．