http://tdpc.contest.atcoder.jp/
F
駅に一回も止まらない方法は1or0通りなので
駅に一回は止まる方法を求めれば良い。
区間和を含んだ式になるが、大体形は決まっているので、代わりにsという値で更新を行っている。
あとは場合分けをきちんとする。
int N, K; ll dp[1000010]; void solve() { cin >> N >> K; ll s = 0; rep(i, 1, N - 1) { if(i < K) { //dp[i] = (dp[i - 1] ~ dp[1]) + 1 dp[i] = (s + 1) % mod; ADD(s, dp[i]); } else if(i == K) { //dp[i] = (dp[i - 1] ~ dp[1]) dp[i] = s; ADD(s, dp[i]); } else { //dp[i] = (dp[i - 1] ~ dp[i - K]) dp[i] = s; ADD(s, dp[i]); s = (s - dp[i - K] + mod) % mod; } } ll res = 0; rer(i, N, max(N - K, 1)) { ADD(res, dp[i]); } if(N < K) ADD(res, 1); cout << res << "\n"; }
G
まずiから始まる部分文字列dp[i]の数を求める。
str[i]の次に使う文字はa...zとあるが、i番目以降に各文字が現れる最小のindexをnext[i][j](j=a...z)としておくと、
dp[i]=1+Σdp[next[i][j]]となる。
次に復元は先頭の文字を決めていくことで行う。
index=-1から初めてdp[next[index][j]]の値の和を求めておく。
その値がK以上になったjが最初の文字となる。これを繰り返す。
int N; ll K; int nex[MAX_N][26]; ll dp[MAX_N]; int E[26]; string str; void solve() { cin >> str; N = (int)str.size(); cin >> K; memset(E, -1, sizeof(E)); rer(i, N + 1, 0) { //1-origin rep(j, 0, 26) nex[i][j] = E[j]; if(i) E[str[i - 1] - 'a'] = i; } rer(i, N + 1, 0) { dp[i] = (i > 0); rep(j, 0, 26) { if(nex[i][j] == -1) continue; dp[i] += dp[nex[i][j]]; MIN(dp[i], K + 1); } //debug(i, dp[i]); } if(dp[0] < K) { cout << "Eel\n"; return; } int at = 0; while(K > 0) { ll tmp = 0; int i = 0; while(nex[at][i] == -1 || tmp + dp[nex[at][i]] < K) { tmp += dp[nex[at][i]]; i++; } K -= (tmp + 1); at = nex[at][i]; cout << char('a' + i); } cout << "\n"; }
H
O(NWC)でいいのか…
配列の更新を少しミスって危なかった。サンプルで引っかかったのは幸い。
int N, W, C; int dp[2][10010][55][2]; int w[110], v[110], c[110]; void solve() { cin >> N >> W >> C; rep(i, 0, N) { cin >> w[i] >> v[i] >> c[i]; c[i]--; } int now = 0, nex = 1; rep(i, 0, W + 1) rep(j, 0, C + 1) { dp[0][i][j][0] = -inf; dp[0][i][j][1] = -inf; } dp[0][0][0][0] = 0; rep(i, 0, 50) { rep(j, 0, N) { if(c[j] == i) { rep(k, 0, W + 1) rep(l, 0, C + 1) { dp[nex][k][l][0] = -inf; dp[nex][k][l][1] = -inf; } rep(k, 0, W + 1) { rep(l, 0, C + 1) { MAX(dp[nex][k][l][0], dp[now][k][l][0]); if(k + w[j] <= W) MAX(dp[nex][k + w[j]][l + 1][1], dp[now][k][l][0] + v[j]); MAX(dp[nex][k][l][1], dp[now][k][l][1]); if(k + w[j] <= W) MAX(dp[nex][k + w[j]][l][1], dp[now][k][l][1] + v[j]); } } nex = 1 - nex; now = 1 - now; } } rep(k, 0, W + 1) rep(l, 0, C + 1) { MAX(dp[now][k][l][0], dp[now][k][l][1]); dp[now][k][l][1] = -inf; //don't forget this } } int res = 0; rep(k, 0, W + 1) rep(l, 0, C + 1) MAX(res, dp[now][k][l][0]); cout << res << "\n"; }
I
まず前処理として文字を余さずiwiを取り出せる区間をdpで求める。
この作業を逆から見ると、連続するiwiを取り出すか、端のiを2つともとり、中央のwをとるかの2つの作業があることがわかる。
無駄文字がある場合は前処理のdpを利用して別のdpを解く。
int N; int dp[310][310]; int dp2[310]; string str; void solve() { cin >> str; N = (int)str.size(); rep(i, 0, N + 1) rep(j, 0, N + 1) if(i != j) dp[i][j] = -inf; rep(k, 1, N / 3 + 1) { rep(l, 0, N) { int r = l + k * 3; if(r > N) continue; if(str[l] == 'i' && str[r - 1] == 'i') { for(int i = l + 1; i < r; i++) { if(str[i] == 'w') { MAX(dp[l][r], dp[l + 1][i] + dp[i + 1][r - 1] + 1); } } } for(int i = l; i + 3 <= r; i += 3) { if(str[i] == 'i' && str[i + 1] == 'w' && str[i + 2] == 'i') { MAX(dp[l][r], dp[l][i] + dp[i + 3][r] + 1); } } } } rep(i, 0, N) { for(int j = 3; j <= N; j += 3) { MAX(dp2[i + j], dp2[i] + dp[i][i + j]); } MAX(dp2[i + 1], dp2[i]); } cout << dp2[N] << "\n"; }
J
期待値の式を立てるだけなんだけど、両辺に同じdpの項が出る場合があるので移項して計算する。
int N; double dp[(1 << 16)]; void solve() { cin >> N; int nbit = 0; rep(i, 0, N) { int a; cin >> a; nbit |= (1 << a); } N = 16; rep(bit, 1, (1 << N)) { dp[bit] = inf; rep(j, 1, N - 1) { int cnt = 0; double tmp = 1.0; rep(k, -1, 2) { if(bit & (1 << (j + k))) { tmp += dp[bit ^ (1 << (j + k))] / 3.0; } else cnt++; } if(cnt == 3) continue; MIN(dp[bit], 3.0 * tmp / (3.0 - cnt)); } } cout << dp[nbit] << "\n"; }
Gが難しかった。
どうすれば独立に文字列を数え上げられるかがよくわかっていない。KMPもSAも使えないので精進あるのみです。