IOI 2007 day1

100 - 100 - 100 = 300

A - Aliens

まず M <= 100 の部分点を取りに行こうとする。

5 * 5 の形で M * M の盤面が作られるが正しいが、M * M の形で M * M の盤面が作られると誤読してしまって 30 分程を溶かす。

なんとか気付いて 40 点を得る。その後、上限を 2 倍にしていく二分探索を用いて 100 点。

B - Flood

とりあえず各連結成分を持つことが出来れば解けそうだが、状態を良い感じに圧縮する方法が思いつかない。色々考えるも結局思いつかず C に向かう。

C - Sails

とりあえず柱の長さでソートをする。ここで、今最も帆が少ない K 個に追加するとよいのではないか？となる。証明を行う。そしてこれをシミュレーションしようとする。遅延セグ木を用いれば一応出来るが、こういうものは set 系で処理できることを思い出す。実際に今回も可能であり、割と複雑な動きに頭をバグらせながらもなんとか 1 発 AC を取る。

B - Flood

グラフを良い感じに構成する手段として、まず全ての横の線を縦の線にぶつからない限り伸ばし、その次に全ての縦の線を横の線にぶつからない限り伸ばし、出来た長方形領域を 1 個の成分としてみて、UnionFind でマージする。が思いつく。しかし、かなり実装が重い(セグ木に set を乗せて二分探索が必要となった)上、そもそもこの方法で連結成分の個数が抑えられるかすら分からない。今考えると点の個数が点の個数 + 4 * 線分の個数で抑えらえるので一応 ok である。ここで方針転換をしてシミュレーションを考える。今外側の線分を取ろうとしたとき、一番 x 座標が小さい(複数あるならばその中で y 座標が小さい)点から初めて線分を前回の線分に対して出来るだけ外側に行くように取っていき、往復した線分達が壊れない壁である。という動きをしそうでありこれならば軽そうなので実装をする。バグらせたり MLE したりするが、修正して 100 点を取る。

感想

C で遅延セグ木を書かずに multiset で処理出来たのはよいが、B での方向転換の遅さと A での誤読が痛すぎる。