JOI春合宿に行ってきました

日本情報オリンピック春合宿に行ってきました。

結果から言うと、日本代表に選ばれて、カナダ・ウォータールーで開かれる国際情報オリンピックに出場することになりました。

以下、問題のまとめ

問題文はこちら→ http://www.ioi-jp.org/camp/2010/2010-sp-tasks/index.html

Day1

JOIポスター

やるだけ。
デバッグでN=20を試してしまい、O(2^n)の恐ろしさを知るなど。
ちなみに、本物のJOIロゴの右下は空欄になっている。

戦国時代

片側尺取メソッド（？）。
奇数偶数、上下左右を一つのループ内でまとめて処理しようとしてちょっと実装にてこずる。

階段

超人的な人シリーズ（ジャンプ出来る高さ）。
ＤＰ。
「階段 and 場合の数」でＤＰで無い場合はあるんだろうか？

Day2

a+bProblem

やるだけその２。
同じ数の連続をまとめたり、一番上の桁の処理がちょっと面倒だった。

DNA

Greedy＋Trie。
Greedyであることに気付かず、O(長さ×素DNAの長さ＾２）のＤＰをして５０％。
本戦５番もだけど、Greedyはなんだか苦手だ…

Regions

二分探索。
@semiexpがSegmentTree萌えなのと同様に、僕は二分探索萌えである。
木の奥から順番に計算していくので再帰が必要。
残念ながら僕は再帰はあまり好きではない。
BFS可愛いよBFS。

Day3

本戦会場

クラスカル。
短い辺から順番に追加していってUnion-findすればいいというのは知っていて、名前を知らなかったので「Union-findのアレ」と呼んでいた。
クラスカル、ちぃ覚えた。

かくれんぼ

SegmentTreeたん。
解けた人≒StarrySkyを解いていた人という過去問ゲーだった。
僕はStarrySkyを解いていなかったけれど、Day0に解法を話し合ってた会話を眺めてたのと、Day1の講義の演習でたまたまK-thNumber（SegmentTreeを使う）を解こうとしていたのが幸いだった。
SegmentTreeを「StarrySky木」と個人的に呼ぼうと思うのだが、いかがでしょう。

シムロード

Output-Only。
とりあえず各都市間のマンハッタン距離を求めてクラスカル法を使う。
そこからいい改良法が思いつかなかったのでそのままsubmitしたら意外と７割ぐらい取れた。
ラッキー。

Day4

コンテスト

やるだけその３。
やるだけシリーズの難易度の順番はいろいろな説があるが、僕はContest＜JOIPoster＜a+bProblemだと思う。

湖

ＤＰ。
初めは思いつかなかったが、高速道路が実装ゲーすぎて嫌になったので湖に戻ってきたところ、円を切って伸ばして直線にするというアイデアが出たので解けた。
ちょっと馬鹿な事をしていたので実装が重くなって、しばらくバグに苦しんでいた。

高速道路

ボス問。
LCA(最近共通祖先）とかRMQ(RangeMinimumQuery)とか色々あってウンザリする。
初めは経路圧縮してその分をBITで持てば高さが高々O(logn)になるから行けるかなと思った。
実際はこの解法は「親が子を２つ持っていて、その子の片方だけが子を二つ持っていて、その子の片方だけが…」という木を考えると高さがN/2にしかならないのでTLEする（その日の就寝時に気づいた）。
とりあえず実装ゲーなので諦めて５０％を取ったが、結果的にラッキーだった。

プラグ

○×の表に追加される長方形の辺をソートしておき、順番に見て端点に＋１、−１を追加して行きながら表を埋める。
クエリが全部処理できたらあとはやるだけ。解説で@imosさんがやっていた方法に感動した。
残念ながらそのアルゴリズムの名前が思い出せない。
超人的な人シリーズ２（クエリの数×プラグの数＾２回実験した店長）。

こんな感じで、300+250+276+350=1176点でした。
問題の事以外にもいろいろ書きたいことはあるけれど、書き疲れたので一旦ここでsubmit。