読者です 読者をやめる 読者になる 読者になる

SRM425 Div2Medium - CrazyBot

問題概要
ランダムウォークするロボットがある。4方向に遷移確率が与えられるので、同じ場所を踏まずにN回ウォーキングを続けられる確率を求めよ。

解法
訪れた場所を **used で記録して遷移確率をかけながら状態を持って dfs するだけ。
EPSについての記述があるが、探索途中で確率が EPS = 1E-9 を下回ったからと言って安易に枝刈りすると落ちる。実際、ここで枝刈りせずとも 時間計算量が 最悪 4*(3^13) = 約600万(多分)なので TLE にはならない

反省
実装だけ考えればEasyレベルな気がする。
誤読や思い込みで、同じ場所を踏むように動くのかと思っていた。しかも与えられた整数Nを無視して何を目的としたコードかわからないを記述していて。サンプルが合わなくて困っていたが、合うわけがない。