2011-07-23
IOI2011メモ
07/20
荷物整理
- パソコン…一台あれば十分だが、二台持っていった。
- 衣服…下着は毎日替える。他は適度に使い回し。
- 書籍…「計算困難問題に対するアルゴリズム理論」を暇つぶし用に。また、競技中は紙の辞書を使用できるので、念のため持参した。(ただし、普通はLeadersが徹夜で翻訳してくれた問題文で足りるし、原文も本質的な部分は難しくないので、あくまで念のため。)
- ケーブル…携帯とか、デジカメとか、iPodとか、パソコンとかの充電器。
- コンセント関連…タイは電圧240V、形式はAが殆どだとのことなので特に準備なし。
- 薬…常備薬と胃薬・風邪薬などの類。
- カロリーメイト…向こうの食事が合わない場合などに備え。
- IOIの人々へのおみやげ…今回はうちわを買って持参した。
- カメラ…記録は大事
- パスポート…これがないと何も出来ない。ケースと一緒に。
- お金…多めでもいいでしょう
- 携帯…テレコムスクエアであらかじめ契約しておきました
- 切符や指定席券…成田や羽田に行くのに必要な何か
07/21
成田に向けて出発
- 成田エクスプレスを使った。
- 電車の中で、予め印刷しておいたルールを読み込んでいた。
- 空港では暇だったので先に両替をした。20000円を6400バーツにしたが正直多すぎかもしれない。
ホテル
- ホテルではいろいろ話し合った。今年のAPIOや過去のIOI、特にUtopiaやBusやほげほげについて。また、今年のルールの変更点について。(一日3問に戻ったりとか)
- 話し合っている人と話し合っていない人がいて、話し合っていない人はiPadでPrime Smashというゲームをやっていた。なぜかPrime Smashの得点に「人権ライン」という閾値が設定され、これに満たないことを人権がないと呼ぶことになっていた。わけがわからないよ。
- ホテルの部屋でインターネットが繋がらないとかいう空気よめない感じ(フロントでLANケーブルを借りようとしたら、何階ですかと聞かれ、8階ですと答えると、それじゃあ繋がりませんと言われた)
- 来年以降の人々は、ぜひとも早く就寝し、体を冷やさないようにしよう！(白目)
壮行会
- 壮行会では写真をとったり抱負を述べたりした。また、JOIから支給される他の選手に渡すためのおみやげは、消せるボールペンだった。
- あと今年は理事長が筧先生である。
07/22
タイに向けて出発＆到着
- 朝から頭痛が酷く、食欲が無いとかいう前代未聞の事態に陥った。チューターからやさしさとサリチル酸を貰って少し回復した。
- 出国は全く問題なかった。
- 飛行機内では寝てた。適当な癒し系音楽をカナル式イヤフォンで聞いていた。あと紙でツイッターしてた。
- 入国審査は、去年と違い全員無事突破。ちなみに、カメラに顔が映るように真っ直ぐ前を見る必要はあったらしい。
- ここで、IMOのためにオランダから直行してきた組と合流。
- ここで香港のチームと会ったが会話し損ねた
パタヤへ向かう
- パタヤまでバスで2時間くらい。
- すぐ酔いそうなくらいガッタンゴットンだったので、極力寝た。
- 隣のIsraelの人がNewsletterを持っていた。去年と同様にNewsletterにはパズルが掲載されていたが、今回はイラストロジック(Nonogramと表記されていた)だった。解いてて矛盾が生じたらしいので、縦と横の和を計算するよう言ってみた。そしたらたしかに差が1あった。
- 着いたら署名をしたりする作業に入った。
(書いてる途中でQuarantine期間に入ったのでまた明日(07/24)書く予定)
Permalink | コメント(1) | トラックバック(0) | 19:38 
2011-07-19
高校生がアルゴリズムで世界に挑んできます
2011年7月22日から29日にかけて、IOI2011 (詳細は後述) がタイで開催されます。
以下の4名が日本代表として参加します。
以下では、IOIに関してひと通り説明したあと、今年行われるライブ映像の配信とスコアボードの公開について説明します。
ぜひ見てね！
国際情報オリンピック(IOI)とは？
国際情報オリンピック(IOI)は、高校生向けの国際科学オリンピック*1の一つで、数理情報科学(Informatics)*2に関する知識、アルゴリズムの洞察力やプログラミングの能力を競うコンテストです。
ありていに言ってしまえば、TopCoderやICPCに代表される「(競技)プログラミングコンテスト」の一つと言えます。
日本では日本情報オリンピック(JOI)が実施され、選抜合宿で最も成績の良かった4名がIOIに派遣されます。
意外(？)なことに、日本の成績は毎年良く、USA、China、Russiaと並ぶレベルです。
出題内容
IOIでは、一日3問、合計6問の問題が与えられ、それぞれプログラムを書いて提出し、その正確性と速度で競います。
速度といっても、「何々というようなプログラミングテクニックを用いて63%高速化する」といった内容よりも、効率のよいアルゴリズムを考えることでオーダーを下げるといった内容が中心となります。
つまり、例えば、10万個のデータが与えられて、何か処理をしなければならないとき、そのうち2つの組み合わせ全部を試すと100億回のループを回さなければいけないところを、うまく工夫することによって、10万×17回程度のループで済ませるといったテクニックを競います。
また、去年は目新しいタイプの出題がありました。特に面白かったのが次のような問題です。
Wikipediaの記事の冒頭部が与えられたとき、その記事がどの言語のものかを当てるプログラムを作成せよ。
ただし、実行時は言語の番号と文字コードをシャッフルする。つまり、事前に学習させておくことは難しい。
その代わり、一個答えるごとにその正答が与えられるので、それを利用して学習することはできる。
次のような問題も出題されました。
収穫の終わったトウモロコシ畑を踏みつぶして迷路を作ることを考える。
トウモロコシ畑には障害物があり、障害物のない所は踏みつぶすことが出来る。
できた迷路の深さ(入り口から一番遠いところの距離)ができるだけ大きくなるように迷路を作りなさい。
今年の抱負
僕は去年のカナダ大会に引き続いての参加になります。
そこで、二つの目標を掲げたいと思います。
- 友達100人作ること。(まあ100人は無理だけど)つまり、他国の選手と積極的に交流していきたい。
- 去年に引き続き金メダルを維持すること。
動画・ライブ映像配信のスケジュール
どうやら、今年は http://www.ioitv.com/ でライブ映像が配信されるようです。
そこで、http://www.ioitv.com/photo/time.php にある予定をここに転載します。
7月22日(金)
| タイ時間 | 日本時間 | プログラム | 内容 | 備考 |
|---|---|---|---|---|
| 19:00 - 19:15 | 21:00 - 21:15 | IOIにようこそ | 夕食と各チームの到着、登録がリポートされる | オンデマンド |
7月23日(土)
| タイ時間 | 日本時間 | プログラム | 内容 | 備考 |
|---|---|---|---|---|
| 8:45 - 10:00 | 10:45 - 12:00 | 開会式 | ライブイベント | ライブ |
| 10:00 - 11:00 | 12:00 - 13:00 | 開会式 | ライブイベント | ライブ |
| 独占インタビュー | オンデマンド | |||
| 13:00 - 13:30 | 15:00 - 15:30 | 実機練習 | ライブ | |
| 18:00 - 18:15 | 20:00 - 20:15 | こんばんはIOI | 今日のハイライト | オンデマンド |
7月24日(日)
| タイ時間 | 日本時間 | プログラム | 内容 | 備考 |
|---|---|---|---|---|
| 7:45 - 8:30 | 9:45 - 10:30 | コンテスト一日目(開始) | ライブイベント | ライブ |
| 13:00 - 13:15 | 15:00 - 15:15 | コンテスト一日目(終了) | ライブイベント | ライブ |
| 15:00 - 15:30 | 17:00 - 17:30 | 自由時間 | 選手を訪問(宿、食事、organ.) | オンデマンド |
| 18:00 - 18:15 | 20:00 - 20:15 | こんばんはIOI | 今日のハイライト(クラー、コンテスト、一日目の結果) | オンデマンド |
7月25日(月)
| タイ時間 | 日本時間 | プログラム | 内容 | 備考 |
|---|---|---|---|---|
| 9:00 - 9:15 | 11:00 - 11:15 | おはようIOI | 昨日のハイライト(コンテスト、会合、一日目の結果) | オンデマンド |
| 12:00 - 12:30 | 14:00 - 14:30 | 自由時間 | リーダー達を訪問(宿、食事、organ.) | オンデマンド |
| 18:00 - 18:15 | 20:00 - 20:15 | こんばんはIOI | 今日のハイライト(総会、旅行) | オンデマンド |
| 19:00 - 20:00 | 21:00 - 22:00 | 総会(stock record) | オンデマンド |
7月26日(火)
| タイ時間 | 日本時間 | プログラム | 内容 | 備考 |
|---|---|---|---|---|
| 7:45 - 8:30 | 9:45 - 10:30 | コンテスト二日目(開始) | ライブイベント | ライブ |
| 13:00 - 13:15 | 15:00 - 15:15 | コンテスト二日目(終了) | ライブイベント | ライブ |
| 13:00 - 13:30 | 15:00 - 15:30 | 自由時間 | visitorを訪問(宿、食事、organ.) | オンデマンド |
| 18:00 - 18:15 | 20:00 - 20:15 | こんばんはIOI | 今日のハイライト(コンテスト、二日目の結果、総会) | オンデマンド |
7月27日(水)
| タイ時間 | 日本時間 | プログラム | 内容 | 備考 |
|---|---|---|---|---|
| 9:00 - 9:15 | 11:00 - 11:15 | おはようIOI | 昨日のハイライト(旅行、コンテスト、一日目の結果、総会) | オンデマンド |
| 12:00 - 12:30 | 14:00 - 14:30 | 自由時間 | 主催者に会う(宿、食事、organ.) | オンデマンド |
| 18:00 - 18:15 | 20:00 - 20:15 | こんばんはIOI | 今日のハイライト(IT exhibition showcase) | オンデマンド |
7月28日(木)
| タイ時間 | 日本時間 | プログラム | 内容 | 備考 |
|---|---|---|---|---|
| 9:00 - 10:00 | 11:00 - 12:00 | おはようIOI | 昨日のハイライト(旅行、会合) | オンデマンド |
| 15:00 - 16:00 | 17:00 - 18:00 | 表彰式 | ライブイベント | ライブ |
| 16:00 - 17:00 | 18:00 - 19:00 | 表彰式 | ライブイベント | ライブ |
| 17:00 - 18:00 | 19:00 - 20:00 | 表彰式 | ライブイベント | ライブ |
| 18:00 - 19:00 | 20:00 - 21:00 | 夕食パーティー | ライブイベント | ライブ |
| 19:00 - 20:00 | 21:00 - 22:00 | 夕食パーティー | ライブイベント | ライブ |
スコアボード
今年も去年に引き続き、競技中インターネットでリアルタイムのスコアボードが見られる見込みです。
今年のスコアボードは http://www.ioi2011.or.th/results です。是非覗いてみてください！
写真速報
日本チームによる写真速報は http://www.ioi-jp.org/ioi/2011/quickreport.html にあります。
Permalink | コメント(0) | トラックバック(0) | 21:21 
2011-05-07
第23回国際情報オリンピック(タイ大会)の日本代表になりました。
Programming, Algorithm, JOI, IOI
IOI概要
国際情報オリンピックは、問題を効率よく解くアルゴリズムに対する洞察力を競うためのプログラミングコンテストであり、数学・生物・化学・物理と並ぶ国際科学オリンピックの一つであると同時に、数あるプログラミングコンテストのうちの1つでもあります。
国際情報オリンピックは1989年の第1回以降、毎年各国の持ち回りで開催され、今年(2011年)はThailandのPattayaで開催されます。
各国は最大4人を国際大会に派遣することができます。2010年カナダ大会では83国から300人が参加しました。
IOIの問題概要
IOIで出題される問題は、単なるコーディングの能力にとどまらず、問題を効率よく解くための数学的な洞察力を問う問題がほとんどです。また、IOIでは、シラバスによって前提としてよい知識が制限されるので、よく知られた特定のアルゴリズムに帰着する問題よりも、立式の仕方など発想力を問う問題が出題される傾向が強いと言えます。
IOIの出題傾向は、年によっても大きく変わります。特に2010年のカナダ大会では、従来と同様の「アルゴリズムとデータ構造」が主題となる一般的な問題の他に、「NP困難な組合せ最適化(出力のみ問題)」「対話式の問題(数当て)」「通信量を可能な限り抑える問題(通信複雑性)」「自然言語解析(情報検索)」など目新しかったり珍しかったりする問題が多数出題されました。
メダル概要
IOIではおおよそ参加者数の1/12が金メダル、1/6が銀メダル、1/4が銅メダルで、合計半分程度の参加者がメダルを得られるように規定されています。
2010年のカナダ大会では、日本は金2、銀2の好成績を残しました。
JOI概要
日本は第6回IOIから3回続けて参加しましたが、バブル崩壊の煽りを受けて一度休止となっています。
その後JOI(日本情報オリンピック)は復活し、2006年のメキシコ大会から今まで毎回参加しています。
JOIでは予選・本選・合宿という一続きの選抜があり、合宿参加者から4名がIOIの日本代表として選ばれます。
例年合宿は3月下旬ごろにありますが、今年は延期になってしまい、4月の下旬と5月の上旬の2分割で開催されることになりました。
というわけで
長々と前置きしましたが、去年に続けて日本代表となることができました。
今年も試験と国際交流を頑張りたいと思います。あと苦手な辛い料理が出ても泣かないで頑張りたいと思います。
Permalink | コメント(1) | トラックバック(0) | 22:34 
2011-03-16
情報オリンピック合宿中止
まえがき
僕のいる地域は東京の隣にある多摩ニュータウンという地域で、地震の被害については交通機関のマヒ以外は無事でした。
震災にあっている人のために出来ることは限られているので、はてな経由で200ポイントだけ寄付したのち、元の生活に戻ろうということで、電力に配慮しつつ情報オリンピックの合宿の対策をしてきましたが、ここに来てやはり合宿は無理だということになりました。
合宿概要
JOIのかかわる合宿は春と夏の2つがあるが、ここで言うのは勿論春合宿である。
JOIの春合宿は2月に開催される本選の次のラウンドと位置づけられ、本選の成績優秀者が参加できる。
この合宿はJOIの一般的な活動の1つとして参加者の技術向上を図るトレーニング合宿であると同時に、その年のIOIへの日本代表4名を決める選抜合宿でもある。(というかこっちのほうが大事)
今回の合宿は2011/03/19から2011/03/25まで、代々木の国立オリンピック記念青少年総合センター
合宿のメイン行事は、4〜5時間かけて3〜4問を解くという競技日程を4日行うことであり、これは研修センターにてPCや競技用のサーバーなどを用意して行う。この成績によって日本代表を決定する予定であった。
事情
これはあくまで参加者側としての予測だが、最も大きな事情は、やはり電力事情だろう。4〜5時間ちゃんとシステムが稼働しなければならない。ノートPCのバッテリーやUPSなどを使えば稼働できないことはないかもしれないが、やはり万全の体制で臨めないのは辛いといえるだろう。
また関東に人を集めること自体に不安が残るというのも正しいだろう。(電力、交通、経済、治安、原子力など…1つ1つはごくごく些細な問題でも、やはり人を集めて何かを開催するのには厳しいものがあるだろう…)
代替
今回の連絡では、当たり前だが、予定されていた合宿は中止ということしか決定していない。しかし、IOIの日本代表4名は何らかの方法で決定しなければならない。
- 本選の成績を用いるという方法はこのさい妥当だと言えるだろう。
- 本来ならば、「代表は合宿で決定する」と予告されていた状態での本選であり、それを考慮した上での成績になっているはずだから、代表決定の指針としては不適当という指摘はできるだろう。
- また、本選の問題の傾向はIOIの傾向とは遠く、その点でも代表決定の指針としては不適当と言える。
- ただ、このような事態であることを踏まえた上では、妥当な選択肢に入っていると言えるだろう。
- オンラインコンテストの実施は交通事情や開催場所の問題を解決できるという利点がある。
- 時期を4月にずらすということも視野に入る。
- 4月に入っても相変わらず電力インフラは不安定なのではないだろうかという問題はある
- スケジュールの調整も問題になる。
- また会場の確保と競技環境の整備も難しいだろう。仮にこの方法で開催できたとしても、縮小運営になりそうである。寂しい。
- 関西など影響のない地域に移して開催するという方法も提案されている。
- この方法だとスケジュールの問題は生じない。
- 関東組としては新幹線の確保ができるかが心配である。
- 前項と同様に会場の確保と競技環境の整備は問題だろう。
ところで
ところで、合宿には岡本玲さんに来ていただけることになっていたようだが、これはもはや無理なのだろうか…せっかくなのでお目にかかりたいところだが。(しかしエンタメ事情に全く通じていないおかげで実は女優さんという以上の認識を持っていない)
まとめ
僕自身の意見というのは、まだ決まっていない。どの選択肢も微妙に欠点があるから、難しい。
ところで、僕が合宿に参加するのは、もちろんIOIに出るためだし、JOIの良質な問題を味わうためでもあるし、そして、JOI参加者の面子と机を囲んでだらだらとTwitterをするためであるのだ。合宿が仮に開催できたとしても、この3番目の愉しみは何かしら縮小される可能性が高いだろう。それはちょっと寂しいなあ。
Permalink | コメント(0) | トラックバック(0) | 17:39 
