国際情報オリンピック日本代表に選出されました

こんにちは、新しく部長になりました松崎です。2015年3月19日(木)から3月25日(水)にかけて開催された日本情報オリンピック春季トレーニング合宿に参加してきました。

情報オリンピック春季トレーニング合宿(通称JOI春合宿)は、国際情報オリンピック(通称IOI)の日本代表となる4名を決める合宿です。JOI本選参加者80名中Aランクの19名が参加しました。

春季トレーニング合宿と大変そうな名前ですが特に運動したりはしないです。問題をプログラミングで解きます。

合宿の内容について

day 1

この日は3時頃に受付し、実機練習(競技で使用するパソコンに慣れる)をした後、フローについての講義を受けました。

3時までは自由なので観光したり遊んだりできるのですが、無計画に渋谷に行ったら何もすることがなくて観光を満喫できませんでした。残念。

実機演習の問題は流石に簡単で全部満点。講義はネットワークフローに関してでした。競技プログラミングにおいては頻出ですがJOIではあまり馴染みがなかったのでためになりました。

day 2

この日から競技が始まります。競技時間は9時から14時の5時間と非常に長く大変です。これを4日間連続で行うので集中力や耐久力も試されます。

この日の問題は4問ありました。競技が始まった後、まず全体に目を通して2番が尺取り法でできることに気づきAC。

その後4番が表裏の境目がたった4つであること、a~b,b~cの反転がa~cと言った感じで結合できることに気づき、グラフに帰着してAC。

3番目はそこそこ難しくて、左から日光を浴びる場合と右からの場合で問題を分割したのち、頑張ってDPに帰着させてAC。

残る1番の問題に取りりかかりますが、数列に数列を持たせるような変な考えをしてハマってしまい、諦めて簡単だった部分点を取りました。

この日の点数は310/400でした。この時点で全体では満点が5名居たらしく、代表の枠が4名なのでかなり絶望していました。講義は昨日に引き続きネットワークフローに関してでした。

day 3

この日の問題は3問ありました。昨日と同様に全ての問題に目を通し、2番に可能性を感じたので考えていくと、普通にDPしようとするとある人が外出した後ある人が帰ってくるパターンが解決できずに困りましたが、変則的な順番にDPすることで解決してACできました。グラフに帰着せずにゴリ押したので少し実装が大変でした。

その後うまく読解できてなかった1番を冷静になって読んでみると、簡単に解ける事に気づきAC。

3番は木であることに気づいた後は適当に木に関するアルゴリズムを試しまくったらなんとかなりました。唯一道路の整備の処理に困りましたが、分割統治法で解決。200行近くにも及ぶコードを書いてAC。

この日の点数は300/300で満点でした。全体では2日連続満点が3人で、ギリギリ4位に滑り込める可能性が出てきて希望の光が見えてきました。講義は数え上げ入門でしたが、入門とは思えない難しさでした。

day 4

この日も3問で、1問応答型課題がありました。まずカードゲーマーなのも相まって2番を考察していくと、前から3枚と山札の一番上を記憶するDPを思いつきましたが、このままでは満点が取れないのでもっと考察していくと前から3枚目のカードは2枚目か山札の一番上のカードのどちらかの次である事に気づきAC。無駄な場合分けをしたせいでメモリ制限を超えてしまい、int型からbool型にして累積和を取ったりしてました。

その後過去の傾向から応答型課題はそこまで難しくないと踏んで道案内に挑戦しました。部分点は全て取れて、番号の高低を利用するところまで思いついたものの、辺に方向を付ける発想が出ずに、長いこと考えるも解けず。最後に1番の部分点を取ろうとするもバグってしまい0点。実装の負担を軽減するために部分点は解法だけ考えて実装を後回しにする戦略を取っていましたが、ここだけは裏目に出てしまいました。

この日の点数は145/300でした。自分と得点が近い人も同程度の点数だったようで決着は明日に持ち越す形となりました。この時自分は推定4位で5位の人とは10点差だったので、結構動揺していました。講義は機械学習についてでした。

day 5

いよいよ競技最終日。昨日と同様3問で応答型課題が1問ありました。まず1番を少し読むと鉄道が木になることから最大全域木を作ってやればいいことに気づきAC。誰に辺を渡すかを二分探索できるか微妙でしたが、自分の直感を信じて書いたら通って一安心しました。

次に2番をさらっと読むと、小課題5が<をストックしている数と今調べている場所を覚えるだけだとすぐにわかりました。5点は順位に影響しないと踏んで小課題3について考えると、かっこの左側(<,[)のストックしている数とその種類と調べている場所を覚えればいいとわかりました。実装が難解で手こずるもののなんとか部分点獲得。15000日電子メールを送れることをうまく活用できないかなぁと思ったりもしました。

その後一度2番を諦め3番を考えるも小課題1しか思いつかずに焦りました。小課題2が解ければちょっと場合分けすれば満点取れそうなので満点狙うも頭が混乱してきて断念。諦めて小課題2を狙うも微妙にうまくいかず。気分転換に2に戻ってみるとSを「いい文字列であるかどうか」ではなく「いい文字列ではないかどうか」を考えてみるといけそうな事に気づき2番を頑張ることに。それぞれのかっこに対応するかっこを探せばいいことに気づきAC。

3番に戻るも最後までわからずに終了。部分点で終わりました。

最終日の得点は210/300で、総得点は965/1300でした。講習はSATソルバー入門で、SATソルバーすげえええって思ってました。

day 6

競技も終わり、この日はJ言語コンテストと表彰式がありました。まるで古代文明の文章みたいなコードを解読するコンテストで、楽しかったです。

表彰式。日本代表に選ばれました。ありがとうございました。

day 7

アンケートを書いて解散。合宿中に仲良くなった人々と共に秋葉原を観光。とても楽しかったです。オリセン脱出からの解放感と、合宿が終わる名残惜しさと共に帰路につきました。

最後に

国際情報オリンピック金メダル目指して頑張ります。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です