Code Jam Korea 2012 본선 (A)

문제 A. 생존자

삽질만 하다가 틀린 문제다. ㅠㅠㅠㅠ

이것도  DP로 풀면 되긴 하는데, 정렬 방법을 잘못 생각해서 틀렸다. 직관적으로 생각할 때 deadline이 앞에 있는 음식부터 먹어야 할 것 같지 않은가? 그래서 S로 먼저 정렬하고, P로 정렬했다. (P로 나중에 정렬했으니, P에 더 가중치를 두고 정렬한 것이 된다.) 그런데 답이 틀렸다. 정렬 방법을 바꿔봤는데도 틀렸다. 그래서 왜 틀렸나 고민을 해보다가 단순히 P로 정렬하면 안 되는 경우를 찾긴 했다. 그래서 gg치고 딴 거 했다.

답을 보고 하는 소리지만, 결론적으로 (P + S)로 정렬하면 된다. (P + S)는 해당 음식을 최대한 늦게 먹고 배부른 상태에서 그 상태가 끝나는 시간일 것이다. 이 값이 상대적으로 더 작은 음식을 먼저 먹는 것은 경우에 따라 가능하지만, 더 큰 음식을 먼저 먹고 더 작은 음식을 나중에 먹는 것은 절대 불가능하다. 그리고 이 값이 같으면 어느 것을 먼저 먹든 생존 시간에 영향을 주지 않는다. (엄밀한 증명은 좀 귀찮겠지만, 대충 따져보니 이런 것 같다.) 이렇게 답을 적어 놓으면 간단해 보이지만, 문제 풀 당시에 생각하는 건 잘 안 됐다. (원래 그런 거지만)

이렇게 음식을 정렬해두면, 그 다음엔 간단하게 풀 수 있다. 타임라인을 그어보면 P_MAX + S_MAX + 1이 최대일 것이다. 타임라인을 그은 다음, 각 시각에 대해 생존한 상태이고, 막 음식을 먹어야할 상황이면 1로 표시한다. 음식을 순서대로 먹을지 말지 적용하면서 타임라인을 업데이트하면 된다. 시간 복잡도는 O((P + S)N)이 된다. Large를 푸는데 40초정도 걸린다.

사실 small data set은 brute force하게 풀어도 답이 나온다. 통계를 보면 small은 126명 중 105명이 풀었고, large는 20명이 풀었다. (다른 사람들도 아마 정렬하는 걸 생각 못해서 틀렸을 것 같다.)

#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
#define ITEM_MAX 1000
#define P_MAX 100000
#define S_MAX 1000
#define TIME_MAX (P_MAX + S_MAX + 1)

typedef pair<int,int> mypair;
vector<mypair> item;
int dp[TIME_MAX + 1];

bool comp3(mypair a, mypair b)
{
	return (a.first + a.second < b.first + b.second);
}

void foo(int i, int j) // wrong
{
	assert(dp[j]);
	if (i > item.size())
		return;

	if (item[i].first < j) {
		foo(i + 1, j);
	} else {
		// eat item i
		int x = j + item[i].second;
		if (x <= TIME_MAX) {
			dp[x] = 1;
			foo(i + 1, x);
		}
		// don't eat
		foo(i + 1, j);
	}
}

int bar()
{
	int large = 0;
	for (int i = 0; i < item.size(); ++i) {
		for (int j = item[i].first; j >= 0; --j) {
			if (dp[j]) {
				int x = j + item[i].second;
				dp[x] = 1;
				if (x > large)
					large = x;
			}
		}
	}
	return large;
}

int main(void)
{
	int T_;
	scanf("%d", &T_);
	for (int i_ = 1; i_ <= T_; ++i_) {
		item.clear();
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		int ans = 0;
		int N;
		scanf("%d", &N);
		for (int i = 0; i<N; ++i) {
			int a, b;
			scanf("%d %d", &a, &b);
			assert(a <= P_MAX);
			assert(b <= S_MAX);
			item.push_back(make_pair(a,b));
		}
		sort(item.begin(), item.end(), comp3);
		//foo(0, 0);
		ans = bar();
		for (int i = 0; i<N; ++i) {
		//	printf("item%d: %d %d\n", i, item[i].first, item[i].second);
		}
		printf("Case #%d: %d\n", i_, ans);
	}
	return 0;
}