前回は、Project Euler で紹介されている問題31を解いてみました。前回は8重ループを使って解きましたが、今回は、DP（動的計画法）を使って計算します。
再掲載 Project Euler 問題31（コインの合計）
イギリスの通貨は、ポンド（£）とペンス（p）である。一般に流通しているコインは次の8枚である。
1p, 2p, 5p, 10p, 20p, 50p, £1（100p）, £2（200p）
£2（200p）を作るには、次のようにすればよい。
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
コインの枚数を問わないとして、£2は何通り作ることができるか求めよ。
考察
DP（動的計画法）は、漸化式を使って問題をモデリングします。
検討案1
作る通り数を配列 dp で表します。漸化式は以下とします。新しい i に対して、coins[j] を使って作る通り数を足せばよい、という考えです。
- dp[0] = 1
- dp[i] = dp[i] + dp[i – coins[j]] (i = 1, …, 200, j = 0, …, 7)
この漸化式をそのまま C プログラムにしました。
#include <stdio.h>
typedef unsigned long long ull;
#define N 200
ull dp[N + 1];
int main(void)
{
int coins[8] = {1, 2, 5, 10, 20, 50, 100, 200};
int i, j;
dp[0] = 1;
for (i = 1; i <= N; ++i) {
for (j = 0; j < 8; ++j) {
if (i - coins[j] >= 0) {
dp[i] += dp[i - coins[j]];
}
}
}
for (i = 1; i <= 10; ++i) {
printf("%d: %lld\n", i, dp[i]);
}
printf("Problem031: %lld\n", dp[N]);
return 0;
}このプログラムを動かすと、dp の値は非常に速く大きくなり、64ビット整数の大きさでもオーバーフローします。i が5以下の範囲で dp[i] の値を調べてみましょう。
| i | 本来の値 | 本来の値の内容 | dp[i] | dp[i] の内容 |
| 1 | 1通り | 1 | 1通り | 1 |
| 2 | 2通り | 1+1, 2 | 2通り | 1+1, 2 |
| 3 | 2通り | 1+1+1, 1+2 | 3通り | 1+1+1, 1+2, 2+1 |
| 4 | 3通り | 1+1+1+1, 1+1+2, 2+2 | 5通り | 1+1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 |
| 5 | 4通り | 1+1+1+1+1+1, 1+1+1+2, 1+2+2, 5 | 9通り | 1+1+1+1+1 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 5 |
- dp[0] = 1
- dp[1] = dp[1-1] = 1
- dp[2] = dp[2-1] + dp[2-2] = 1+1 = 2
i = 2 までの値は、本来の値と一致しています。dp[3] からは以下のように差がでます。
- dp[3] = dp[3-1] + dp[3-2] = 2+1 = 3
具体的な通り数を考えると以下のようになります。
- dp[2] の2通りは、1+1 と 2 の2通りです。
dp[3] に dp[3-1] を加えるのは、1+1+1 と 2+1 の2通りを加えています。 - dp[1] の1通りは、1 の1通りです。
dp[3] に dp[3-2] を加えるのは、1+2 の1通りを加えています。
つまり、1+2 と 2+1 を重複してカウントしているため、本来の値より1通り増えています。
i = 4 のとき、1+1+2 だけカウントすればよいのですが、今回の dp[4] では、1+1+2、1+2+1、2+1+1 の3通りをカウントしています。このため、本来の値より2通り増えています。
この理由により、この計算は正しい解答を出力していません。
検討案2
さきほど検討した漸化式では、dp[i] を決める場合に、それより前の dp に対して、どのコインを使っているか分かりません（情報がありません）。
発想を逆転して、使うコインを決めて、dp を求めてみます。以下とします。
- coins[0] (1p) を使って、dp[i] (i = 1, …, 200) を求めます。
漸化式 dp[i] = dp[i – 1] を用いて、
dp[1] = dp[2] = … = dp[200] = 1
を求めることができます。 - 次に coins[1] (2p) を使って、dp[i] (i = 1, …, 200) の値を更新します。
漸化式は同じ dp[i] = dp[i] + dp[i-2] を用います。
この計算により i = 3 の場合、1+2 のみカウントします。(2+1は除かれます。） - これを coins[i] (i = 2, …, 7) まで繰り返します。
解答例
検討案2を Ｃ プログラムにしました。以下となります。検討案1と近いですが、2重ループの順番が逆になっています。
#include <stdio.h>
typedef unsigned long long ull;
#define N 200
ull dp[N + 1];
int main(void)
{
int coins[8] = {1, 2, 5, 10, 20, 50, 100, 200};
int i, j;
dp[0] = 1;
for (i = 0; i < 8; ++i) {
for (j = coins[i]; j <= N; ++j) {
dp[j] += dp[j - coins[i]];
}
}
printf("Problem031: %lld\n", dp[N]);
return 0;
}プログラムは正しい解答を出力しました。
このプログラムは、N = 10000 に対しても待ち時間なく解答を出力します。解答は、64ビット整数に収まる 1,133,873,304,647,601 通りとなりました。
コインの種類をQ、求める数をNとすると、前回の求め方の計算量は、$O(N^Q)$ となります。今回のDPを使った計算量は、$O(N \times Q)$ となり、劇的に減らすことができました。
最後に
今回、紹介したDPを使った実装は、Project Euler が正解者向けに公開している解説を参考にしました。
最近、AtCoder の ABC で出題される問題の解説と、AOJ で公開されている IPT1 を Python で解く解説を書くことが増えていました。Project Euler の問題は、教育的な観点がより多く含まれているように感じます。勉強になりました。
引き続き、Project Euler の問題を紹介していきます。
