動的計画法の漸化式をループさせるときに、ある添え字が別の添え字の取りうる範囲に制限を与えることに着目して、ループさせたら誤った答えが得られた。

Question

前提・実現したいこと

問題文は以下の通り。

「高橋君は、N枚のカードを持っています。 i(1≤i≤N) 番目のカードには、整数 xi が書かれています。 高橋君は、これらのカードの中から 1 枚以上を選び、 選んだカードに書かれた整数の平均をちょうど A にしたいと考えています。 そのようなカードの選び方が何通りあるか求めてください。」

動的計画法を用いて漸化式を立てると次の通り。

if (j >= x[i]&&k > 0) {dp[i + 1][j][k] = dp[i][j - x[i]][k - 1] + dp[i][j][k];}
else {dp[i + 1][j][k] = dp[i][j][k];}

i:ここまでで選ぶかどうか判断し終えたカードの番号
j:選んだカードたちの値の合計
k:実際に選んだカードの枚数

これを全通りに対し実行し、最後にdp[N][kA][k]をすべてのkについて合計すれば答えが得られる。（Aは平均値であるから。j=kAとすれば良い。）

発生している問題・エラーメッセージ

質問は二点。

まず一点目。私は、

for (int i = 0; i < N; i++) {
for (int k = 0; k <= N; k++) {
for (int j = 0; j <= sum; j++) {}}}

と素直にすればいいものの、

for (int i = 0; i < N; i++) {
for (int k = 0; k <= i; k++) {
for (int j = 0; j <= sum; j++) {}}}

とした。なぜなら、ここまでで選ぶかどうか考慮し終えた番号iを、実際に選んだ枚数kが超えることなどありえないから、当然i<kのときの場合の数は0通りになるので考慮する必要がないと考えたからだ。すると、誤った答えが得られた。これはなぜだろうか。

質問二点目。
次に、質問一点目の内容を正しいソースコードに書き換えたが、最後にdp[N][kA][k]をすべてのkについて合計するところで、1≤k≤Nで合計するのではなく、1≤k≤n(但しint n=sum/a,sumは全xiの合計値)で合計した。なぜなら、選んだカードの合計値jが、nAを超えて、かつkが整数となることは数学的にあり得ないので、n<k≤Nなるkを考慮する必要はないと考えたからである。
すると、またしても誤った答えが得られた。なぜだろうか。

入門者なりに散々考えた末の質問です。どうか核心を突いた明快なご指摘を頂きたいです。よろしくお願い致します。

該当の(誤った)ソースコード

#include <iostream>
using namespace std;
 
int main() {
	int N, A;
	cin >> N >> A;
	int x[53];
	int sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> x[i];
		sum += x[i];
	}
	long long dp[53][2550][53] = { 0 };
	dp[0][0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k <= i; k++) {
			for (int j = 0; j <= sum; j++) {
				if (j >= x[i]&&j>0) {
					dp[i + 1][j][k] = dp[i][j - x[i]][k - 1] + dp[i][j][k];
				}
				else {
					dp[i + 1][j][k] = dp[i][j][k];
				}
			}
		}
	}
	long long combi;
	combi = 0;
	int n = 0;
	n = sum / A;
	for (int i = 1; i <= n; i++) {
			combi += dp[N][i*A][i];
	}
	cout << combi;
	return 0;
}

正しいソースコード

#include <iostream>
using namespace std;

int main() {
int N, A;
cin >> N >> A;
int x[53];
int sum = 0;
for (int i = 0; i < N; i++) {
cin >> x[i];
sum += x[i];
}
long long dp[53][2550][53] = { 0 };
dp[0][0][0] = 1;
for (int i = 0; i < N; i++) {
for (int k = 0; k <= N; k++) {
for (int j = 0; j <= sum; j++) {
if (j >= x[i]&&k > 0) {
dp[i + 1][j][k] = dp[i][j - x[i]][k - 1] + dp[i][j][k];
}
else {
dp[i + 1][j][k] = dp[i][j][k];
}
}
}
}
long long combi;
combi = 0;
int n = 0;
n = sum / A;
for (int i = 1; i <= N; i++) {
combi += dp[N][i*A][i];
}
cout << combi;
return 0;
}

Answer 1

質問1への回答

例えばx[0]=3の場合、1枚目(i=0)の検証で「取らずに合計値0」か、「取って合計値3」のパターンがありえるので、
dp[1][0][0]=1,dp[1][1][3]=1となり、それ以外のdp[1][j][k]は0のままになります。
ところが、質問者のロジックではi=0のループではk=0しか取れないため、forの中でelseにしか入れません。
そのため、dp[1][j][k]はdp[0][j][k]をそのままコピー、つまりdp[1][0][0]=1以外が0になってしまいます。
この間違いの原因は

ここまでで選ぶかどうか考慮し終えた番号iを、実際に選んだ枚数kが超えることなどありえない

と考えたことにあります。iは正しくは「今現在考慮している番号」で、kは「そこまでで実際に取ろうとしているカード枚数」になります。iが0始まりである関係上、kの最大値はi+1になります。上記理由のため、「そこまでのカードすべて取る」などが実現不可能になっています。

質問2への回答

Aがカードの平均値以上であれば問題ありませんが、カード平均値未満である場合、sum/Aがカード枚数Nを超える可能性があります。その場合、範囲外アクセスをしてしまう可能性があります。

そもそも

いろいろ、非常に効率が悪く、読みにくいコードであるように感じます。
今見ているところから次を見る形にすると、質問者さんの質問1の思考がそのまま適用しやすいですし、余計な分岐が要らなくなります。

    int subsum = 0;  //その時点での合計最大値
    for (int i = 0; i < N; i++) {
        for (int k = 0; k <= i; k++) {  //今見ているのがi番目、それまで取ったカードの最大枚数はi
            for (int j = 0; j <= subsum; j++) {  //合計値はそこまでの最大値までを見ればいい
                dp[i + 1][j + x[i]][k + 1] += dp[i][j][k];  //x[i]を取った場合
                dp[i + 1][j][k] += dp[i][j][k];  //x[i]を取らなかった場合
            }
        }
        subsum += x[i];
    }

Comments

[hanyansakura]

明快かつ完璧なご指摘ありがとうございました。完全にすべての疑問が解決しました。
特に、提示していただいたより読みやすいコードは、入門者の自分にとって大変勉強になりました。
さらなる精進を目指します。