部分和問題 / 真偽値か場合の数を扱うかで答えが変わってしまう

Question

問題

AtCoder Beginner Contest 204 D問題

方針

配列の値を集合１と集合２に分け、各総和の差が最小となるような時の、両集合の最大値を求める。

正解コード

こちらは、dp[i][j] := 「i番目までの要素を見た時に、総和をjとすることは可能か？」というdpテーブルを作ることで実装しました。

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define ll long long

/* import vector from standard input */
vector<ll> import_vector(ll n) { vector<ll> li = {}; for (ll i = 0; i < n; i++) { ll j; cin >> j; li.push_back(j); } return li; }

/* max(a, b) */
ll larger(ll a, ll b) { if (a >= b) { return a; } else { return b; } }

/* sum */
ll total(vector<ll> li) { ll ans = 0; for (ll i = 0; i < li.size(); i++) { ans += li.at(i); } return ans; }

void solve() {
	ll N; cin >> N;
	vector<ll> A = import_vector(N);

	vector<vector<bool>> dp = {};
	for (ll i = 0; i < N; i++) {
		vector<bool> cand = {};
		for (ll j = 0; j <= total(A); j++) {
			cand.push_back(false);
		}
		dp.push_back(cand);
	}

	dp.at(0).at(A.at(0)) = true;
	for (ll i = 0; i < N; i++) {
		dp.at(i).at(0) = true;
	}

	for (ll i = 1; i < N; i++) {
		for (ll j = 0; j <= total(A); j++) {
			if (j >= A.at(i)) {
				dp.at(i).at(j) = (dp.at(i - 1).at(j - A.at(i)) || dp.at(i - 1).at(j));
			}
			else {
				dp.at(i).at(j) = dp.at(i - 1).at(j);
			}
		}
	}

	vector<bool> check = dp.at(N - 1);
	ll faster = 0;
	for (ll j = 0; j <= total(A); j++) {
		if (2 * j <= total(A) && check.at(j)) {
			faster = j;
		}
	}

	ll slower = total(A) - faster;
	cout << larger(slower, faster) << endl;
}

int main() {
    solve();
}

不正解コード

方針は全く同じですが、dp[i][j] := 「i番目までの要素を見た時に、総和をjとする選び方の場合の数は何通りか？」というdpテーブルを組みました。

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define ll long long

/* import vector from standard input */
vector<ll> import_vector(ll n) { vector<ll> li = {}; for (ll i = 0; i < n; i++) { ll j; cin >> j; li.push_back(j); } return li; }

/* max(a, b) */
ll larger(ll a, ll b) { if (a >= b) { return a; } else { return b; } }

/* sum */
ll total(vector<ll> li) { ll ans = 0; for (ll i = 0; i < li.size(); i++) { ans += li.at(i); } return ans; }

void solve() {

	ll N; cin >> N;
	vector<ll> A = import_vector(N);
 
	vector<vector<ll>> dp = {};
	for (ll i = 0; i < N; i++) {
		vector<ll> cand = {};
		for (ll j = 0; j <= total(A); j++) {
			cand.push_back(0);
		}
		dp.push_back(cand);
	}
 
	dp.at(0).at(A.at(0)) = 1;
	for (ll i = 0; i < N; i++) {
		dp.at(i).at(0) = 1;
	}
 
	for (ll i = 1; i < N; i++) {
		for (ll j = 0; j <= total(A); j++) {
			if (j >= A.at(i)) {
				dp.at(i).at(j) = dp.at(i - 1).at(j - A.at(i)) + dp.at(i - 1).at(j);
			}
			else {
				dp.at(i).at(j) = dp.at(i - 1).at(j);
			}
		}
	}
 
	vector<ll> check = dp.at(N - 1);
	ll faster = 0;
	for (ll j = 0; j <= total(A); j++) {
		if (2 * j <= total(A) && check.at(j) > 0) {
			faster = j;
		}
	}
 
	ll slower = total(A) - faster;
	cout << larger(slower, faster) << endl;
}

int main() {
    solve();
}

質問

両者は基本的には全く同一のアルゴリズムで組み立てられていて、違いといえば「可能か？」の部分を「何通りか？」に変えただけで、これは後者の値が0より大きい時前者の可能であるということに対応すると考えておりました。しかし、ジャッジでは複数個のテストケースにおいて不正解が出る結果となりました。一体どの部分が起因してこのようになってしまうのでしょうか。素人質問にて恐縮ですが、ご教授のほど何卒よろしくお願い申し上げます。

Answer 1

99
1000 ... 1000
のようなケースが不正解を出していましたが、よくよく調べると多数の箇所でオーバーフローを起こしていました。こういった場合場合の数が巨大になり得るということを想定しきれていませんでした。