列全体から計算される値を部分的な要素の更新の度に計算する実装パターン
こどふぉ頻出です．大体やるだけなんだけどバグらせないようにしたいという記事です
次の問題を考えます
http://codeforces.com/contest/1467/problem/B
概要: 数列 $a$ が与えられるので「 $a_{i -1} < a_i > a_{i + 1}$ または $a_{i - 1} > a_i < a_{i + 1}$ 」が成り立つ $i$ の個数を考えたときに，高々一回好きな位置の値を好きな値に変えれるのでその個数を最小化してください
少し考えるとある値を変更する場合はその隣り合う数のどちらかと同じ値に変更してしまうことにしてよいことがわかります．また，変更によって影響が及ぶのは変更した値とその隣り合う二つの数だけなので変更なしの計算結果との差分をとればいいです
実装では次の二つを用意します
A. ある位置を受け取って条件をそのまま記述してその結果を返します．このとき区間範囲外の位置も受け付けて適切な値を返すようにしておくと残りの実装をより脳死でできるのでそのようにする
B. ある区間を受け取ってその区間の各位置について A を計算してその結果を返す
これを使って次のようなことをします
C. まず変更なしの計算は区間全体を B に渡せばよくて，これを val とします．次に各変更について考えます．ある位置の変更に対してその影響が及ぶ区間をとって変更前の状態でその区間を B に渡してその結果を val から引きます．そのあと変更後の状態で同じ区間を B に渡してその結果を val に足します．これが変更後の結果になります
これの嬉しさは変更の位置や種類等に関心を持つ必要がない点です
具体的な実装は次のようにしました
A
int calc_at_point(const vector<int> &a, int idx) { int n = a.size(); if (idx > 0 && idx < n - 1) { if (a[idx - 1] > a[idx] && a[idx] < a[idx + 1]) { return 1; } if (a[idx - 1] < a[idx] && a[idx] > a[idx + 1]) { return 1; } } return 0; };
B
int calc_at_range(const vector<int> &a, int l, int r) { int res = 0; for (int i = l; i <= r; i ++) { res += calc_at_point(a, i); } return res; }
C
int val = calc_at_range(a, 0, n - 1); int ans = val; rep(i, n) { int o = a[i]; for (int d = -1; d <= 1; d += 2) { if (0 <= i + d && i + d < n) { int t = val; t -= calc_at_range(a, i - 1, i + 1); a[i] = a[i + d]; t += calc_at_range(a, i - 1, i + 1); a[i] = o; ans = min(ans, t); } } } cout << ans << '\n';
似たような問題をもう一つ考えます
http://codeforces.com/contest/1420/problem/c2
概要: 数列 $a$ が与えられるので，そこから好きな部分列をとってそれを $b$ としたときに $b_0 - b_1 + b_2 - b_3 + ... $ の値が最大になるようにしてください．ただしある $l, r$ について $a_l$ と $a_r$ を swap してくださいというクエリを順に処理しながらその都度最大値を求めてください
行列をデータ構造にのせて解くこともできると思いますが，ここでは別の解き方をします．まずよく考えると実は + として使う数というのは必ず $a_{i - 1} < a_i > a_{i + 1}$ を満たす $a_i$ であるということが言えます．証明としては，仮に $a_{i - 1} \geq a_i$ なときに $a_i$ を + として使うのだとすると $a_{i - 1}$ は使わないか - として使うかのどちらかになりますが， もし使わないなら $a_i$ ではなく $a_{i - 1}$ を + として使った方が損することはないです．もし - として使うなら， $a_i$ も $a_{i - 1}$ もどちらも使わないとする方が損することはないです．よってこのような構造はないと思って良いことがわかってこれは右側についても言えるので，言えました．同様にして - として使う数は必ず $a_{i - 1} > a_i < a_{i + 1}$ を満たす $a_i$ であることも言えて，逆に以上の条件を満たすものは全部 +/- として使って損はしないので，そのようなものの総和をとる問題になりました
最初の問題とほとんど同じように次のような実装ができます（ただし l と r の距離が近い場合は独立に計算しようとすると差分が二回計算されたりして壊れるのでまとめて一つの区間で計算しています）
A
int calc_at_point(const vector<int> &a, int idx) { int n = a.size(); if (idx < 0 || n <= idx) { return 0; } bool add = true, sub = true; if (idx == 0 || idx == n - 1) { sub = false; } if (idx > 0) { add = add && a[idx - 1] < a[idx]; sub = sub && a[idx - 1] > a[idx]; } if (idx < n - 1) { add = add && a[idx + 1] < a[idx]; sub = sub && a[idx + 1] > a[idx]; } if (add) { return a[idx]; } else if (sub) { return -a[idx]; } else { return 0; } }
B
ll calc_at_range(const vector<int> &a, int l, int r) { ll res = 0; for (int i = l; i <= r; i ++) { res += calc_at_point(a, i); } return res; }
C
ll ans = calc_at_range(a, 0, n - 1); cout << ans << '\n'; while (q --) { int l, r; cin >> l >> r; l --, r --; if (r - l >= 5) { ans -= calc_at_range(a, l - 1, l + 1); ans -= calc_at_range(a, r - 1, r + 1); swap(a[l], a[r]); ans += calc_at_range(a, l - 1, l + 1); ans += calc_at_range(a, r - 1, r + 1); } else { ans -= calc_at_range(a, l - 1, r + 1); swap(a[l], a[r]); ans += calc_at_range(a, l - 1, r + 1); } cout << ans << '\n'; }
Codeforces Round #693 (Div. 3)
http://codeforces.com/contest/1472
A: $2^{ctz(h)} * 2^{ctz(w)}$ 個に分かれます
B: 次の順で判定します．sum が奇数なら no，1 が一個以上あれば yes，n が奇数なら no，あとは yes
C: 思考停止メモ化したけど後ろから決めていけばいいです
D: あくまで勝つことが目標なので大きい数は「自分がとる」と「相手にとらせないようにする」が同様に嬉しいので，両者とも偶奇を無視して大きいものからとっていくのが最適です
E: h でソートして w の累積 min をとっておくとかでできます（自分自身と条件を満たすペアになることはないので区間 min とかでやる必要はない）
F: 2 * 2 の無のグリッドは消せるので座圧して dp します
G: 一回しか使えない移動は使うなら一番最後に使うので変なことを考えずに dp できます
数列上の数の組み合わせであって不等式を満たすものの数を数える
まず数列 $a$ の転倒数を求める問題を考えます
より正確には $i < j$ を満たす組 $(i, j)$ であって $a_i > a_j$ となるようなものの数を求める問題で，これは fenwick tree などのデータ構造を使って以下のように解けます
fenwick_tree<long long> ft(MAX); long long ans = 0; rep(i, n) { ans += ft.sum(a[i] + 1, MAX); ft.add(a[i], 1); }
まず今見ている値を不等式の右辺の値として計算結果に加算して，次に今後その値が不等式の左辺としてどれくらい結果に寄与するかというのを考えているだけです
ところで上記を踏まえると，一般に次のような問題が同様に解けます
$i < j$ を満たす組 $(i, j)$ であってなんらかの制約 $f, g$ について $f(i) > g(j)$ *1 を満たすようなものの数を求めよ
（例題: https://codeforces.com/contest/1324/problem/D）
fenwick_tree<long long> ft(MAX); long long ans = 0; rep(i, n) { ans += ft.sum(g(i) + 1, MAX); ft.add(f(i), 1); }
(ただし必要に応じて $f, g$ のとりうる値を列挙しておいて自然数に座圧する）
また，より一般に $idx_0 < idx_1 < ... < idx_k$ を満たす $idx$ であって $i = 0, 1, ..., k - 1$ に対するなんらかの $f, g$ を用いた制約 $f_i(idx_i) > g_i(idx_{i + 1})$ を満たすようなものの数を求めることもできて，これは fenwick tree を $k$ 本用意して，各制約ごとに上記とほとんど同様のことをやれば良いです
*1:不等式の向きは $>$ としていますが， $f, g$ を適当に定めればそのようにできるからそう書いているだけであって大小関係について言及しているわけではありません
狭義単調増加な整数列を広義単調増加な整数列として扱う
http://codeforces.com/contest/1437/problem/E の部分問題を考えます
概要としては，ある整数列 $a$ が与えられ，「要素を一つ選び，任意の整数に置き換える」という操作を繰り返して $a$ を狭義単調増加な数列に変えるために必要な操作回数の最小値を求める問題です
例えば $a = \{3, 4, 4, 7, 9, 8, 10, 11\}$ なら三回の操作で $a = \{3, 4, 5, 7, 8, 9, 10, 11\}$ とできてこれが最小回数です
自明な考察としてそのまま（狭義） $LIS$ をとってそれ以外に対して操作をするということが考えられますが，これだとうまくいきません．理由は $a_i$ を $x$ に変更すると狭義単調増加な状態を保つために， $a_{i - 1} < x$ と $a_{i + 1} > x$ という制約がつくことになってこれを考慮できないからです．上の例だと $LIS$ の一つをとってそれ以外を $?$ で置き換えると $\{3, 4, ?, 7, 9, ?, 10, 11\}$ になりますが二個目の $?$ に入る数は存在しません
そこで $b_i = a_i - i$ となる数列 $b$ を考え， $a$ が狭義単調増加であることと $b$ が広義単調増加であることが同値であることを利用します．数列 $b$ の上では各要素同士の距離を考慮しなくてよくなるので，数列 $b$ で（広義） $LIS$ をとれば答えが分かります．上の例だと $b = \{3, 3, 2, 4, 5, 3, 4, 4\}$ となって $\{3, 3, ?, 4, ?, ?, 4, 4\}$ などがとれて，この $?$ が適当な数で置き換えられないということはありえません
AGC 028 D. Chords
まず円を直線上に展開することに気付くと，区間を $N$ 個とる問題になって区間 $dp$ っぽいことができそうな気持ちになります．連結成分を適当に分けてそれぞれ独立に数え上げることができればよさそうなことから自然に $dp(l, r) :=$ 区間 $[l, r]$ を被覆する連結成分の数 が生えて，これは $O(N^3)$ で計算できるので，これで解けました
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++) using namespace std; int main() { int n, k; scanf("%d%d", &n, &k); vector<int> p(2 * n, -1); rep(i, k) { int a, b; scanf("%d%d", &a, &b); a --, b --; p[a] = b; p[b] = a; } vector<vector<long long>> tozan(2 * n, vector<long long> (2 * n)); rep(i, 2 * n) { rep(j, 2 * n) { for (int l = i; l <= j; l ++) { tozan[i][j] += (p[l] == -1); } } } const long long mod = 1e9 + 7; vector<vector<long long>> gezan(2 * n, vector<long long> (2 * n)); rep(i, 2 * n) { rep(j, 2 * n) { if (tozan[i][j] % 2 == 0) { gezan[i][j] = 1; for (long long l = tozan[i][j] - 1; l > 0; l -= 2) { (gezan[i][j] *= l) %= mod; } } } } vector<vector<long long>> dp(2 * n, vector<long long> (2 * n)); vector<long long> hoge; long long ans = 0; for (int d = 1; d < 2 * n; d ++) { rep(l, 2 * n) { int r = l + d; if (r >= 2 * n) break; bool ng = false; for (int m = l; m <= r; m ++) { if (p[m] != -1 && (p[m] < l || r < p[m])) { ng = true; break; } } if (tozan[l][r] % 2 == 1) ng = true; if (ng) continue; dp[l][r] = gezan[l][r]; for (int m = l + 1; m < r; m ++) { (dp[l][r] -= dp[l][m] * gezan[m + 1][r] % mod) %= mod; (dp[l][r] += mod) %= mod; } long long rem = (l > 0 ? tozan[0][l - 1] : 0) + (r < 2 * n - 1 ? tozan[r + 1][2 * n - 1] : 0); long long unko = 1; for (long long m = rem - 1; m > 0; m -= 2) (unko *= m) %= mod; (ans += dp[l][r] * unko % mod) %= mod; } } printf("%lld\n", ans); return 0; }
AGC 032 E. Modulo Pairing
まず $mod\ M$ の制約を無視して考えると，数直線状で交差する二つのペアや独立したペアをとっても得することはないのでペアをすべて入れ子状にしたものが最適解の一つになります．元の問題でこれが成り立つのはいずれのペアも $x + y < m$ であるか $x + y >= m$ であるかのどちらかなのでペアをこの $2$ 種類に分けるとよさそうで，種類の異なる二つのペアの関係は $x + y - (y + Y - m) > 0$ などから左右に独立に切り離せることがわかって，以上の操作を繰り返すと左右に入れ子状のペアが並んだ形に帰着されるので，あとは適当な探索によってこの境界を決定できて，解けました
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++) using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); vector<int> a(2 * n); rep(i, 2 * n) scanf("%d", &a[i]); sort(a.begin(), a.end()); int lb = -1, ub = n; while (ub - lb > 1) { int mid = (ub + lb) / 2; bool ok = true; mid *= 2; for (int i = mid; i < mid + (2 * n - mid) / 2; i ++) { if (a[i] + a[2 * n + mid - i - 1] < m) { ok = false; break; } } if (ok) ub = mid / 2; else lb = mid / 2; } int b = ub * 2; int ma = 0; for (int i = 0; i < b / 2; i ++) ma = max(ma, a[i] + a[b - 1 - i]); for (int i = b; i < b + (2 * n - b) / 2; i ++) ma = max(ma, (a[i] + a[2 * n + b - i - 1]) % m); printf("%d\n", ma); return 0; }
AGC 031 C. Differ by 1 Bit
動く回数は必ず $2^N - 1$ 回なので $a$ と $b$ の立っている $bit$ の個数の偶奇は異なることが必要です．$0...$ から $1...$ などにはきれいに移動できるので自然に分割統治をしたくなります．頂点 $S$ と $T$ が今見ている部分の半分に含まれているかどうかで場合分けをすると帰納法によって経路 $S → T$ が必ずとれることがわかるので，これで解けました
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++) using namespace std; vector<int> dfs(int left, int len, int s, int t) { assert(__builtin_popcount(s) % 2 != __builtin_popcount(t) % 2); if (len == 2) { return vector<int>{ s, t }; } int m = left + len / 2; bool swapped = false; if (s > t) { swap(s, t); swapped = true; } if (s < m && m <= t) { int u = left; while (__builtin_popcount(u) % 2 == __builtin_popcount(s) % 2) { u ++; } assert(u < m); int uu = u + len / 2; auto l = dfs(left, len / 2, s, u); auto r = dfs(m, len / 2, uu, t); for (auto it : r) { l.push_back(it); } assert(l.size() == len); if (swapped) { reverse(l.begin(), l.end()); } return l; } else { vector<int> res; if (s < m && t < m) { auto l = dfs(left, len / 2, s, t); int u = l[1]; int uu = u + len / 2; int ss = s + len / 2; auto r = dfs(m, len / 2, ss, uu); res.push_back(s); for (auto it : r) { res.push_back(it); } for (int i = 1; i < l.size(); i ++) { res.push_back(l[i]); } } else { auto r = dfs(m, len / 2, s, t); int u = r[1]; int uu = u - len / 2; int ss = s - len / 2; auto l = dfs(left, len / 2, ss, uu); res.push_back(s); for (auto it : l) { res.push_back(it); } for (int i = 1; i < r.size(); i ++) { res.push_back(r[i]); } } assert(res.size() == len); if (swapped) { reverse(res.begin(), res.end()); } return res; } } int main() { int n, a, b; scanf("%d%d%d", &n, &a, &b); if (__builtin_popcount(a) % 2 == __builtin_popcount(b) % 2) { puts("NO"); return 0; } puts("YES"); auto ans = dfs(0, (1 << n), a, b); assert(ans.size() == (1 << n)); rep(i, ans.size()) { printf("%d ", ans[i]); } printf("\n"); return 0; }
