Constant Sum | CS Academy #30 (Div. 2 only)
更新の操作は以下のように表せる。
A[i]+=s
A[j]+=-s/(N-1), j!=i
前者を変形すれば
A[i]+= (s+s/(N-1)) -s/(N-1)
となる。なので
全体に-s/(N-1)を加算し、A[i]にs+s/(N-1)を加算したとすれば、1クエリO(1)で処理できる。
Educational Codeforces Round 21 D: Array Division
n=1のとき明らかにNO
よってn>=2とする。
とりあえず、挿入は考えずに配列を前の部分(S)と後の部分(T)に分けてみる。ただし、S,Tは空であってもよいとする。
z=Σ[x∈S](x), w=Σ[y∈T](y)とする。
場合1. z=wの場合
ある要素を選んで同じ場所に挿入すればいいからYES
場合2. z>wの場合
Sから値vを取り除いてTに挿入したときに和が等しくなればYES
すなわち
z-v = w+vより
v = (z-w)/2としてv∈SならばYES
場合3. w>zの場合
場合2.と同様
S,Tはすべて試す。つまり、全ての前の部分の長さ(後ろの部分の長さ)を総当りで固定して、上記のチェックをすればいい。
Educational Codeforces Round 21 E: Selling Souvenirs
エディトリアル見て書いたコード。コメントつき
/* エディトリアルのとおりの解法 */ /* 重さ1, 2のsouvenirだけを使ったとき、重さの和がiとする。 このときdp[i]=(x,y,z)は以下の意味。 xはコストの和の最大値 yは重さ1のsouvenirをいくつ使ったか。 zは重さ2のsouvenirをいくつ使ったか。 インデックスのほうにy,zのような情報を持たせないで、最適値の後ろにくっつけてる。 */ tuple<ll, int, int> dp[300001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vll weight(N), cost(N); rep(i, N) { cin >> weight[i] >> cost[i]; } // 重さの種類は3種類しかないのでバケツソートしておく。 vll costByWeight[4]; rep(i, N)costByWeight[weight[i]].push_back(cost[i]); // とりあえず、コストの大きい方から使いたいのでソートしておく。 rep(i, 4)sort(costByWeight[i].rbegin(), costByWeight[i].rend()); FOR(i, 1, M + 1)dp[i] = mt(-1ll, -1, -1); rep(i, M) { ll sumCost; int cnt1, cnt2; tie(sumCost, cnt1, cnt2) = dp[i]; if (sumCost == -1)continue; if (cnt1 < sz(costByWeight[1])) { smax(dp[i + 1], mt(sumCost + costByWeight[1][cnt1], cnt1 + 1, cnt2)); } if (cnt2 < sz(costByWeight[2]) && i + 2 <= M) { smax(dp[i + 2], mt(sumCost + costByWeight[2][cnt2], cnt1, cnt2 + 1)); } } /* maxCost[i]は1,2の重さのsouvenirだけ使ったとき、重さの和がi以下である場合のコストの最大値 */ vector<ll> maxCost(M + 1); rep(i, M) { maxCost[i + 1] = max(maxCost[i], get<0>(dp[i + 1])); } // sumThreeは重さ3のsouvenirのコストの和 ll answer = 0, sumThree = 0; // 重さ3のsouvenirのコストを総当りで固定する for (int i = 0; i <= M && i / 3 <= sz(costByWeight[3]); i += 3) { // 事前に計算したDPをうまく使って、解を更新する smax(answer, sumThree + maxCost[M - i]); if (i / 3 < sz(costByWeight[3])) { sumThree += costByWeight[3][i / 3]; } } cout << answer << endl; }
Educational Codeforces #21 G: Anthem of Berland
上図は3番目の入力例の文字列t="abcab"にダミーの1文字を加えたt+'#'="abcab#"に対してKMP法のDFAを描いたもの。!はその他の文字を表す。
tはオーバーラップしてもよいので、最終状態からの遷移もほしい。そこで、末尾にダミーの文字を加えた。これにより、最終状態からの遷移も得られた。
例えば
abcabと最後まで一致した後、
cが来た場合
接頭辞abcと一致するはず。実際、上図でそのような遷移が得られる。
|s|*|t|<=10^7という特殊な制約に注意しよう。
これにより、KMP法の計算以外ではO(|s|*|t|)の実行時間が許されている。
dp[i][j]を「Sの文字列をi番目まで確定していてDFA上で状態がjであるときの、DFA上のダミーでない最終状態に到達した回数の最大値」
とすれば、max(dp[|s|][j])が解。
Codeforces #413 E: Aquarium decoration
解説付きコード
/* 解説 二人とも好むアイテムの集合をX, MashaだけのはY, ArkadyだけのはZとする 全体でちょうどm個でなければならないが、とりあえずそのことは考えない。 Xからx個選ぶとする。xは|X|から0まで総当りする。 k-x個だけYとZから取る必要があるので取る。 ただし、YまたはZからk-x個取れない場合があるが、このとき条件を満たさない。 YとZから取った個数をy, zとする。ただし、y=z 明らかに x+y+z<=m である必要がある。 逆にこの時、残ったアイテムからm-(x+y+z)個を安い方から貪欲に取ればいい。 m-(x+y+z)個のアイテムの値段の和を得るために Binary Indexed Treeを使う。 BIT を2個もちそれぞれcnt, sumとする。 アイテムが価格順であるとき、 cnt: クエリ[l, r)に対して[l, r)のうち残っているのはいくつあるか sum: クエリ[l, r)に対して[l, r)のうち残っているものの値段の和 とする。 xは降順なので1個ずつcntとsumを調整できる。 また、xを降順に見ていったとき、y,zは昇順であることに注意すると cnt,sumに対する更新はO(N)回で済む。 二分探索で cntに対するクエリがm-(x+y+z)となるようなクエリ[0, p)を満たすpを求めれば、 m-(x+y+z)個の価格の和をsumに対してクエリ[0, p)を投げて求められる。 実行時間 O(n(log(n))^2) */ int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, M, K; cin >> N >> M >> K; vector<pair<ll,int> > C(N); vi A(N), id(N); rep(i, N) { cin >> C[i].first; C[i].second = i; } // 値段は安い方を優先して使いたいので昇順ソート sort(all(C)); vll cf(N); // ソート後のコスト、インデックス rep(i, N)cf[i] = C[i].first; rep(i, N)id[C[i].second] = i; for (int a : {1, 2}) { int t, x; cin >> t; while (t--) { cin >> x; --x; A[id[x]] |= a; } } vi X, Y, Z, DUMMY; rep(i, N) (A[i] == 3 ? X : A[i] == 2 ? Y : A[i] == 1 ? Z : DUMMY).push_back(i); // 集合X, Y, Zからいくつ選んだもののコストの和 ll cur = 0; each(x, X)cur += cf[x]; ll ans = LLONG_MAX; BIT cnt(N), sum(N); // Xに含まれないものをBITに加える rep(i, N)if (A[i] != 3) { cnt.add(i, 1); sum.add(i, cf[i]); } // 二分探索判定用 int need = -1; auto f = [&](int m) { return cnt.sum(m) >= need; }; auto g = [&](vi &W, int w, int a) { cur += a*cf[W[w]]; cnt.add(W[w], -a); sum.add(W[w], -a*cf[W[w]]); }; int y = 0, z = 0; for (int x = sz(X); x >= 0; --x) { // Xからx個選ぶ // YからK-x個以上選ばなければならない。 while (x + y < K && y<sz(Y)) g(Y, y++, +1); // ZからK-x個以上選ばなければならない。 while (x + z < K && z < sz(Z)) g(Z, z++, +1); // MashaかArkadyは不満足 if (x + y < K || x + z < K)break; // x+y+z>Mとすると多すぎて駄目 if (x + y + z <= M) { // あとM-x-y-z個必要 need = M - x - y - z; if (need == 0)smin(ans, cur); else { int w = binarySearchR(0, N, f); smin(ans, cur + sum.sum(w)); } } if (x) g(X, x - 1, -1); } cout << (ans != LLONG_MAX ? ans : -1) << endl; }
Codeforces #413 C: Fountains
解説付きコード
/* 解候補は4種類ある。 何も買わない コインとダイヤモンドでそれぞれ1個ずつ噴水を買う コインで2個噴水を買う ダイヤモンドで2個噴水を買う 前二者は自明 後二者について 噴水をコインで2個買うとする 安い方の必要なコイン数を固定すると、 使える残りのコイン数が決まる。 そのコインの数以下で変える最大の美しさを持つ噴水も確定する。 よって、安い方の噴水を昇順で固定して、 それより安い噴水と高くて買えない噴水を候補から外す。 */ /* コインだけ、もしくはダイヤモンドだけで2個の噴水を買いたい */ int f(vector<pii> &a, int m) { // price_beauty, beauty_price // 前者は値段で、後者は美しさで // 最大値、最小値を取得できる multiset<pii> p_b, b_p; auto g = [&](int p, int b) { // multisetの削除はイテレータを使うこと // そうでないと重複要素をすべて削除してしまう。 p_b.erase(p_b.find(mp(p, b))); b_p.erase(b_p.find(mp(b, p))); }; rep(i, sz(a)) { p_b.insert(a[i]); b_p.insert(mp(a[i].second,a[i].first)); } int res = 0; while (sz(p_b) > 1) { int p1, b1; // 安い方の噴水の値段,美しさ tie(p1, b1) = *p_b.begin(); if (p1 > m)break; // この噴水を解候補から削除 g(p1, b1); // あとlimコインだけ使える int lim = m - p1; // 高すぎる噴水を削除 while (sz(p_b) && p_b.rbegin()->first > lim) { int p, b; tie(p, b) = *p_b.rbegin(); g(p, b); } if (sz(p_b) == 0)break; // 買える噴水のうち最も美しいもの int b2 = b_p.rbegin()->first; smax(res, b1 + b2); } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, C, D; cin >> N >> C >> D; vector<pii> cs, ds; int mac = 0, mad = 0; rep(i, N) { int b, p; char c; cin >> b >> p >> c; if (c == 'C') { cs.emplace_back(p, b); if (p <= C) { // ここをmac=bとしてしまった smax(mac, b); } } if (c == 'D') { ds.emplace_back(p, b); if (p <= D) { // ここをmad=bとしてしまった smax(mad, b); } } } int ans = 0; // 何も買わない場合がある if (mac > 0 && mad > 0)ans = mac + mad; // コインとダイヤモンドを両方使う場合 // コインだけ、もしくはダイヤモンドだけ smax(ans, max(f(cs, C), f(ds, D))); cout << ans << endl; }
Codeforces #413 D: Field expansion
まずa[i]は大きい方を優先して使ったほうがいいので降順にソートしておく。
2^17>10^5かつa[i]>=2より
掛け算は縦横合わせてたかだか17+17=34回
よって
f[i番目までは掛けた][横の長さ]=縦の長さの最大値
をDPで解けばいい。