第13回日本情報オリンピック(JOI2013/2014)春季トレーニング合宿について

2014年2月20日
情報オリンピック日本委員会

更新履歴

目次

昨年度からの変更点

昨年度の春季トレーニング合宿実施方法からの変更点は次の通りです.

春季トレーニング合宿競技実施方法概要
フィードバック
昨年度の春季トレーニング合宿では,競技参加者が競技中に利用できるフィードバックは,課題ごとに「完全」「部分」「例のみ」のいずれかでした. JOI2013/2014 春季トレーニング合宿では,利用できるフィードバックは,原則として「完全」のみになります. 競技参加者は,原則として,全ての課題について問題文中の例と全ての採点用入力データに対するフィードバックを利用することができます. ただし,課題によっては,競技中のフィードバックが制限される可能性もあります.
ソース提出回数の制限
競技参加者は,各課題ごとに,最後の提出から 1 分間は解答を提出することができません.

実施期間

2014年3月19日(水) 15:00 ~ 25日(火) 10:00

会場

競技,講義6,表彰式 講演会 選手発表会   講義1~5,講評 解説,宿泊
 NTT DATA 駒場研修センター    国立オリンピック記念青少年総合センター
 〒153-0041 東京都目黒区駒場 2-18-2     〒151-0052 東京都渋谷区代々木神園町3番1号
 電話 03-5738-3850     電話 03-3469-2525
 URL http://www.nttdata-univ.co.jp/establishment/    URL http://nyc.niye.go.jp

春季トレーニング合宿 スケジュール

競技実施時間
競技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日(水) 15:00 集合
15:00~17:30 ガイダンス・実機練習
18:00~19:00 夕食
19:00~21:00 講義1
(センター棟103教室)
3月20日(木) 7:00~8:00 朝食
9:00~14:00 競技1
14:00~15:00 昼食
15:00~15:30 解析1

(解析終了後,国立オリンピック
記念青少年総合センターに移動)
16:00~18:30 講義2
18:30~19:30 夕食
19:30~21:00 講評・解説1
(センター棟103教室)
3月21日(金) 7:00~8:00 朝食
9:00~14:00 競技2
14:00~15:00 昼食
15:00~15:30 解析2

(解析終了後,国立オリンピック
記念青少年総合センターに移動)
16:00~18:30 講義3
18:30~19:30 夕食
19:30~21:00 講評・解説2
(センター棟103教室)
3月22日(土) 7:00~8:00 朝食
9:00~14:00 競技3
14:00~15:00 昼食
15:00~15:30 解析3

(解析終了後,国立オリンピック
記念青少年総合センターに移動)
16:00~18:30 講義4
18:30~19:30 夕食
19:30~21:00 講評・解説3
(センター棟103教室)
3月23日(日) 7:00~8:00 朝食
9:00~14:00 競技4
14:00~15:00 昼食
15:00~15:30 解析4

(解析終了後,国立オリンピック
記念青少年総合センターに移動)
16:00~18:30 講義5
18:30~19:30 夕食
19:30~21:00 講評・解説4
(センター棟103教室)
3月24日(月) 7:00~8:00 朝食
9:00~12:00 講義6
12:00~13:00 昼食
14:30~15:30 表彰式
15:40~16:40 講演会
17:00~17:30 IOI2014日本代表選手
発表会
18:00~19:00 食事会
(国際交流棟レセプションホール)
3月25日(火) 7:00~8:00 朝食
8:00~8:30 清掃
9:00 アンケートなど
(センター棟103教室)
10:00 解散

表彰式

2014年3月24日(月)の 14:30~15:30 に,NTT DATA 駒場研修センター・イベントホールで第13回日本情報オリンピックの表彰式を行います.

講義

春季トレーニング合宿期間中に,以下の予定で情報科学に関する講義を行います.詳細は決まり次第このページでお知らせします.

講義1
3月19日(水) 19:00~21:00
講師:保坂和宏 先生(東京大学理学部数学科4年)
    IOI2008 エジプト大会 金メダル,IOI2009 ブルガリア大会 金メダル・準優勝,
    ACM-ICPC 2013 World Finals 金メダル・3 位,ICFPC 2011 準優勝,
    Facebook Hacker Cup, Google Code Jam, TopCoder Open Algorithm 世界大会出場
題目:Binary Indexed Tree のはなし
概要:本講義では,Binary Indexed Tree (あるいは Fenwick Tree) と呼ばれるデータ構造について解説します.同等以上の機能をもつ構造として Segment Tree や平衡二分木といったものがありますが,Binary Indexed Tree の特徴はそのシンプルさにあります.既に理解しているという人も,この機会に復習や応用範囲の確認に役立ててもらえればと思います.
講義2
3月20日(木) 16:00~18:30
講師:山下洋史 先生(東京大学工学部計数工学科数理情報工学コース3年)
    IOI2010 カナダ大会 銀メダル
