IOI 2008 day1

100 - 100 - 80 = 280

A - Type Printer

ソートしてから全て繋げればいいという考察をしたが、一番最後の単語は消さなくてもいいのではこれは間違いだった。しかしこの考察はかなり利用出来て、最後に来る単語の先頭の文字を 26 通り探索して再帰するという方法でこの問題を解くことが出来る。実装に割と手間取ってしまった。

B - Islands

諸悪の根源。考察はほぼ自明であり、サイクルを通る経路と木の内部だけで終わる経路の max の総和を取ればよい。後者を忘れてしまい時間ロスをしてしまった。しかしこの問題は 10^6 制約かつ 128 Mib 制限である。なので再帰を queue を使ったり配列を使いまわしたりすることを繰り返しなんとか 100 点を得る。この制約に設定した人は何を考えていたのだろうかとただただ疑問である。

C - Fish

まさかの数え上げだが、mod が合成数かつ 3 * 10^4 以下というなんとも嫌な見た目。考察はこれも IOI にしては簡単目であり、それぞれの宝石を持つ最大の魚を取る場合のみ考えればよく、更にその場合もその魚の持つ種類の宝石を全て取るか、その魚より大きい魚の持つ種類の宝石を 1 個も取らないかという 2 通りを考えればよい。とりあえず k <= 20 制約を実装する。ここから modint を実装して平面操作を書き、そしてセグ木や二分探索を用いて高速化していき時間制限ギリギリでなんとか 80 点を得る。TLE しているケースがあったので高速化して 85 点。ここでまた 5 * 10^5 制約かつ 64 Mib 制限という制約に満点を阻まれる。時間が足りずメモリ節約の目途も立たずに時間切れ。昔の IOI はメモリ制限を厳しくしようという動きが全体的に多かったのだろうか？MLE 対策は今まであまりしてこなかったのでかなりやりづらい。

感想

ただただメモリが苦しかった。