第１１回日本情報オリンピック（JOI 2011/2012）春季トレーニング合宿について

2012年3月11日
情報オリンピック日本委員会

更新履歴

• 2012.3.11　スケジュールの概要を掲出．以後，追加情報はこの欄に記載します．
• 2012.3.13　競技実施環境の「その他」に追記しました．
• 2012.3.18　競技実施環境の「その他」に追記しました．

目次

• 実施期間
• 実施会場
• 春合宿スケジュール
• 講義
• 日本代表選手選考基準
• 競技実施環境
• 表彰式

実施期間

2012年3月19日(月) 〜 25日(日)

実施会場

3月24日(土) 午後の表彰式，記念講演，IOI 2012 日本代表選手発表会，懇親会は東京大学駒場キャンパスで行います．

春合宿スケジュール

競技実施時間

競技1　3月20日(火)　9時00分〜14時00分（5時間）

競技2　3月21日(水)　9時00分〜14時00分（5時間）

競技3　3月22日(木)　9時00分〜14時00分（5時間）

競技4　3月23日(金)　9時00分〜14時00分（5時間）

春合宿スケジュール

赤字　国立オリンピック記念青少年総合センターで実施

青字　NTT DATA 駒場研修センターで実施

講義

講義１

3月19日(月)　19時00分〜21時00分

講師：保坂和宏　先生　（東京大学教養学部理科 I 類 2 年）
　　　　IOI 2008 エジプト大会 金メダル，IOI 2009 ブルガリア大会 金メダル・準優勝
　　　　ICFPC 2011 準優勝，TopCoder Open Algorithm 2011 8 位
　　　　ICPC，Google Code Jam，Facebook Hacker Cup 世界大会出場

題目：「解けない問題」を知ろう

概要：ある問題に対する効率的なアルゴリズムを考える際に，「この問題は効率的には解けない」というような問題を知っておくと便利なことがあります．プログラミングコンテストにおいても「解ける問題」「解けない問題」の知識を付けておくのは有意義です．この講義では，問題を解く方針を立てるためのちょっとした計算量理論に関して，いろいろな例を挙げて解説します．

講義２

3月20日(火)　15時00分〜17時30分

講師：秋葉拓哉　先生　（東京大学大学院情報理工学系研究科修士１年）
　　　　IOI を含むプログラミングコンテストの世界大会に計 8 回進出
　　　　主な結果は ICFPC'11 準優勝，TCO'11 7 位，GCJ'10 9 位など．
　　　　「プログラミングコンテストチャレンジブック」共著者

題目：プログラミングコンテストでのデータ構造２

概要：2010 年の「プログラミングコンテストでのデータ構造」の講義では，Union-Find，セグメント木，バケット法などを扱いました．今回は，さらに進んだ，希にプログラミングコンテストに出題される話題として，平衡二分探索木，永続データ構造，動的木などについて扱います．
（2010年の春合宿の講義スライド：http://www.slideshare.net/iwiwi/ss-3578491）

講義３

3月21日(水)　15時00分〜17時30分

講師：岩田陽一　先生　（東京大学大学院情報理工学系研究科修士１年）
　　　　ICPC World Finals 出場 (2009, 2010)
　　　　TopCoderOpen Marathon部門 2010 優勝 2011 準優勝, ICFPC'11 準優勝
　　　　「プログラミングコンテストチャレンジブック」共著者

題目：指数時間アルゴリズム入門

概要：プログラミングコンテストにおいては，多項式時間で解ける問題のみでなく，指数時間かかる問題もしばしば出題されています．指数時間かかる問題では，何の指数になるか，指数の底はどれほど小さいかがアルゴリズムの効率に大きな影響を与えます．この講義では，より高速な指数時間アルゴリズムを設計するための様々なテクニックを紹介します．

講義４

3月22日(木)　15時00分〜17時30分

講師：今城健太郎　先生　（京都大学情報学研究科修士１年）
　　　　IOI2006 メキシコ大会 銅メダル
　　　　スーパーコン2006 優勝, EPOCH2007 優勝

題目：情報分野でこの先生き残るには

概要：コンピュータアーキテクチャ，ネットワーク，マルチメディア，ハードウェアのそれぞれについて情報分野に行くのであれば専門にならなくとも知っておいて欲しい知識を紹介します．

講義５

