Ritsumeikan University Programming Contest 2013 (AOJ 2507) Computer Onesan

お題箱より。

解法

実は過去の解説記事に類題があります。

Codeforcesの問題は最大化でAOJの問題は数え上げという違いはありますが、解法はほぼ同じです。

左上から右下に向かう経路において、もし下から上に引き返せないというルールであれば、上から動的計画法で経路数を求めていくことができます。 $M=1$ の場合と $M=2$ の場合をそれぞれ考えます。

$M=1$ のとき縦の辺は2列あり、一度下から上に引き返してしまうとゴールすることができません。そのため引き返すことを考慮せずに動的計画法で答えを求めることができます。

あるいは縦の辺を1本通るたびに、どちらの列を通るかの2通りから選べるので、答えを $2^{N}$ と直接求めることもできます。

$M=2$ のとき縦の辺は3列あり、下から上に引き返す経路を考慮する必要があります。そのため下から引き返してきて、また下に進むコの字型の経路を予め作っておくことで動的計画法を用いることができます。

f:id:betrue12:20210606125911p:plain

コの字型の経路は高々1本で、スタートから伸びている列以外の2列がコの字になっている場合に限られます。このことから次のように動的計画法の状態を定義することができます。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack =$ スタート地点から縦の辺 $i$ 本分だけ下に進んでいて、スタート地点から伸びている経路が $j$ 列目にあって、残りの2列がコの字型に伸びてきている（ $k=1$ ）/いない（ $k=0$ ）ような経路数