コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 2025 (記事作成時点)
供養
解法
- $N \gt M + K$ のとき、自明に $0$
- $(x, y) = (0, 0)$ から $x = x + 1$ もしくは $y = y + 1$ を繰り返して $(M, N)$ に到達するパターン数を数える問題と同義
- 全パターン数は $_{N + M}\mathrm{C}_{N}$
- NGの経路パターンを以下のように考える
- $K = N$ のとき、NGとなる経路は存在しない
- NGのとき、少なくとも1回は直線 $y = x + K + 1$ に接触するような経路を通っている
- そのような経路において、$(0, 0)$ から接触した点 $(x, y)$ までの経路を直線 $y = x + K + 1$ について対象となるように描くと、必ず $(-K - 1, K + 1)$ から $(x, y)$ までの経路となる
- したがって、NGとなる経路は $(-K - 1, K + 1)$ から $(M, N)$ まで移動するパターン数 $_{N ＋M}\mathrm{C}_{N - K - 1}$ と同値
- 全パターン数からNGパターン数を引いた値が答え
実装
計算量は $O(N + M)$
公式解説
躓いた点
- $(0, 0)$ を直線で折り返して $(-K - 1, K + 1)$ に集約すればよいことに気が付かなかった