3月23日(金)　15時00分〜17時30分

講師：稲葉一浩　先生　（グーグル株式会社）
　　　　SuperCon 1998 本戦出場
　　　　ACM/ICPC 2003 World Finals 11位入賞
　　　　Google Code Jam 2008 World Finals 出場

題目：形式言語理論の紹介

概要：文字列やツリー構造の(無限)集合を有限の記述で表現する「形式言語」の理論について初歩から応用を交えて解説します．構文解析や文字列検索でよく使われる「文脈自由文法」や「オートマトン」を題材としますが，この講義では，特にJOIなどのプログラミングコンテストに親しんだ人ならではの近道となるような方向からの紹介を目指します．

講義６

3月24日(土)　9時00分〜12時00分

講師：平野湧一郎　先生　（東京大学教養学部理科 III 類 2 年）
　　　　IOI 2009 ブルガリア大会 銅メダル

題目：ショートコーディング入門

概要：この講義ではショートコーディングを紹介します．ショートコーディングとは，正しい出力をするプログラムをできるだけ短いコード長で書く競技です．選手の皆さんもC 言語でのショートコーディングに挑戦してみましょう．

日本代表選手選考基準

　合宿中に 4 回の競技を実施します．競技 1〜4 でそれぞれ 3 問が出題されます．どの問題も 100 点満点で合計 1200 点満点となります．4 回の競技の合計点の上位 4 名を IOI 2012 日本代表選手とします．
　合計点が同点のため 4 位以内の代表候補者が 5 名以上になった場合は，同点の候補者の中で本選の順位が上位の者から代表とします．ただし，本選の成績を参考にするのは同点が生じた場合だけです．

競技実施環境

使用できるプログラミング言語

C, C++　（Java は使用できません）

使用できる機器・ソフトウェア

本委員会が用意した機器のみ使用できる．また，本委員会が事前に準備し使用を許可したソフトウェアのみ使用できる．
具体的に使用できる機器・ソフトウェアについては，下記を参照のこと．

機器

ノート型パーソナルコンピュータ　ThinkPad L512

筐体:A4ノート, CPU:Core i5-560Mプロセッサー(2660MHz), メモリ:4 GB, HDD:250GB

本体ディスプレイ: 15.6 インチ液晶ディスプレイ (1366×768)

マウス: 光学式スクロールマウス

ソフトウェア

Ubuntu 10.10 英語版 (Windows 7 Professional (32 bit) 上で動作する VMware Player 4.0 のゲストOS)

gcc/g++, gdb, Gnu Emacs, GVim, Kate, jEdit, C++ STL Document (英語)

これ以外にも仮想マシン内にインストールされているソフトウェアを使うことができる．
練習用仮想マシンをダウンロードできるようにする．ダウンロード用 URL は合宿参加者にメールで通知する．

出題される課題について

春合宿では，本選と同様に，アルゴリズムを設計しそのアルゴリズムを C, C++ のいずれかのプログラミング言語で実装する問題が出題される．実行時の実行時間と使用メモリに制限があるので，解法のアルゴリズムの効率が重要となる．採点用入力データは，効率が異なる解法を識別できるよう調整されている．
また，春合宿では，本選とは異なる形式の課題が出題されるかもしれない．例えば，（ソースを提出せずに）出力データのみを提出する課題（Output only task）や，出力データの質を評価し採点する課題が出題されるかもしれない．そのような場合，課題の詳細は問題文および Overview Sheet に記載される．
過去の合宿で出題された問題を「日本情報オリンピック 春季トレーニング合宿　記録」で見ることができる．

解答方法および解答提出方法

・課題の趣旨に合致するプログラムを作成し，解答提出用 Web インタフェースからソースを提出すること．
・解答プログラムは，入力を標準入力から読み込み，出力を標準出力に出力し，正常終了すること（0 を返すこと）．
・提出した解答には，フィードバック（「完全」「部分」「例のみ」のいずれか）が与えられる．フィードバックが与えられるまでに時間がかかることがある．競技終了 15 分前までに提出されたソースには競技時間内にフィードバックが与えられるが，それ以降に提出されたソースには競技時間内にフィードバックが与えられるとは限らない．
・ただし，課題によってはこれとは異なる方法で解答を提出するものもあるかもしれない．そのような場合，提出方法の詳細は問題文および Overview Sheet に記載される．
・ソースを提出する回数に制限はないが，ソースを複数回提出した場合は最後に提出したソースのみが採点の対象となる．

