TCO 2011 Qual2 Div1 500(ニコ生オープン)

とぷこだ 過去問

いい問題。

問題

通路の左端にいる。右端に行きたい。通路の各マスには、「なにもなし」「やさしいクリーチャー」「危険なクリーチャー」がありえる。
もしクリーチャーがいるとき、は時刻tによって入れるかどうかが決まる。

  • 入ろうとするマスにやさしいクリーチャがいるとき、時刻tがKで割り切れるならば機嫌が悪く通ることができない。それ以外なら通れる。
  • 入ろうとするマスに危険なクリーチャがいるときは、時刻tがCで割り切れるならば、具合が悪いので通ることができる。それ以外なら通れない。

時刻は1から始まるとき、右端に行くことができる最短の時刻を返す。行けないなら-1。

考え方

メモ化BFS。
各状態で、「左」「そのまま」「右」の動作ができるので、「位置」と「時刻」を状態にもってBFSする。
位置と時刻をメモするが、この時刻は実は適当にとってはいけない。
「.CKC.」みたいな並びの時、通り抜けるのに結構時間がかかる(けど通れる)。
KとCについて、lcm(K,C)以上の時間では各クリーチャーの変わり方は繰り返しになるので、MOD=lcm(K,C)でメモ化すればいい。

反省

最大ケースが思いつけず、メモの最大時間を3000とかしたため落ちた。lcmで繰り返しは気付いていたけど、それを使わず適当に最大時間を見積もってしまったのが×。
「何回以上かかるなら打ち切り」というやり方は危険だとわかった。