京大入試を題材に動的計画法を解説する

　こんにちは。東進衛星予備校　金沢南校の北川です。

　本日は入試問題を1つ取り上げて解説するとともに、この問題を解く「手順」の応用性について面白さを見ていきましょう。

　今回の問題はこちら。

　どうでしょうか。見た目は結構簡単ですし、言っていることもそれほど大変ではないです。

　「1段昇る」、もしくは「（1段飛ばして）2段昇る」のどちらかを選んで15段の階段を昇ります。ただし、2回連続で「2段昇る」を選択できないとします。

　例えば、1段→2段→1段→1段→2段→1段→2段→1段→1段→1段→2段という昇り方はこの条件を満たして15段昇っています。

　こういう昇り方は、全部で何通りあり得ますか？ という問題です。

　さて、では考えていきましょう。

1.見た目は猫、難易度はライオン

　入試問題には色々な格言（という名の有象無象の放言）があるのですが、その中でよく言われるものが「問題文が短い問題ほど難しい」というものです。

　これが一般に正しいかはさておき、この問題には当てはまりそうな気がします。実際、15段の昇り方はちょっと考えるだけでもたくさん見つかります。

　パッと書くだけでもこんな感じ。もっとたくさんあるのが分かると思います。

　ただ単に列挙していくのはどうやら得策ではないようです。

　この類の問題に対して洞察を得るには、少し少ない段数で考えてみるのがポイントです。

　例えば、4段を上りきる方法は何通りあるでしょうか？ 4段くらいだったら全部列挙できそうじゃないですか？

　この4通りで全部になりそうです（2段→2段は連続2段になってしまうのでダメです）。

　そして、今回注目したいのはこの部分です。

　当たり前なのですが、3段目から4段目に移動するときは、必ず「1段でしか」移動できないのが分かるでしょうか。そして、3段目を通らない場合は、必ず2段目から「2段でしか」移動できないのも分かるでしょうか？

　まとめると、最後の移動で1段昇った場合は直前に3段目におり、最後の移動で2段昇った場合は直前に2段目にいるのです。つまり、最後から1手前を考えると、「最後に昇る前どこにいたか」と「最後に何段昇ったか」は必ず対応関係にあるのです。何回階段を昇ったか、1歩が何回で2歩が何回だったか、そういうのは全く関係なく、ただ「最後はこうだった」ということが確かにわかるのです。

　そして、この事実こそがこの問題を解くためには不可欠なキーポイントなのです。

2.問題を解くとは明確な手順を定めること

　では、これを15段の時に拡張して考えてみます。

　15段目に昇るには

・最後に昇る前に13段目にいて、最後に2段昇る

・最後に昇る前に14段目にいて、最後に1段昇る

　かのいずれかしかありません。ただし、13段目から2段昇る場合は、13段目自体に2段昇って到達していてはいけない（連続で2段昇っていることになるため）ので、正確にはこう書けます。

・最後に昇る前には1段昇って13段目にいて、最後に2段昇る

・最後に昇る前には14段目にいて、最後に1段昇る

　また、「最後に昇る前には1段昇って13段目にいる」ためには、その直前に12段目にいる必要があります。よって、「最後に1段昇って13段目にいる方法」の数は、結局「12段目に昇る方法」の数と等しいことが分かりました。

　よって、「15段目に昇る方法」の数は

・14段目に昇る方法の数

・12段目に昇る方法の数

　を合わせたものになります。

　なんだか問題が複雑になったような気もしますが、実はこの方向でよいのです。なぜならば同様に考えていくことで、

・14段目に辿り着くための方法の数は、「13段目にいる方法の数と、11段目にいる方法の数」の和

　ということが分かります。これを繰り返していくと、

…

・5段目に辿り着くための方法の数は、「4段目にいる方法の数と、2段目にいる方法の数」の和

・4段目に辿り着くための方法の数は、「3段目にいる方法の数と、1段目にいる方法の数」の和

