ミリマス4周年記念PVを見た（2回目）。あれを見るたびに定期的に見なければならないという思いにさせられる。完全にまどマギの影に隠れてしまった密かな名作と評されるアニメ『THE IDOLM@STER』も見る時期が来たのかもしれない。
AOJ 2847 Ninja Map
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2847
解の条件がゆるゆるなのでテキトーに全探索して上から埋めていけばいけそうと予想して提出→AC。なぜそれでいけるかは分からん。
実装が複雑ではないがややこしくめんどくさい。一応タイプ量を減らすために辺の管理にsetを使ったが、それでも150行くらいになった。うまくやれば相当縮むと思うので、プロはどう書くのか気になる。
しかしこの忍者、やることがあまりにみみっちい。
AOJ 2781 Help the Princess!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2781
めちゃめちゃ苦労したし挫折しかけたがテストケースにらみつけながらhackして何とか自力。
何人いるか分からん兵士がむちゃくちゃに動き回るので、やりにくいったらありゃしない。 兵士がどのように動いても脱出できるか？ をこの問題では問うているので、兵士は一度に全員が全方向に移動する（留まる）としても良い。 こう考えると、兵士ひとりひとりの移動を考えてたらどうあがいても詰みなので、兵士をひとかたまりのスライム状のモンスターと考えて、これが時間が経過するごとに規則にしたがってだんだんと勢力を伸ばしていくと言い換えられる。これは全探索で配列上で管理できるので、あとはこの上の安全なゾーンだけを通って姫が脱出できるかをBFSで調べれば良い。全探索パートで力を使い果たしてBFSをおろそかにしないように注意（n敗。当たり前だけどループ回避用のフラグはいります）。
この方法だと兵士の数が多いとTLEするので、全探索をどこまで行うかに気を配る必要がある。最大ケースは200*200の迷路に兵士が1人だけいる場合だが、これが何ターン使えば全領域を埋められるのか分からなかった。テストケースを見ながら検証していたところ、1000回までは減らしても大丈夫なことが分かり、それで出したらAC。よくわからん。（実際のコンテストで出たらパラメータを微妙に変えながら10回ぐらい投げると思います）
たまにあるこういう問題が辛い。editorial調べたら想定多始点BFSだった。完全に地雷
