方向音痴

$\mathrm{dp}[i][j]$ を、 $i$ 分時点で街 $j$ にいる確率と定義した動的計画法で解くことが出来ます。