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"; }
まあここまでは特に問題なし。