GCJ Round2
参加してきました。してきましたが、問題読んだ時点で D-small 以外はどれも解ける気がしなかったりしてわりと残念でした。ちなみに D-small は問題をちゃんと読んだ人なら誰でも解けたんじゃないかと思うくらい簡単。*1
最初 20 分
とりあえず ABCD の順番に全部問題読む。ちょっと考える。
A はなんかよくわからないので small だけ BFS で全探索してみようかと思ったけど
11111111 11111110 11111100 11111000 11110000 11100000 11000000 10000000
こんなんが出てきたらたぶん終わらないなーと思ってパス。
B は small だけなら BFS でできるかなー、と思ったので、他に解くものがなければやってみるつもりでとりあえず保留。
C はグラフを作って極大クリークでの被覆を考えれば解けるなーと思ったけど時間内にそんなものを書けるかどうかは怪しい。*2
D-small は N <= 3 なので、一つの円で二つを覆えばいい。簡単なのですぐ解く。large はよくわからないので放置。
で、解けそうなのが C-small か B-small なのだけどとりあえず BFS やってみるという方針があったので B 狙いにすることに。
それ以降
D-small 通した後はほとんど B 解いてました。しかし、この問題めんどくさすぎました。紙の上でもう少しきちんと整理してからキーボードに向かったほうがよかったのかもしれませんが。
しかも残念なことに、単純な BFS だと small input 上限の R = 10, C = 6 が終わりませんでした。こういうの。
...... ###### ###### ###### ###### ###### ###### ###### ###### ######
それに気付いたのが残り 20 分ぐらいのときだったので、まあしょうがないなーという感じで残りの時間はわりとぼーっとしてたような気がします。
