Code Jam Korea 2012 본선 (C)

문제 C. 모자 쓴 아이들

푸는데 0.3초밖에 안 걸린다. 추가로  sum of bar()도 dp로 바꿔버릴 수 있다. 사실 dp 테이블에서 삼각형 모양만 필요하니까 역삼각형 모양에 누적값을 저장해두는 식으로 활용하면 된다. 물론 dp[2001][2002]로 바꿔줘야 하지만... 그런데 이 문제에서는 그렇게 고친다고 엄청나게 빨라지지는 않는다. 그러므로 코드가 깔끔한 버전을 여기에 올림.

아래 식도 내가 직접 계산했던 식인데 오랜만에 보니 어떻게 이런 식이 나왔는지 도저히 기억이 나지 않는다.

http://www.algospot.com/forum/read/1326/

1st부터 (i-1)th의 아이에게 모자를 씌우는 방법의 수를 구할 때, 남은 모자의 개수를 생각해서 조합으로 구했습니다.

 

#include <stdio.h>
#include <string.h>
#include <assert.h>

int dp[2001][2001];

void foo()
{
	for (int i = 0; i <= 2000; ++i) {
		for (int j = 0; j <= i; ++j) {
			if (j > i / 2) {
				dp[i][j] = dp[i][i - j];
			} else if (j == 0) {
				dp[i][j] = 1;
			} else {
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				if (dp[i][j] >= 32749)
					dp[i][j] -= 32749;
			}
		}
	}
}

int bar(int i, int j)
{
	if (i < 0 || i > 2000) {
		fprintf(stderr, "ERR_bar: %d\n", i);
	}
	if (j >= 0 && j <= i)
		return dp[i][j];
	return 0;
}

int main(void)
{
	foo();
	int T_;
	scanf("%d", &T_);
	for (int i_ = 1; i_ <= T_; ++i_) {
		int B, W, k, i;
		scanf("%d %d %d %d", &B, &W, &k, &i);
		assert(k <= B + W);
		if (i > k) {
			fprintf(stderr, "ERR_INPUT: %d %d\n", i, k);
		}
		const int kk = (B + W) - k;
		int ans = bar(k - i, B - i + 1) // i는 흰색
			+ bar(k - i, W - i + 1); // i는 검은색
		if (ans > 32749)
			ans -= 32749;
		if (ans) {
			int mul = 0;
			for (int m = i - 1 - kk; m <= i - 1; ++m) {
				mul += bar(i - 1, m);
			}
			mul %= 32749;
			for (int m = 1; m <= i - 1; ++m) {
				int x = 0;
				for (int p = 0; p <= kk; ++p) {
					x += bar(m - 1, p);
				}
				x %= 32749;
				mul -= bar(i - m - 1, kk - m + 1) * x;
				mul %= 32749;
			}
			//fprintf(stderr, "mul: %d\n", mul);
			ans *= mul;
			ans %= 32749;
		}
		printf("Case #%d: %d\n", i_, ans);
	}
	return 0;
}