採点方法

・採点用入力データに対する出力の正誤で得点を定める．実行時の実行時間と使用メモリに制限がある．制限は問題ごとに異なり，競技時に配布される Overview Sheet に記載される．
・採点プログラムは，Overview Sheet に記載されているコンパイルオプションを用いて解答プログラムをコンパイルし，採点用入力データに対して実行する．時間・メモリの制限を満たして正常終了し，かつ，出力が正しい場合に，その採点用入力データへの出力は正解となる．
・正解した入力データに対し，配点分の得点が与えられる．問題によっては，複数の入力データをセットにして採点することもある．セット採点を行う場合は，1 つのセット内の全てのデータに正解した場合に限り，そのセット分の得点が与えられる．セット採点についての詳細は Overview Sheet に記載される．
・ただし，課題によってはこれとは異なる方法で採点するものもあるかもしれない．そのような場合，採点方法の詳細は問題文および Overview Sheet に記載される．
・ソースを複数回提出した場合は，最後に提出したソースのみが採点の対象となる．

仮想マシンの使用方法

Windows へのログインおよび仮想マシンへのログインはチューターが行う．
競技では仮想マシン内にインストールされているソフトウェアを自由に使うことができる．選手は仮想マシンで起動された Ubuntu から外に出てはならない．万が一，ログアウトしてしまった場合や，仮想マシンがフリーズした場合は，会場責任者の指示に従うこと．
STL のドキュメントが Ubuntu デスクトップ上の stl-docs/tech/stl/index.html から参照できる（Ubuntu のデスクトップ上にもリンクがある）．

キーボードの設定について

Ubuntu のキーボード設定が US キーボードに切り替わってしまった場合は，画面上部のキーボードのアイコンをクリックして，Jpn (日本語キーボード) に切り替えること．うまく切り替わらない場合は，一度 USA を選んでから Jpn に戻すとよい．

実機練習（プラクティス）について

実機練習の時間に競技用のノートパソコン・仮想マシンを使用して，解答作成・解答提出方法が確認できる． OS の操作方法，エディタの使い方，コンパイル方法，解答提出方法などに関する質問は，実機練習の時間中にチューターに質問すること．

競技中の質問について

競技中，課題について質問やコメントがある場合は「質問票」を提出することができる．競技開始後 2 時間以内に提出された質問には，
　　　　　正しい　　正しくない　　ノーコメント　　課題の記述の中に答えはある　　無効
のいずれかで答える．2 時間以上経過後も「質問票」を提出することはできるが，競技時間内に答えが返されるとは限らない．

解析の時間について

競技終了後に競技結果を配布する．解析の時間に，採点用入出力データを用いて，自分の提出したプログラムの動作確認を行うことができる．競技結果について異議（アピール）がある場合は「抗議票」を提出することができる．「抗議票」は解析の時間中に提出すること．解析の時間終了後の抗議は認めない．

禁止事項

・競技に先立ち，競技に使用するＰＣにいかなるデータもコピーしてはならない．
・競技中は，参考書・ノート・辞書などの資料を参照してはならない．
・競技中は，本委員会が用意した機器以外の機器（携帯電話・電卓・電子辞書・外付けキーボードなど）を使用してはならない．また，USB メモリや CD-ROM 等の外部メディアの使用も禁止されている．
・提出する解答プログラムは，実行時に標準入出力以外にアクセスしてはならない．一時ファイルの作成，ネットワークへのアクセス，外部プログラムの呼び出しは禁止されている．
・Windows 7 上で動作する VMware Player の仮想マシン上で競技を行うこと．競技中は Windows 環境のデスクトップに戻ってはならない．

その他

・筆記用具は各自で持参すること．計算用紙は本委員会が用意したものを使用すること．

・自分が競技中に作成したソースや採点用入出力データは，競技終了後に各自の USB メモリにコピーして持ち帰ることができる．ただし，競技用 PC への USB メモリの接続は，会場責任者の許可を得て行うこと (3/13 追記)．

・競技参加者は，競技中に小さなマスコットを机の上に置くことができる (3/18追記)．

表彰式

3月24日(土) の午後に東京大学駒場キャンパスで第１１回日本情報オリンピックの表彰式を行います．