1. 問題

p986.jpg

上記のグラフにおいて、左のほうでは、高さ3でのピークが2、高さ2でのピークが2である。右のほうでは、高さ1, 2, 3でのピークはそれぞれ1である。
 グラフでは、パスは原点(0,0)から出発し、ステップ(1,1)と(1,-1)に沿って右へ移動し、最終的に(2n,0)にもどる。パスはx軸を切って下に移動することはない。
 n (1<=n<20)、および高さk (1<=k<20) でのピーク数がちょうどr (0<=r<20) であるパスの数を示せ。

2. 計算法
 本問題もDPによる方法を考える。
 高さkのところのピース数がrであるパスが右上がり(つまりステップ(1,1))で (x,y) に来た時の数を c[x][y][r][k][1] とし、右下がり(ステップ(1,-1))のパス数を c[x][y][r][k][0] とする。
 配列の大きさは c[40][21][21][20][2] になる。
 初期値 c[1][1][0][k][1] = 1 (1<=k<20)、他の要素はゼロ。
 漸化式は以下の通り。

for (x = 2; x < 40; x++) {
for (r = 0; r < 20; r++) {
for (k = 1; k < 20; k++) /* x軸上に来たパスに対し */
c[x][1][r][k][1] += c[x-1][0][r][k][0];
for (y = 1; y < 20; y++) {
for (k = 1; k < y; k++)
c[x][y-1][r][k][0] += c[x-1][y][r][k][1];
c[x][y-1][r+1][y][0] += c[x-1][y][r][k][1];
for (k = y+1; k < 20; k++)
c[x][y-1][r][k][0] += c[x-1][y][r][k][1];
for (k = 1; k < 20; k++) {
c[x][y-1][r][k][0] += c[x-1][y][r][k][0];
c[x][y+1][r][k][1] += c[x-1][y][r][k][0];
c[x][y+1][r][k][1] += c[x-1][y][r][k][1];
}
}
}
}

入力の値n, r, kに対する答えは c[n+n][0][r][k][0] である。

3. 検証用入出力データ

19 19 1
19 9 0
19 9 1
19 9 2
19 9 3
19 9 4
19 9 5
19 9 6
19 9 7
19 9 8
19 9 9
19 9 10
19 9 11
6 2 2
6 3 2
6 1 1
6 2 1
6 3 1
1
0286572
2466750
2413917
1024608
318921
81628
17003
2772
332
26
1
28
14
40
21
8

4. 感想
 DPの表現式(配列)をちゃんとつくっておけば、複雑な問題ではなさそう。

Comments are closed.

Post Navigation