Typical DP Contest ABCDE

http://tdpc.contest.atcoder.jp/assignments

Typical DP Contestの問題が最近のCodeforcesでも出たということを聞いて埋めておこうと思った。

20問あるので5問ずつに分けます。

A
配列使いまわしもして十分高速だけど、boolのdpだとどっかで無駄に情報持ってないか心配になる。

int N;
bool dp[10010];
 
void solve() {
	cin >> N;
	dp[0] = true;
	rep(i, 0, N) {
		int a; cin >> a;
		rer(i, 10001, 0) {
			if(i - a >= 0 && dp[i - a]) dp[i] = true;
		}
	}
	int res = 0;
	rep(i, 0, 10001) {
		res += dp[i];
	}
	cout << res << "\n";
}

B
ゲームを後ろから見ればわかる。

int A, B;
int D[1010], E[1010];
int dp[1010][1010];

void solve() {
	cin >> A >> B;
	rep(i, 0, A) cin >> D[i];
	rep(i, 0, B) cin >> E[i];
	reverse(D, D + A); reverse(E, E + B);

	rep(i, 0, A + 1) {
		rep(j, 0, B + 1) {
			if((A + B - i - j) % 2 == 0) dp[i][j] = 0;
			else dp[i][j] = inf;
		}
	}

	dp[0][0] = 0;
	rep(i, 0, A + 1) {
		rep(j, 0, B + 1) {
			bool snuke = ((A + B - i - j) % 2 == 0);
			if(snuke) {
				if(i) MAX(dp[i][j], dp[i - 1][j] + D[i - 1]);
				if(j) MAX(dp[i][j], dp[i][j - 1] + E[j - 1]);
			}
			else {
				if(i) MIN(dp[i][j], dp[i - 1][j]);
				if(j) MIN(dp[i][j], dp[i][j - 1]);
			}
		}
	}
	cout << dp[A][B] << "\n";
}

C
O(K*4^K)なんて10^7くらいだから余裕で通るのに、O(K*2^K)にしようとうんうん唸っていたの謎。計算式そのまま。

int N, K;
double dp[11][1040];
int R[1040];

void solve() {
	cin >> K;
	N = (1 << K);
	rep(i, 0, N) {
		cin >> R[i];
		dp[0][i] = 1.0;
	}

	rep(i, 0, K) {
		rep(j, 0, N) {
			int a = (1 << i);
			int b = j / a;
			if(b % 2 == 0) {
				rep(k, (b + 1) * a, (b + 2) * a) {
					dp[i + 1][j] += dp[i][k] / (1.0 + pow(10.0, (R[k] - R[j]) / 400.0));
				}
			}
			else {
				rep(k, (b - 1) * a, b * a) {
					dp[i + 1][j] += dp[i][k] / (1.0 + pow(10.0, (R[k] - R[j]) / 400.0));
				}
			}
			dp[i + 1][j] *= dp[i][j];
		}
	}
	rep(i, 0, N) cout << dp[K][i] << "\n";
}

D
1~6までならあり得る約数は2,3,5しかないので、こいつらを持つ。

int N, A, B, C;
ll D;
double dp[2][40][40][40];

void solve() {
	cin >> N >> D;
	while(D % 2 == 0) {
		D /= 2;
		A++;
	}
	while(D % 3 == 0) {
		D /= 3;
		B++;
	}
	while(D % 5 == 0) {
		D /= 5;
		C++;
	}
	if(D != 1) {
		cout << 0 << "\n";
		return;
	}
	dp[0][0][0][0] = 1.0;

	int now, nex;
	rep(i, 0, N) {
		now = i % 2, nex = 1 - now;
		rep(j, 0, A + 1) {
			rep(k, 0, B + 1) {
				rep(l, 0, C + 1) dp[nex][j][k][l] = 0.0;
			}
		}
		rep(j, 0, A + 1) {
			rep(k, 0, B + 1) {
				rep(l, 0, C + 1) {
					double s = dp[now][j][k][l] / 6;
					dp[nex][j][k][l] += s;
					dp[nex][min(j + 1, A)][k][l] += s;
					dp[nex][j][min(k + 1, B)][l] += s;
					dp[nex][min(j + 2, A)][k][l] += s;
					dp[nex][j][k][min(l + 1, C)] += s;
					dp[nex][min(j + 1, A)][min(k + 1, B)][l] += s;
				}
			}
		}
	}
	cout << dp[nex][A][B][C] << "\n";
}

E
上の位から見ていってNと一致しているかそうでないか、その時のDで取ったmodを持つ。
Dと一致している場合、modは1通りしかないのに100要素の配列使っているのは無駄ですね…

int D, N;
ll dp[2][100][2];
string str;
 
void solve() {
	cin >> D >> str;
	N = (int)str.size();
	dp[0][0][0] = 1;
 
	int now, nex;
	rep(i, 0, N) {
		int a = str[i] - '0';
		now = i % 2, nex = 1 - now;
		rep(j, 0, D) {
			dp[nex][j][0] = 0;
			dp[nex][j][1] = 0;
		}
		rep(j, 0, D) {
			ADD(dp[nex][(j + a) % D][0], dp[now][j][0]);
			rep(k, 0, a) 
				ADD(dp[nex][(j + k) % D][1], dp[now][j][0]);
			rep(k, 0, 10) 
				ADD(dp[nex][(j + k) % D][1], dp[now][j][1]);
		}
	}
	cout << (dp[nex][0][0] + dp[nex][0][1] - 1 + mod) % mod << "\n";
}

まあここまでは特に問題なし。