AtCoder Beginner Contest 24 D. 動的計画法

※このエントリは競プロで圧倒的成長 Advent Calendar 2015の12日目のエントリです．

問題

問題概要

• 方眼紙の左下のマスからあるマスへ移動する道のパターン数をDPで求めた
• A (あるマス)，B(Aの上のマス)，C(Cの上のマス)が与えられる
• Aは下から上に何マス(r)，下に何マス(c)進んだマスか

解法

• A, B, Cを数式であらわすと
  [latex]A={}_{r+c}\mathrm{C}_c=\frac{(r+c)!}{r!c!}[/latex]
  [latex]B={}_{r+c+1}\mathrm{C}_c=\frac{(r+c+1)!}{(r+1)!c!}[/latex]
  [latex]C={}_{r+c+1}\mathrm{C}_{c+1}=\frac{(r+c+1)!}{r!(c+1)!}[/latex]
  となる
• あとは変数を消してr=(A,B,Cの式)，c=(A,B,Cの式)とする
• タイトル詐欺過ぎ