🐢
[鉄則B30] Combination 2
nCr の計算より n r の決め方が難しいグリッド問題。
問題を要約する
- 右または下に移動できる
- 左上から右下まで移動できるのは何通りか？
考え方
最小マップで考える。
| 0 | 1 | |
|---|---|---|
| 0 | S | |
| 1 | G |
この場合 S から G までの移動するには、横に 1 歩移動する必要がある。同様に下にも 1 歩移動する必要がある。つまり 2 歩分の選択肢がある。したがって nCr の n は 2 とする。なお、この 2 は (W - 1) + (H - 1) に該当する。
しかし、ただの 2 歩ぶんだと「→→」「↓↓」の場合に G に辿りつけない。
| 1歩目 | 2歩目 | Goal |
|---|---|---|
| ↓ | → | ○ |
| → | → | |
| → | ↓ | ○ |
| ↓ | ↓ |
G に移動できる条件は「右にちょうど1歩」のときになる。言い換えると W - 1 のときなので nCr の r は W - 1 とする。「下にちょうど1歩」と考えて H - 1 とするのでもいい。
解説の W + H - 2 とは？
唐突に出てきたこの 2 が謎だったが縦横を分けて考えると理解できた。まず左端のマスから右端のマスまで移動するには横の「辺の数」だけ移動する必要があるため「横マスの数 - 1」になる。同様に縦は「縦マスの数 - 1」になる。その二つを足したのが (W - 1) + (H - 1) で、これを詰めて解説では W + H - 2 としている。
解説の模範解答風 (AC)
126 ms
H, W = gets.split.collect(&:to_i) # => [5, 10]
MOD = 1000000007
n = W.pred + H.pred # => 13
r = W.pred # => 9
# nCr = n! / (r! * (n - r)!)
a = n.downto(2).inject(1) { |a, e| (a * e).modulo(MOD) } # => 227020758
b = r.downto(2).inject(1) { |a, e| (a * e).modulo(MOD) } # => 362880
c = (n - r).downto(2).inject(1) { |a, e| (a * e).modulo(MOD) } # (n - r)!
d = (b * c).modulo(MOD) # r! * (n - r)!
x = (a * d.pow(MOD - 2, MOD)).modulo(MOD) # n! / r! * (n - r)!
p x # => 715
nCr の n r が決まればあとは前問と同じ実装でよい。また r = H.pred でも答えは同じになる。
Discussion