JOI 春合宿 2013 Day2 (mascots, spy)

今日はDay 2 の問題. Constructions の実装方針が迷走しているので, 明日以降じっくり詰めていきたい.
考える実装は本当に苦手なので, おいおいDragon もキレイに書こうと決意.

Mascots (問題文はコチラ)

dp[i][j] : i * j の長方形を埋める順序 としてDP. 初期値は簡単に求まる. 弱数学.

#include <cstdio>
#include <algorithm>

#define MOD (1000000007)

typedef long long lint;

using namespace std;

lint dp[3001][3001], comb[3001][3001], per[3001];

int main()
{
	for (int i = 0; i <= 3000; i++){
		comb[i][0] = comb[i][i] = 1;
		per[i] = i ? (per[i - 1] * i) % MOD : 1;
		for (int j = 0; j < i; j++){
			comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
		}
	}
	
	int R, C, N;
	scanf("%d %d\n%d", &R, &C, &N);
	
	int minx = 3000, miny = 3000, maxx = 0, maxy = 0;
	
	for (int i = 0; i < N; i++){
		int A, B;
		scanf("%d %d", &A, &B);
		miny = min(miny, A); maxy = max(maxy, A);
		minx = min(minx, B); maxx = max(maxx, B);
	}
	
	lint perm = 1;
	for (int i = 1; i <= (maxx - minx + 1) * (maxy - miny + 1) - N; i++)
		perm = (perm * i) % MOD;
	
	dp[maxx - minx + 1][maxy - miny + 1] = perm;
	
	for (int i = maxx - minx + 1; i <= C; i++){
		for (int j = maxy - miny + 1; j <= R; j++){
			dp[i][j] += dp[i - 1][j] * per[j];
			dp[i][j] += dp[i][j - 1] * per[i];
			dp[i][j] %= MOD;
		}
	}
	
	lint res = (dp[C][R] * comb[C - (maxx - minx + 1)][minx - 1]) % MOD;
	res = (res * comb[R - (maxy - miny + 1)][miny - 1]) % MOD;
	
	printf("%lld\n", res);
	
	return (0);
}

Spy (問題文は コチラ)

想定解はeuler-tour + imos 法だが, 綺麗なDP 解がある. DAG の遷移が自明に分かるのでキレイ.

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int memo[2048][2048];
int proj[2048][2048];
int pJ[2048], pI[2048];
vector<int> JOI[2048], IOI[2048];

int calc(int joi, int ioi)
{
	if (~memo[joi][ioi]) return (memo[joi][ioi]);
	
	int res = proj[joi][ioi];
	
	if (~pJ[joi]) res += calc(pJ[joi], ioi);
	if (~pI[ioi]) res += calc(joi, pI[ioi]);
	if (~pJ[joi] && ~pI[ioi]) res -= calc(pJ[joi], pI[ioi]);
	
	return (memo[joi][ioi] = res);
}

int main()
{
	memset(memo, -1, sizeof(memo));
	memset(pJ, -1, sizeof(pJ)); memset(pI, -1, sizeof(pI));
	
	int N, M;
	
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < N; i++){
		int joi, ioi;
		scanf("%d %d", &joi, &ioi);
		pJ[i] = --joi; pI[i] = --ioi;
		if (~joi) JOI[joi].push_back(i);
		if (~ioi) IOI[ioi].push_back(i);
	}
	
	for (int i = 0; i < M; i++){
		int qJ, qI;
		scanf("%d %d", &qJ, &qI);
		proj[--qJ][--qI]++;
	}
	
	for (int i = 0; i < N; i++){
		printf("%d\n", calc(i, i));
	}
	
	return (0);
}