題目:行列の基礎とその応用
概要:数や式を縦横に並べた行列と呼ばれる表現は,物理や工学を含む科学の広い分野で用いられています.この講義では,行列に関する基本的な事柄や,なぜ行列を用いると嬉しいのか,具体的にどのような問題に用いることができるのか,などをお話します.時間があれば,行列に関する数値計算のアルゴリズムについても少し触れる予定です.
講義3
3月21日(金) 16:00~18:30
講師:武永康彦 先生(電気通信大学大学院情報理工学研究科准教授)
題目:二分決定グラフとその応用
概要:二分決定グラフ(OBDD)は論理関数のグラフによる表現法として様々な分野に応用されています.この講義では,OBDDや,その変種として最近注目されているゼロサプレス型BDD(ZDD)について,その基本的な性質や処理手法のほか,組合せ問題への応用についても紹介します.
講義4
3月22日(土) 16:00~18:30
講師:小林佑輔 先生(東京大学大学院情報理工学系研究科助教)
    東京大学大学院情報理工学系研究科博士課程修了,博士(情報理工学)
    第27回 井上研究奨励賞 (2010年度), 第11回 船井研究奨励賞 (2012年),
    第2回 日本オペレーションズ・リサーチ学会 研究賞奨励賞 (2012年)
題目:理論的に高速なアルゴリズム
概要:アルゴリズムの理論研究においては,計算時間が入力の多項式時間で抑えられるか否かが,アルゴリズムの効率性(速さ)の重要な指標となります.この講義では,実用的なアルゴリズムとはかけ離れた,理論的な意味で高速なアルゴリズムについてお話しします.
講義5
3月23日(日) 16:00~18:30
講師:新屋良磨 先生(東京工業大学大学院情報理工学研究科博士課程1年)
    日本ソフトウェア科学会大会 学生奨励賞 (2011年),情報処理学会 山内奨励賞 (2012年1月)
題目:正規表現入門 ~星の高さを求めて~
概要:正規表現とはパターンマッチングのための記法であり,文字列検索の便利な道具として広く親しまれています.この講義では,正規表現の基礎から始め,「星の高さ」という性質に注目して正規表現の裏側に潜む数理構造に迫っていきます.1960年代から未解決である「星の高さ問題」に浪漫を感じてもらえると幸いです.
講義6
3月24日(月) 9:00~12:00
講師:城下慎也 先生(東京大学教養学部理科I類2年)
    IOI2011 タイ大会 銀メダル
題目:チューター企画:シュタイナー木コンテスト
概要:この企画は,多項式時間で厳密解を求めるのが難しい「シュタイナー木問題」という最適化問題を題材に,焼きなまし法などの手法を実践して理解を深めてもらおうという企画です.この企画に関する基礎的な事項等については,企画内で説明する予定ですので,特に予習などは必要はありません.(※「コンテスト」とありますが,コンテストに似た形式をとるだけで,JOI 春合宿の競技とは異なります.そのため,代表選考にこの企画での得点が影響することはありません.)

日本代表選手選考方法

国際情報オリンピック派遣日本代表選手選考に関する内規(2011年12月16日改訂版)に基づき,IOI 2014 日本代表選手を決定します.

春季トレーニング合宿期間中,3月20日,21日,22日,23日の 4 日間にかけて合計 4 回の競技を実施します.各競技日に 3 題または 4 題の課題が出題され,どの課題も 100 点満点です.4 日間の競技の合計点の上位 4 名を IOI 2014 日本代表選手とします.合計点が同点のため 4 位以内の代表候補者が 5 名以上になった場合は,同点の候補者の中で本選の順位が上位の者から代表とします.ただし,本選の成績を参考にするのは同点が生じた場合だけです.

春季トレーニング合宿は全日程参加が原則ですが,事情がある場合は,春季トレーニング合宿の一部の行事の欠席を認めることがあります.競技の一部を欠席した場合でも失格にはなりませんが,欠席した競技の得点は 0 点になります.欠席した競技に対して特別な措置(得点調整など)は実施しません.

春季トレーニング合宿競技実施方法概要

競技時間 競技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 時間)
課題数 各競技日に 3 題または 4 題の課題が出題される.
配 点 配点は各課題 100 点である.
各課題がいくつかの小課題に分割されることがある.小課題の配点は問題文中に記載する.
使用できるプログラミング言語 C, C++ (C++11 は使用できません)
使用できる用品 鉛筆,シャープペン,ボールペン,消しゴムなどの筆記用具を使用できる.
筆記用具は本委員会では準備しないので持参すること.計算用紙は本委員会が用意したものを使用すること.
競技中に小さなマスコットを机の上に置くことができる.
使用できる機器・ソフトウェア 本委員会が用意した機器と,認められた方法で持ち込んだキーボードのみ使用できる.
キーボードの持ち込みについては,小さなマスコット・キーボードの持ち込みについてを参照のこと.

