茶色コーダーが青Diff解いてみました！
AtCoderのレートが539な私ですが、教えてもらいながら青Diffの問題を解くことができたので、記事を書いてみました！
優しく丁寧に説明しようと思っているので、まどろっこしかったらごめんなさい><
今回解いた問題は、AtCoder Beginner Contest 042D-いろはちゃんとマス目です。
私の提出リンク
最初の発想
まず、この問題を見た時に「とあるマスからとあるマスまでの最短経路の総数を求める」という問題に見えました。
高校数学の組み合わせのところで出てきた問題に似ているので、コンビネーションを使うのではないかと考えました。
（リンク先の問題では、コンビネーションは使っていませんが、模範解答の数式（階乗を階乗で割っているやつ）を式変形するとコンビネーションになります。）
高校数学の復習を少しします。
図のような縦3横4の格子状の道路があって、左上から右下まで行く最短経路の総数を調べます。
最短経路の長さは7で、7のうち3回下へ進まなければならないので、7C3で求められます。
（同様に、７のうち4回右へ進まなければならないと考えて7C4と計算しても同じ結果が得られます。）
では、次に、×をつけたところが通れない場合はどうでしょうか。
この場合は、余事象を利用します。つまり、上で求めた最短経路の総数から必ず×を通る最短経路の数を引けばいいです。
必ず×を通る最短経路は、（AからBまでの最短経路の総数）×（BからCまでの最短経路の総数）×（CからDまでの最短経路の総数）で求めることができ、これは2C1×1C1×4C2で表せます。参考
それでは、元のいろはちゃんとマス目の問題に戻ります。
しかし、今回は通れない場所があるので、それについて考えないといけません。
困ったので、とりあえず入力例を見ながら絵を描いてみることにしました。
入力例1を描いてみたのですが小さすぎて考えにくかったので、入力例2で描いてみます。
まずはマス目を用意しました。斜線部は通れません。
最短経路のうちのいくつかを描き込んでみました。
最初は通れない部分があるから、高校数学のように余事象で考えようと思ったのですが、通れない範囲が広いので、余事象を求めるのが大変そうだと思いました。
そこで、素直に斜線部を通らない最短経路の個数を求めます。
左上から右下までの経路を2つに分けます。
そうすると、図のように、緑の分け方、ピンクの分け方、...、青の分け方となります。
ちょっと分かりにくいと思う（私はそうだった）ので、緑とピンクの分け方の時の最短経路の一例を描き込んでみます。
それぞれの分け方は排反なので、それぞれを求めてから足してあげれば良さそうです。
実装の問題1
この問題を実装しようとすると、コンビネーションの両側の数字がぐちゃぐちゃしてややこしく感じました。
そこで、丁寧に入力例2の答えを求める式を書き出していきます。
この時、最初に挙げた高校数学と違って、最初にいろはちゃんがいるのは点ではなく、マスなことに注意してください。
コンビネーションの両端の数字について規則性を探してみると、下の方に矢印で書いてあるような規則性が見つけられると思います。（ここでのiはfor文で動かしていく数字です。）
ここの部分だけ実装してみます。
コンビネーションの実装はあとで述べるので、とりあえずcmb(コンビネーションの左側の数字,右側の数字)でコンビネーションを求められるものとします。
for i in range(h - a):
ans += (cmb(b - 1 + i, i) * cmb(w - b - 1 + h - i - 1, w - b - 1))
for文の回す範囲がh-a未満であることにも注意してください。
実装の問題2
コンビネーションは、冒頭で少し触れたように、階乗の割り算で表すことができます。
階乗を使って実装しようと思って実装してみるとわかるのですが、TLEします（たぶん）。
だいたい、組み合わせの総数を求める問題で、「10^9+7で割ったあまりを出力」と書かれているときは、普通に計算するとTLEしてしまいます。
そこで、逆元を使って高速化するのですが、それの考え方が難しいです。
そのため、私はテンプレートとして用意しておいて、必要な時にコピペすることで対応しています。
#コンビネーション
def cmb(n, r):
if (r < 0) or (n < r):
return 0
r = min(r, n - r)
return fact[n] * factinv[r] * factinv[n-r] % mod
N = 110 # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1] # factinv 計算用
for i in range(2, N + 1):
fact.append((fact[-1] * i) % mod)
inv.append((-inv[mod % i] * (mod // i)) % mod)
factinv.append((factinv[-1] * inv[-1]) % mod)
cmbの1つ目の引数はコンビネーションの左側の数字、2つ目の引数は右側の数字です。
使用上の注意なのですが、N=110となっていますが、必要な数に自分で変えて使ってください。
今回は、最悪でh+w個の中からr個選ぶことがあるので、ちょっと余裕をみてN=200000+1000くらい用意しておきます。
それ以外はコピペをしておけばOKです。
最終的なコードは以下のようになります。
#コンビネーション
def cmb(n, r):
if (r < 0) or (n < r):
return 0
r = min(r, n - r)
return fact[n] * factinv[r] * factinv[n-r] % mod
N = 2 * 10 ** 5 + 1000 # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1] # factinv 計算用
for i in range(2, N + 1):
fact.append((fact[-1] * i) % mod)
inv.append((-inv[mod % i] * (mod // i)) % mod)
factinv.append((factinv[-1] * inv[-1]) % mod)
h, w, a, b = map(int,input().split())
ans = 0
for i in range(h - a):
ans += (cmb(b - 1 + i, i) * cmb(w - b - 1 + h - i - 1, w - b - 1)) % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))
おしまい
初めて書くので、誤字とか間違えている部分とかがあれば教えてください！