　ということが分かります。そして、1段目、2段目、3段目に昇る方法はそれぞれ1通り、2通り、3通りしかないことが、実際に数えることですぐにわかります。

　これが分かれば、4段目に昇る方法の数と5段目に昇る方法の数が分かります。そしてこれを使うと、6段目、7段目……と順々にわかっていき、やがて15段目に昇る方法の数も分かるのです。

　より一般には

「n段目に昇る方法の数は、n-1段目に昇る方法の数と、n-3段目に昇る方法の数の和である」

　という事実が4以上の整数nについて成り立つので、n=4,5,……と順に解けばn=15の場合が分かるのです。同じ構造の小さな問題を順に解くことで、大きな問題を解く、というようなイメージです。　

　これは手計算することもできますが、以下のようにプログラムを書いて解かせることもできます。

# 数列dpの要素を0で初期化する（配列の1番目は「0番目」としてカウントされることに注意）
dp = [ 0 for _ in range(15)]

# 初期値の初期化（1段目には1通り、2段目には2通り、3段目には3通りの昇り方がある）
dp[0] = 1
dp[1] = 2
dp[2] = 3

# 先に考えた通りの方法で昇り方の総数を計算する
for i in range(3, 15):
    dp[i] = dp[i - 1] + dp[i - 3]

# 15段目の昇り方を出力する
print(dp[14])

#include <iostream>
#include <vector>

int main(){
    // 数列dpの要素を0で初期化する（配列の1番目は「0番目」としてカウントされることに注意）
    std::vector<int> dp(15, 0);

    // 初期値の初期化（1段目には1通り、2段目には2通り、3段目には3通りの昇り方がある）
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 3;

    for(int i=3;i<15;i++){
        dp[i] = dp[i - 1] + dp[i - 3];
    }

    std::cout << dp[14] << std::endl;

    return 0;
}

　別解として「1歩昇ってn段目に到達する方法の数」と「2歩昇ってn段目に到達する方法の数」を別の配列で分けて考える方法もあるので、PythonとC++でそちらを実装した別解も載せておきます。

# dp_step1[i]はちょうどi段目に1歩昇って到達する方法
# dp_step2[i]はちょうどi段目に2歩昇って到達する方法
dp_step1 = [ 0 for _ in range(15)]
dp_step2 = [ 0 for _ in range(15)]

# 1段を1歩で昇る方法は1通り、2歩で昇る方法は0通り
dp_step1[0] = 1
dp_step2[0] = 0
# 2段を1歩ずつで昇る方法は1通り、2歩で昇る方法は1通り
dp_step1[1] = 1
dp_step2[1] = 1

# 2連続2段にならないように気をつけながら足していく
for i in range(2, 15):
    dp_step1[i] = dp_step1[i - 1] + dp_step2[i - 1]
    dp_step2[i] = dp_step1[i - 2]

print(dp_step1[14] + dp_step2[14])

#include <iostream>
#include <vector>

int main(){
    // dp_step1[i]はちょうどi段目に1歩昇って到達する方法
    // dp_step2[i]はちょうどi段目に2歩昇って到達する方法
    std::vector<int> dp_step1(15, 0);
    std::vector<int> dp_step2(15, 0);

    // 1段を1歩で昇る方法は1通り、2歩で昇る方法は0通り
    dp_step1[0] = 1;
    dp_step2[0] = 0;
    // 2段を1歩ずつで昇る方法は1通り、2歩で昇る方法は1通り
    dp_step1[1] = 1;
    dp_step2[1] = 1;

    // 2連続2段にならないよう気をつけながら足していく
    for(int i=2;i<15;i++){
        dp_step1[i] = dp_step1[i - 1] + dp_step2[i - 1];
        dp_step2[i] = dp_step1[i - 2];
    }

    std::cout << dp_step1[14] + dp_step2[14] << std::endl;

    return 0;
}

　いずれの場合も、1秒足らずで今回の正解である「277」が出力されます。

