SRM418 Div2 1000

問題

戦略ゲームで、敵の兵士とタワーを壊すことを考える。最初、味方の兵士はmyUnits人いて、敵の兵士は0人である。各ターンで、味方の兵士は敵の兵士またはタワーを攻撃することができる。倒せなかった場合、敵の兵士は味方の兵士を攻撃する。タワーはunitsPerRound人敵の兵士を生み出す。このタワーのHPはbarHpで与えられる時、相手のタワーと兵士を倒すまでの最小ターン数を返す。もし無理な場合は-1を返す。

考え方

味方の兵士数、敵の兵士数、タワーのHPを状態にBFSする。
もし味方の兵士数が「敵の兵士数+タワーのHP」以上の場合、そのターンで倒すことができるので、それを返す。それ以外の場合はi人タワーのHPを削って、(その時の兵士数-i)人が敵の兵士を倒した状態としてキューに入れる。
また、同じ状態が繰り返される場合のために、メモ化して、同じ状態が出てきた場合は計算しないようにする。もし見つかればそれが答え。見つからなければ-1。

反省

メモ付き再帰かDPでも解ける。
メモはbool memo[]でよかった。(map使う必要ない)