AOJ 2335: １０歳の動的計画 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とします。
• まず、左右の動きと上下の動きの２つに関して見ると
  ( N + M + 2*K, N + 2*L ) のコンビネーションで左右移動・上下移動の割り振り方の通りの数が求まります。
• これに、左右の左・右の割り振り方、上下の上・下の割り振り方の通りの数をかければ答えが求まります。
• kagamiz先生から snukeさんのブログのリンクとヒントを貰う

• @public_sate ヒントになりそうな奴 → https://t.co/UgESgEke9i

  — Jayson Sho Toma (@kagamiz) 2016年6月13日

• 左右の割り振り方の通りの数というのはその時の右に行った回数分だけしか左にいけないのでブログの図に対応する。

• この式の意味が分からなかった解説も頂けた。

• @public_sate 縦がa-1, 横がb+1の盤面を、図の赤線の位置で折り返した移動を考えてみると「縦a,横bの長さでオレンジを通って辿るもの」と一対一の対応がついていて嬉しい感じなる(図の青の経路と緑の経路みたいな感じ) pic.twitter.com/vpufjOFWJe

  — Jayson Sho Toma (@kagamiz) 2016年6月14日

• 天才か
• ということで、
  左右の割り振り方: ( 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さんに感謝。