288.1

やり直し。

1000

DPで解くことも、ステートの取り方も、ステート遷移の式も問題なかったのだけれど、探索の方向と初期値の設定がまずかったっぽい。最初の状態の確率を1.0として、一番確率の高い終了状態を求めようとすると、残存兵力のすべての可能性とそれに応じた確率のベクトルを保持する必要があるけれど、逆に、終了状態のすべての残存兵力について、勝利している可能性を1.0とすれば、状態と残存兵力について考えるだけで良くなる。

確率の問題は大抵がDPになるはずなので、今までに解けなかった問題も、実は探索の方向が間違っていたのかも知れない。特に初期状態の確率を1.0にしてから探索を始めるような気がするので、終了状態の確率を1.0にしてからやるべきかも。この辺りはループを0から回すか最大値から逆に回すかとかにも通じるところがあるし、何事も両面からとらえるのは重要ってことなんだろうなぁ。