　お疲れ様でした！

3.おわりに

　このように「最終的に解きたい問題を、小さな似たような問題に切り分けていき、小さな問題の答えを記録しておいて、最終的に解きたい問題の答えを出す」というような解き方の手順を「動的計画法」と呼びます（この説明は厳密ではありません。あくまで雰囲気です）。

　今回なら「15段目に昇るための方法の数」を知るために、「1～14段目に昇るための方法の数」という小問題を作り、それを解くことで最終的な問題にも答えていました。コンピュータを使わなくても、まさに動的計画法の1例と言うことができるでしょう。

　一応、入試数学においては数列や漸化式というジャンルに分類されますが、競技プログラミングなどの目線から見るとまた別の名前が付いているわけですね。同じものを別の目線から見ることで、別の方向から理解をするのも面白いものです。

　ちなみに、同様の考察で漸化式を立てられる問題として、京都大学2005年にこんな出題があります。

　この問題では一般のnに対して答えを出す必要があるので、漸化式を立てたらちゃんと自分で解く必要があります。プログラミングで解くなら……1000000以下の正の整数nを入力すると、2秒以内には答えの下5桁が返ってくるようなプログラムが書ければ充分でしょう（答えそのものはnが大きくなるとかなり大きくなってしまうので、下5桁に限定しています）。

　以下にプログラムの例と入力例、及び元の問題の正しい解答を置いておきますので、確認したい方はどうぞ。

2 -> 5
3 -> 11
100 -> 40501
365 -> 25643
4210 -> 25365
10419 -> 55051
414120 -> 46101
1000000　-> 12501

#include <iostream>
#include <vector>
using ll = long long;

int main(){
    ll N;
    std::cin >> N;

    std::vector<ll> dp_red(N, 0);
    std::vector<ll> dp_blue(N, 0);
    std::vector<ll> dp_yellow(N, 0);

    dp_red[1] = 3;
    dp_blue[1] = 1;
    dp_yellow[1] = 1;

    for(int i=2;i<N;i++){
        dp_red[i] = dp_red[i - 1] + dp_blue[i - 1] + dp_yellow[i - 1];
        dp_blue[i] = dp_red[i - 1];
        dp_yellow[i] = dp_red[i - 1];
        dp_red[i] %= 100000;
        dp_blue[i] %= 100000;
        dp_yellow[i] %= 100000;
    }

    ll answer = dp_red[N - 1] + dp_blue[N - 1] + dp_yellow[N - 1];
    std::cout << answer % 100000 << std::endl;

    return 0;
}

N = int(input())

# dp_red[i]はi+1両目を最後尾としたときに「最後尾が赤色かつ、条件を満たすもの」の個数。
# dp_blueやdp_yellowについても同じ。
dp_red = [ 0 for _ in range(N)]
dp_blue = [ 0 for _ in range(N)]
dp_yellow = [ 0 for _ in range(N)]

# 2両の場合、最後尾が赤で条件を満たすものの個数は3つ、青は1つ、黄は1つ
dp_red[1] = 3
dp_blue[1] = 1
dp_yellow[1] = 1

# dp計算
for i in range(2, N):
    dp_red[i] = dp_red[i - 1] + dp_blue[i - 1] + dp_yellow[i - 1]
    dp_blue[i] = dp_red[i - 1]
    dp_yellow[i] = dp_red[i - 1]
    dp_red[i] %= 100000
    dp_blue[i] %= 100000
    dp_yellow[i] %= 100000

answer = dp_red[N - 1] + dp_blue[N - 1] + dp_yellow[N - 1]
print(answer % 100000)

　今月の記事はここまで。今年もプログラミングの記事をはじめ、様々な面白さの切り口を自分なりに提供する機会を頂きまして、本当にありがとうございました。ここまで読んでくださる皆様のおかげで、このコラムは成立しております。

　来年度も気力のある限り続けていければと思いますので、どうぞよろしくお願いいたします。