第11回情オリ本選対策2日目

もっと効果的にやらないとやばい気がする。
ともかくDPとグラフと思ってTC Practiceに手をつける。GogoXMarisaKirisimaが分からなかった。解説読んでもやっぱり分からなかった。
BricksNも解けそうで解けなかった。解けそうでというのは全然おしい感じではなくて、普通に考える力がない。他人のソース見た上で書いたがWAった。

仕方ないのでAOJ0042 A Thiefを解いた。レベル一気に下がりましたね…

#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

int main()
{
	int W;
	for (int h = 1; scanf("%d\n", &W), W; ++h) {
		int N;
		scanf("%d\n", &N);

		vector<int> value(N), weight(N);
		for (int i = 0; i < N; ++i)
			scanf("%d,%d\n", &value[i], &weight[i]);

		vector<vector<int> > dp(N, vector<int>(W + 1, 0));
		for (int i = weight[0]; i < dp[0].size(); ++i)
			dp[0][i] = value[0];

		for (int i = 1; i < dp.size(); ++i)
		for (int j = 0; j < dp[i].size(); ++j) {
			int cur = dp[i - 1][j];
			if (j - weight[i] >= 0)
				cur = max(cur, dp[i - 1][j - weight[i]] + value[i]);

			dp[i][j] = cur;
		}
		int resValue = dp.back().back(), resWeight = 0;
		for (int i = W - 1; 0 <= i; --i) {
			if (dp.back()[i] != resValue) {
				resWeight = i + 1;
				break;
			}
		}
		printf("Case %d:\n%d\n%d\n", h, resValue, resWeight);
	}
	return 0;
}

AOJ 0202 At Boss's Expenseも解く。が、何故かREとかWAとか言われる。よく分からない。間違ってるのだろうか。他人のソース見てみたけどやっぱり想定解すぎて何が間違ってるんだ…

#include <cstdio>
#include <vector>
using namespace std;
void createPrimeList(vector<bool>& v)
{
	v[0] = v[1] = false;
	for (int i = 2; i < v.size(); ++i) {
		if (!v[i])
			continue;
		for (int j = i + i; j < v.size(); j += i)
			v[j] = false;
	}
	return;
}
int main()
{
	int n, x;
	while (scanf("%d %d\n", &n, &x), n || x) {
		vector<int> value(n);
		for (int i = 0; i < n; ++i)
			scanf("%d\n", &value[i]);

		vector<bool> dpPrev(x + 1, false);
		vector<bool> dpCur;
		for (int i = value[0]; i <= x; i += value[0])
			dpPrev[i] = true;

		for (int i = 1; i < n; ++i) {
			dpCur = vector<bool>(x + 1, false);
			for (int j = 0; j <= x; ++j) {
				bool cur = dpPrev[j];
				if (j - value[i] >= 0)
					cur = cur || dpCur[j - value[i]];
				dpCur[j] = cur;
			}
			dpPrev = dpCur;
		}

		vector<bool> pl(x + 1, true);
		createPrimeList(pl);

		int res = -1;
		for (int i = x; 0 <= i; --i) {
			if (pl[i] && dpCur[i]) {
				res = i;
				break;
			}
		}
		if (res == -1)
			printf("NA\n");
		else
			printf("%d\n", res);
	}
	return 0;
}

誰か気付いたら教えて(他力本願)