問題概要

正の整数 $r_{1}, r_{2}, c_{1}, c_{2}$ が与えられる.

$f(x, y)$ を 2次元グリッド上の $(0, 0) \rightarrow (x, y)$ への最短経路の経路数とする. $f(x, y) = 0$ ( $x \lt 0$ or $y \lt 0$ のとき) このとき,

$\displaystyle{ \sum_{r_{1} \leq x \leq r_{2} } \sum_{c_{1} \leq y \leq c_{2}} f(x, y) }$

を求めよ.

atcoder.jp

個人的解法

基本的数学知識(数A程度) から明らかに, $f(x, y) = {}_{x + y} C_{y}$ であるが, その前に得られる自明な漸化式

$f(x, y) = f(x-1, y) + f(x, y-1)$

に注目して議論を行うことにする. (ただし, $x = y = 0$ のときの式であり, $f(0, 0) = 1$ とする.)

元の問題は, 2次元グリッド上の値と見ればの長方形型の値を求める問題とみなすとき, この問題は累積和を求めることと同値である. (累積和は部分問題であるし, 累積和を使って2次元累積和の基本的な使い方をすれば求められる.)
したがって, 二次元累積和 $\displaystyle{ S(a, b) := \sum_{0 \leq x \leq a} \sum_{0 \leq y \leq b} f(x, y) }$ を考えることにする.
すると, このとき, 上の $f$ に関する漸化式から次の関係式が成り立つ (+1の部分は $f(0, 0)$ の寄与分)

$S(a, b) = S(a, b-1) + S(a-1, b) + 1$

この式は線形っぽいが, 定数が扱いにくいので, $T(a, b) = S(a, b) + g(a) + g(b)$ の形であって $T(a, b) = T(a, b-1) + T(a-1, b)$ の形になる関数 $g$ があれば嬉しい. 所望の $T$ の関係式に, $T$ の定義式を代入すると

$S(a, b) + g(a) +g(b) = S(a, b-1) + g(a) + g(b-1) + S(a-1, b) + g(a-1) + g(b)$

Sの関係式を用いることで

$g(a-1) + g(b-1) = 1$

より, $T(a, b) = S(a, b) + 1$ とおくと嬉しいのではないかという予想がつく.

このとき, $T(a, b) = T(a, b-1) + T(a-1, b)$ および $T(a, 0) = a + 1, T(0, b) = b + 1$ が成り立っているが, $T(a, b) = f(a+1, b+1)$ となっていることがわかる. (パスカルの三角形を考えたら明らか ; 初項が1ずれているだけと思えば簡単)

したがって, 求める答えは

$\begin{aligned} (\text{答え}) &= S(r_{2}, c_{2}) - S(r_{2}, c_{1}-1) - S(r_{1}-1, c_{2}) + S(r_{1}-1, c_{1}-1) \\ &= ( T(r_{2}, c_{2}) - 1 ) - ( T(r_{2}, c_{1}-1) - 1 ) - ( T(r_{1}-1, c_{2}) - 1 ) + ( T(r_{1} -1, c_{1} - 1) - 1 )\\ &= T(r_{2}, c_{2}) - T(r_{2}, c_{1} - 1) - T(r_{1} - 1, c_{2}) + T(r_{1} - 1, c_{1} - 1)\\ &= f(r_{2} + 1, c_{2} + 1) - f(r_{2} + 1, c_{1}) - f(r_{1}, c_{2} + 1) + f(r_{1}, c_{1}) \\ \end{aligned}$