読者です 読者をやめる 読者になる 読者になる

AOJ 2335: 10歳の動的計画 10-Year-Old Dynamic Programming

問題↓

10-Year-Old Dynamic Programming | Aizu Online Judge

問題概要

  • 格子があります。
  • 右と上しか進めません。
  • ただし、ちょうどK回だけ寄り道(左or下に行くこと)します。
  • (0,0) から (N,M) に辿る道は何通りあるでしょう。
  • (0,0)より左下には行くことができない(マイナスの座標へはいけない)

解法

  • nCk = ( n, k ) と書きます。
  • K回のうち、左に寄り道する回数をLとして下に寄り道する回数をRとします。
  • まず、左右の動きと上下の動きの2つに関して見ると
    ( N + M + 2*K, N + 2*L ) のコンビネーションで左右移動・上下移動の割り振り方の通りの数が求まります。
  • これに、左右の左・右の割り振り方、上下の上・下の割り振り方の通りの数をかければ答えが求まります。
  • kagamiz先生から snukeさんのブログのリンクとヒントを貰う
  • 左右の割り振り方の通りの数というのはその時の右に行った回数分だけしか左にいけないのでブログの図に対応する。

  • この式の意味が分からなかった解説も頂けた。
  • 天才か
  • ということで、
    左右の割り振り方: ( N + 2*L, L ) - ( N + 2*L , L-1 )
    上下の割り振り型: ( M + 2*R, R ) - ( M + 2*R , R-1 )
  • を掛けあわせればOK
  • これを各Lについて足し合わせたものが答え。
  • 階乗は予め計算しておいて、割り算はmod_invで答える。
 

感想

数え上げdpは500でさんざんやったが
こういう純粋な数え上げみたいなのが苦手だったので解けてよかった。

kagamizとsnukeさんに感謝。