AtCoder Grand Contest 003
解法
全ての数が異なるので, ソートされた後それぞれの数がどこに移動するかが決まっている, ということと, 操作 2 が「偶数番目のみ, 奇数番目のみを入れ替えることができる」ということに対応している, ということがポイントです。
最終的に行きたいポイントは決まっているので, 最後に偶数番目になる数が奇数番目にある場合は入れ替えなければならないし, 逆もまた然りです。これに必要な回数は(最終的な偶奇と最初の偶奇がバラバラな数字の数)/2 です。
int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vi A(N); vi B, C; for (int i = 0; i < N; i++) { cin >> A[i]; if (i%2 == 0) B.push_back(A[i]); else C.push_back(A[i]); } sort(A.begin(), A.end()); sort(B.begin(), B.end()); sort(C.begin(), C.end()); int b = 0, c = 0; ll ans = 0; for (int i = 0; i < N; i++) { if (b < B.size() && A[i] == B[b]) { b++; if (i%2 == 1) ans++; } if (c < C.size() && A[i] == C[c]) { c++; if (i%2 == 0) ans++; } } cout << ans/2 << endl; return 0; }
yukicoder No.417 チューリップバブル
O(NM^2) だと結構厳しめの制約だと思ってだいぶ悩んでいた。
解法
O(NM^2) の木 dp をします。
まず考察ですが, 最後に頂点 0 に戻ってこなければならないことから, v -> u と辺を降りた場合, 再び u -> v と戻ってこなければなりません。つまり, 通る辺はすべて 2 回通ることになります。
dp[v][rest] = (頂点 v の時点で残り時間が rest の時の最大利益) とすると, v の子が ch として,
dp[v][rest] = max(dp[ch][j-(v から ch に行くコスト)] + dp[v][rest-j]) + U[v]
というように更新していけば良いです。
const int MAXN = 222; const int MAXM = 1010; int N, M; ll U[MAXN]; struct Edge { int to; int cost; Edge() {} Edge(int t, int c) : to(t), cost(c) {} }; vector<Edge> G[MAXN]; ll dp[MAXN][MAXM]; void dfs(int v, int p) { for (Edge e : G[v]) if (e.to != p) { dfs(e.to, v); } for (Edge e : G[v]) if (e.to != p) { for (int i = M; i >= 0; i--) { for (int j = e.cost; j <= i; j++) { dp[v][i] = max(dp[v][i], dp[v][i-j] + dp[e.to][j-e.cost]); } } } for (int i = 0; i <= M; i++) dp[v][i] += U[v]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M; M /= 2; for (int i = 0; i < N; i++) cin >> U[i]; for (int i = 0; i < N-1; i++) { int a, b, c; cin >> a >> b >> c; G[a].emplace_back(b, c); G[b].emplace_back(a, c); } dfs(0, -1); ll ans = 0; for (int i = 0; i <= M; i++) ans = max(ans, dp[0][i]); cout << ans << endl; return 0; }
yukicoder No.416 旅行会社
解法
クエリを逆に読んでデータ構造をマージする一般的なテクを使えば解けます。
まず消される辺についてはすべて消されてる状態にします。この際 0 と連結な頂点は答えが -1 です。
で, クエリの後ろの辺から辺を追加していきます。追加される辺が a, b であるとすると, a も b も 0 と同じ連結成分にない場合, 普通にマージすれば良いです。
一方で, a, b のいずれかが 0 と同じ連結成分に含まれる場合, 含まれてない側が 0 と初めて連結する, 逆にクエリの順に辺を消していったときはじめて 0 と離れるのはそのクエリの辺の時点とわかるので, 0 と連結していなかった側の答えが確定します。
これらの操作は データ構造をマージする一般的なテクを使う方で O(N log N), 答えをメモするので O(N) かかるので結局計算量は O(N log N) です。
他にもついこないだ出題されたパラレルバイナリサーチを使っても解けるようです。
const int MAXM = 200200; pii edge[MAXM], del[MAXM]; int ans[MAXM]; int e2g[MAXM]; vi g2e[MAXM]; bool isSame(int x, int y) { return e2g[x] == e2g[y]; } void unite(int x, int y) { if (isSame(x, y)) return; int gx = e2g[x], gy = e2g[y]; if (g2e[gx].size() < g2e[gy].size()) { swap(x, y); swap(gx, gy); } for (int el : g2e[gy]) e2g[el] = gx; g2e[gx].insert(g2e[gx].end(), g2e[gy].begin(), g2e[gy].end()); g2e[gy].clear(); } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, Q; cin >> N >> M >> Q; for (int i = 0; i < M; i++) { cin >> edge[i].first >> edge[i].second; edge[i].first--; edge[i].second--; } set<pii> S; for (int i = 0; i < Q; i++) { cin >> del[i].first >> del[i].second; del[i].first--; del[i].second--; S.insert(del[i]); } for (int i = 0; i < N; i++) { e2g[i] = i; g2e[i].push_back(i); } for (int i = 0; i < M; i++) { if (S.find(edge[i]) == S.end()) { unite(edge[i].first, edge[i].second); } } { int g = e2g[0]; for (int el : g2e[g]) ans[el] = -1; } for (int i = Q-1; i >= 0; i--) { int a = del[i].first, b = del[i].second; if (!isSame(a, b)) { if (!isSame(0, a) && !isSame(0, b)) { unite(a, b); } else { if (isSame(0, b)) { swap(a, b); } int gb = e2g[b]; for (int el : g2e[gb]) ans[el] = i+1; unite(a, b); } } } for (int i = 1; i < N; i++) cout << ans[i] << endl; return 0; }
SRM 565 div1 med TheDivisionGame
med にしてはかなり簡単ですね。復帰戦だったのでちょうど良いけど。
問題
TopCoder Statistics - Problem Statement
U さんと K さんがゲームをする。ゲームは S = {L, L+1, ..., R-1, R} という数の集合を使って行う。そして,
- 集合 S の中から何らかの数 X を取り出す。
- X を割り切る数 Y を選ぶ(Y は 2 以上の整数)。
- X を X/Y にして集合 S に戻す。
この一連の操作ができないほうが負けである。ある二つの自然数 A, B が与えられて, L, R は A <= L <= R <= B の範囲で動く。この中で先攻の U さんが勝つ [L, R] の組み合わせは何通りあるか。
解法
明らかに grundy 数っぽいですが, この grundy 数は素因数分解の指数の和になります。
この grundy 数の xor の和が 0 になるところが負けですが, これは累積和を使えば高速に計算できます。
const int MAX = 1000100; int value[MAX]; int cnt[MAX]; int xorCnt[555]; class TheDivisionGame { public: long long countWinningIntervals(int L, int R) { memset(cnt, 0, sizeof(cnt)); for (int i = L; i <= R; i++) value[i-L] = i; for (int i = 2; i*i <= R; i++) { int l = L/i*i; if (l < L) l += i; for (int j = l; j <= R; j+= i) { while (value[j-L] % i == 0) { cnt[j-L]++; value[j-L] /= i; } } } for (int i = L; i <= R; i++) { if (value[i-L] > 1) cnt[i-L]++; } ll minus = 0; int now = 0; memset(xorCnt, 0, sizeof(xorCnt)); xorCnt[0] = 1; for (int i = L; i <= R; i++) { now ^= cnt[i-L]; minus += xorCnt[now]; xorCnt[now]++; } ll d = R-L+1; return d*(d+1)/2 - minus; } };
SRM 565 div1 easy MonstersValley
院試が終わりました。受かったらそれについてもなんか書きます。
問題
TopCoder Statistics - Problem Statement
0 ～ N-1 番までの商品を順番に買っていく。それぞれの商品には値段と重さがあり, 値段は 1 か 2 である。
あなたは, 今までに買った商品の重さの合計が今見ている商品の重さより小さい場合, その商品を買わなければならない。
最小でいくらの値段で N-1 番目までの商品を見終えることができるか。
解法
重さはかなり大きいので dp[i][w] = (i 番目までで合計 w の重さになったときの最小消費) という dp は無理です。ですが値段が 1 or 2 であることを利用して, dp[i][v] = (i 番目までで合計 v のお金を消費した時に得られる最大重量) という dp にすれば計算できます。
const int MAXN = 55; ll dp[MAXN][2*MAXN]; class MonstersValley { public: int minimumPrice(vector<long long> dread, vector <int> price) { int n = dread.size(); memset(dp, -1, sizeof(dp)); dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= 2*i; j++) if (dp[i][j] >= 0) { // 選ぶ dp[i+1][j+price[i]] = max(dp[i+1][j+price[i]], dp[i][j] + dread[i]); // 選ばない if (dp[i][j] >= dread[i]) { dp[i+1][j] = max(dp[i+1][j], dp[i][j]); } } } for (int i = 0; i <= 2*n; i++) { if (dp[n][i] >= 0) return i; } return -1; } };
AtCoder Regular Contest 059 F - バイナリハック / Unhappy Hacking
解法
まず部分点解法を考えます。
dp[n][m][now] = (すでに n 回キーを押したときに, 目標の文字列と m 番目までは一致していて, 生成されている文字は now 個であるような場合の数) という dp をします。これは各状態で 0 を押すか, 1 を押すか, BackSpace を押すかで場合分けすれば簡単に遷移ができるので O(N^3) です。
満点解法では, 文字列 s があって, これを空文字にするように遷移していくことを考えます。
例えば 001001 という文字があったとすると,
- その前は BackSpace を押していた -> 右に 0 か 1 を追加する(0010010 or 0010011)
- その前は文字を追加していた -> 1 を追加する(00100 という文字列だった)
というような遷移があります。空文字列の場合は少し違って, 前に BackSpace を押していた場合にその前もやはり空文字列なこともあるし前の文字は 0 か 1 だったということもあります。
このように考えると, 文字列 s になにが書いてあったかは関係なく, 文字列の長さだけが重要であることに気付きます。この dp は O(N^2) でできるので満点を取ることができます。
const int MAXN = 5050; const int MOD = 1e9+7; int N, M; string s; ll dp[MAXN][MAXN]; ll dfs(int n, int m) { ll& ret = dp[n][m]; if (ret >= 0) return ret; if (n == N) { if (m == 0) return ret = 1; else return ret = 0; } ret = 0; // Back if (m+1 < MAXN) { ret += 2*dfs(n+1, m+1); } if (m == 0) { ret += dfs(n+1, m); } // other if (m > 0) { ret += dfs(n+1, m-1); } ret %= MOD; return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; cin >> s; M = s.size(); memset(dp, -1, sizeof(dp)); cout << dfs(0, M) << endl; return 0; }
AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies
解法
まず部分点解法を考えてみますと, dp[i][rest] = (i 番目まで考えた時点でべき乗する数が C から rest まで減っているような時の和) というのを考えると, この i 番目でべき乗する数をいくつ使うかで場合分けして A[i]^j * dp[i+1][rest-j] というのの和を取れば良いことがわかります。
満点解法では A[i] <= Xi <= B[i] を満たすものすべてを扱わなければなりませんが, これは上記の A[i]^j というのを A[i]^j + (A[i]+1)^j ... + B[i]^j とすれば良いです(a*c + a*d + b*c + b*d = (a+b) * (c+d) みたいのと同じ考え方)。あらかじめ累積和を取っておけばこれは上と変わらない計算量で求められるので間に合います。
ll mod_pow(ll x, ll p, ll MOD) {
ll a = 1;
while (p) {
if (p%2) a = a*x%MOD;
x = x*x%MOD;
p/=2;
}
return a;
}
const int MAXN = 404;
const int MOD = 1e9+7;
int A[MAXN], B[MAXN];
int N, C;
ll memo[MAXN][MAXN];
ll sum[MAXN][MAXN];
ll dp[MAXN][MAXN];
ll dfs(int now, int rest) {
ll& ret = dp[now][rest];
if (ret >= 0) return ret;
if (now == N-1) {
//return ret = memo[A[now]][rest];
ret = sum[B[now]+1][rest] - sum[A[now]][rest];
ret = (ret%MOD+MOD)%MOD;
return ret;
}
ret = 0;
for (int i = 0; i <= rest; i++) {
//ll tmp = memo[A[now]][i];
ll tmp = sum[B[now]+1][i] - sum[A[now]][i];
tmp = (tmp%MOD+MOD)%MOD;
tmp *= dfs(now+1, rest-i);
(ret += tmp%MOD) %= MOD;
}
return ret;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXN; j++) {
memo[i][j] = mod_pow(i, j, MOD);
}
memset(sum, 0, sizeof(sum));
for (int i = 0; i < MAXN; i++) {
for (int j = 1; j < MAXN; j++) {
sum[j][i] = sum[j-1][i] + memo[j-1][i];
sum[j][i] %= MOD;
}
}
cin >> N >> C;
for (int i = 0; i < N; i++)
cin >> A[i];
for (int i = 0; i < N; i++)
cin >> B[i];
memset(dp, -1, sizeof(dp));
cout << dfs(0, C) << endl;
return 0;
}