また,本委員会が事前に準備し使用を許可したソフトウェアのみ使用できる.
競技で使用予定の機器・環境は以下の通りである.(変更される場合がある)

ハードウェア ノート型パーソナルコンピュータ 東芝 SATELLITE B551
  • CPU: Core i5-2520M (2.5 GHz)
  • メモリ: 8GB
  • ハードディスク: 250GB
  • ディスプレイ: 15.6インチ TFTカラー液晶 (1366×768)
  • マウス: 光学式スクロールマウス
ソフトウェア
  • Ubuntu 12.04 LTS 64-bit 英語版 (http://www.ubuntu.com/download/desktop)
    Windows 7 Professional (64 bit) 上で動作する VMware Player の仮想マシンで競技を行います.後日,練習用仮想マシンをダウンロードできるようにします.ダウンロード用 URL は,後日,春季トレーニング合宿参加者にメールで通知します.
    (VMware Player: http://www.vmware.com/jp/products/player/)
  • gcc/g++, python, ruby 1.9, gdb, DDD
  • eclipse-cdt, Code::Blocks, Geany
  • Gnu Emacs, vim, vim-gnome (gvim), gedit, Kate, KWrite, SciTE, joe, nano
  • C++ STL Document (英語)
  • Ubuntu ディストリビューションに含まれる,その他のソフトウェア
出題される課題 アルゴリズムを設計しそのアルゴリズムを C, C++ のいずれかのプログラミング言語で実装する課題が出題される.実行時の実行時間と使用メモリに制限があるので,解法のアルゴリズムの効率が重要となる.採点用入力データは,効率が異なる解法を識別できるよう調整されている.
春季トレーニング合宿では,日本情報オリンピックの予選・本選とは異なる形式の課題が出題されるかもしれない. 例えば,(ソースを提出せずに)出力データのみを提出する課題(Output only task)や,出力データの質を評価し採点する課題が出題されるかもしれない. また,競技中のフィードバックが制限される課題が出題されるかもしれない. その場合,課題の詳細は問題文および Overview Sheet に記載される.
過去の合宿で出題された課題が日本情報オリンピック 春季トレーニング合宿 記録で公開されている.
解答方法・解答提出方法 課題の趣旨に合致するプログラムを作成し,解答提出用 Web インタフェースからソースを提出すること.解答プログラムは,入力を標準入力から読み込み,出力を標準出力に出力し,正常終了すること(0 を返すこと).
各課題ごとに,最後の提出から 1 分間は解答を提出することができない.
ただし,課題によってはこれとは異なる方法で解答を提出するものもあるかもしれない.その場合,提出方法の詳細は問題文および Overview Sheet に記載される.
フィードバック 競技中に提出されたソースは Overview Sheet に記載されているコンパイルオプションを用いてコンパイルされ,問題文中の例と,全ての採点用入力データに対して実行される.その結果がフィードバックとして競技参加者に通知される.フィードバックを利用することで,自分の提出したソースが問題文の仕様をみたしているかどうかを確認することができる.また,その課題に関する自分の得点を競技中に知ることができる.
フィードバックの詳細については実機練習(プラクティス)の時間に確認することを勧める.
フィードバックが与えられるまでに時間がかかることがある.競技終了 15 分前までに提出されたソースには競技時間内にフィードバックが与えられる.それ以降に提出されたソースには競技時間内にフィードバックが与えられるとは限らない.
競技中のフィードバックが制限される課題が出題されるかもしれない.その場合,詳細は問題文および Overview Sheet に記載される.
採点方法 採点用入力データに対する出力の正誤で得点を定める.実行時の実行時間と使用メモリに制限がある.制限は課題ごとに異なり,競技時に配布される Overview Sheet に記載される.
各課題がいくつかの小課題に分割されることがある.小課題に関する詳細は問題文中に記載する.
採点プログラムは,Overview Sheet に記載されているコンパイルオプションを用いて解答プログラムをコンパイルし,採点用入力データに対して実行する.時間・メモリの制限を満たして正常終了し,かつ,出力が正しい場合に,その採点用入力データへの出力は正解となる.1 つまたは複数の入力データをセットにして採点を行う.1 つのセット内の全てのデータに正解した場合に限り,そのセット分の得点が与えられる.
ソースを複数回提出した場合は,提出された全てのソースが採点され,提出されたソースの得点の最大値がその課題の得点となる.
ただし,競技サーバに予期せぬ障害が発生した場合は,最後に提出されたソースのみを採点の対象とする場合がある.提出したソースは,各自の競技用 PC に保存しておくことを勧める.
課題によってはこれとは異なる方法で採点するものもあるかもしれない.その場合,採点方法の詳細は問題文および Overview Sheet に記載される.
質問 質問がある場合は,競技開始から 2 時間 30 分が経過するまで質問票を提出することができる.質問への回答は「正しい」「正しくない」「ノーコメント」「課題の記述の中に答えはある」「無効」のいずれかである.競技開始から 2 時間 30 分経過後も質問票を提出することはできるが,競技時間内に回答するとは限らない.
実機練習(プラクティス) 実機練習の時間中に,競技用 PC を使用して解答作成・解答提出方法が確認できる.操作方法,コンパイル方法,解答提出方法などを実機練習の時間中に確認すること.
実機練習の時間中に,競技用 PC に新たなソフトウェアやドライバをインストールすることはできない.
実機練習の時間中に,競技用 PC に周辺機器や USB メモリなどの外部メディアを接続してはならない(キーボードを持ち込む競技参加者が動作確認のためにキーボードを接続する場合を除く).
小さなマスコットやキーボードを持ち込んで競技に参加する場合は,実機練習の時間中に申請すること.詳細は小さなマスコット・キーボードの持ち込みについてを参照のこと.
解析の時間 競技終了後に競技結果を配布する.解析の時間に,採点用入出力データを用いて,自分の提出したプログラムの動作確認を行うことができる.
競技結果について異議(アピール)がある場合は「抗議票」を提出することができる.「抗議票」は解析の時間中に提出すること.解析の時間終了後のアピールは認めない.
禁止事項
  • 競技前(実機練習の時間中も含む)および競技中に,周辺機器や USB メモリなどの外部メディアを競技用 PC に接続してはならない(キーボードを持ち込む競技参加者が動作確認のためにキーボードを接続する場合を除く).
  • 競技用 PC には,いかなるデータもコピーしてはならない.競技用 PC に新たなソフトウェアやドライバをインストールしてはならない.
  • 競技中は,参考書・ノート・辞書などの資料を参照してはならない.競技中は,本委員会が用意した機器と,認められた方法で持ち込んだキーボードのみ使用できる.それ以外の機器(携帯電話・電卓・電子辞書など)を使用してはならない.
  • 競技参加者が提出する解答プログラムは,実行時に標準入出力以外にアクセスしてはならない.一時ファイルの作成,ネットワークへのアクセス,外部プログラムの呼び出しは禁止である.
  • 競技中は,競技システムを通じて解答を提出したり提出結果を確認する場合を除き,ネットワークやインターネット上のいかなるコンピュータへのアクセスも試みてはならない.競技システムを改ざんしたり,セキュリティを侵害することを試みてはならない.
  • 自分自身に割り当てられた競技用 PC とアカウントを使用すること.自分自身に割り当てられたアカウント以外のアカウントへのアクセス権を得ようと試みてはならない.自分自身に与えられた競技用 PC 以外のコンピュータにふれてはならない.
  • 競技中は,本委員会のスタッフを除き,他の人と連絡を取ってはならない.
  • Windows 上で動作する VMware Player の仮想マシン上で競技を行うこと.競技中は Windows 環境のデスクトップに戻ってはならない.
その他 競技参加者は,解析の時間中に会場責任者の許可を得て競技用 PC に USB メモリを接続して,ソースやデータなどを USB メモリにコピーして持ち帰ることができる.自分が競技中に作成したソースやデータなどを持ち帰りたい人は,USB メモリを持参すること.
競技課題および採点用入出力データは,後日,本委員会のウェブページで公開する.

小さなマスコット・キーボードの持ち込みについて

競技参加者は,小さなマスコットおよびキーボードを持ち込んで競技に参加することができます.ただし,持ち込む方法には次のような制限があります.

小さなマスコット・キーボードを持ち込む方法
注意事項

小さなマスコットおよびキーボードの持ち込みに関する上記の規則は,今後,変更することがあります. 変更があった場合は,このページでお知らせします.

オープンコンテスト

春季トレーニング合宿競技と同じ時間帯に,同じ課題を使ったオープンコンテストをオンラインで行う予定です.オープンコンテストにはどなたでも参加できます.

オープンコンテストに用いる競技システムの仕様は,春季トレーニング合宿競技で用いる競技システムと同一ではありません.

参加希望者は,オープンコンテストのページからアカウント登録を行なって参加してください.オープンコンテストに関する情報は,オープンコンテストのページに随時掲載予定です.(3月18日更新)

持ち物リスト

春季トレーニング合宿参加者の持ち物リストです.
本委員会が用意した PC を使用して競技を行いますので,PC を持参する必要はありません.
貴重品(財布,各自の PC,携帯電話など)は各自で管理してください.

交通費補助関連
本人確認・競技関連
その他

個人情報の扱いについて

個人情報の扱いについては,情報オリンピック日本委員会の「個人情報保護方針」をご覧ください.