AtCoder Beginner Contest 011 - D
- 座標(0,0)と座標(X,Y)をそれぞれスタート地点、ゴール地点とする
- スタート地点から出発してN回移動できる
- 移動は上下左右に1だけ動ける
- 上下左右どこに動くかは1/4の確率で決まる
ちょうどN回でスタート地点からゴール地点まで行ける確率を求める
解説の解説
どうやってN回でスタート地点からゴール地点まで行ける確率を数え上げるか？（解説に沿って）
解説に沿った数え上げの道筋
- 確率を求めるので、求める場合の数 / すべての場合の数 を考えれば
- すべての場合の数
- N=1で上下左右4通りあるので、すべての場合の数は4^N になるはず
- すべての場合の数
- 求める場合の数
- N = 1000, X = 10, Y = 20のとき、左右に動くのを600で固定する
- すると、X = 10から 左に動くのは295回、右に動くのは305回 と決まる（{600+10}÷2） ... ※１
- 求める場合の数は
... ①
- 上下に動くのは 1000 - 600 = 400となる、そこから
- 求める場合の数は
（{400+20}÷2）... ②
- ① x ② = 左右に動く回数がK回のときの場合の数
- ここまでの手順を N := 1 〜 N まで試し、足しあげればよい
- ※１
- ここがなぜ確定するか疑問だったのだが、例えば N = 30, X = 10 とすれば
- 目一杯左に移動したとしても、<- 10、 -> 10、 -> 10 と移動する他なく、右が20で確定する
どうやってN回でスタート地点からゴール地点まで行ける確率を数え上げるか？（参考サイトに従う）
- 参考サイトの式は、
- (1/4)^N * Comb(N, up+down) * Comb(up+down, up) * Comb(right+left, right)
つまり
最短経路の場合の数 × 上下の選択できる場合の数 × 左右の選択できる場合の数 / すべての場合の数4^N
固定した各場合において最短経路で到達できる場合の数を求め、縦と横の移動で後戻りが可能である場合をかけ合わせることで全体の場合の数を求めている。
かなりしっくりくる
abc011-1.png
abc011-2.png