ARC035 C - アットコーダー王国の交通事情
解法
頂点数が小さいので，ワーシャルフロイドでよい．
ただし，建設するたびにワーシャルフロイドすると間に合わない．
よく考えると，x-y 間に橋を作ったときに最短経路が変わるのは，x-yを経由するという意味にほかならない．
すると，最短経路を更新するときは
d[i][j] = min(d[i][j], d[i][x] + d[x][y] + d[y][j])
のように，i -> x -> y -> j という経路だけ確認すれば良いことになる．
もちろん，i -> y -> x -> j の経路も確認する．
これは O(N^2) でできるので，クエリに対して O(KN^2) で求まる．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int INF = 1e9; int main() { int N, M; cin >> N >> M; vector<vector<int>> d(N, vector<int>(N, INF)); for(int i = 0; i < N; ++i) { d[i][i] = 0; } for(int i = 0; i < M; ++i) { int a, b, c; cin >> a >> b >> c; a--; b--; d[a][b] = min(d[a][b], c); d[b][a] = d[a][b]; } for(int k = 0; k < N; ++k) { for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } int K; cin >> K; while(K--) { int x, y, z; cin >> x >> y >> z; x--; y--; if(d[x][y] > z) { d[x][y] = d[y][x] = z; for(int i = 0; i < N; ++i) { for(int j = i + 1; j < N; ++j) { int t = d[i][x] + d[x][y] + d[y][j]; t = min(t, d[i][y] + d[y][x] + d[x][j]); d[i][j] = d[j][i] = min(d[i][j], t); } } } ll sum = 0; for(int i = 0; i < N; ++i) { for(int j = i + 1; j < N; ++j) { sum += d[i][j]; } } cout << sum << endl; } }
感想
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
これと一緒．AOJのほうは制約がちょっと違うからゴリ押せるんだけど．
ARC023 C - タコヤ木
解法
典型 of 典型みたいな問題．
L -1 -1 ... -1 R
みたいな区間に分けて考えて，R - L を -1 にうまく分配するという問題になる．
これはいわゆる重複組合せというやつ．高校数学でも頻出．
というか，
http://abc021.contest.atcoder.jp/tasks/abc021_d
これと全く同じ問題になる．
今回は A の値がでかいので，factテーブルを 10^5 まで持つとかはできないけど，区間が 2000 と小さいので nCr を愚直に求めていける．
逆元は，mod が素数だから分母を Y として Y^(p - 2) で求められる．（フェルマーの小定理）
あとは得られた値をそれぞれかけてやればOK．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; constexpr ll M = 1e9 + 7; ll modpow(ll x, ll n) { ll res = 1; while(n > 0) { if(n & 1) { res = (res * x) % M; } x = (x * x) % M; n >>= 1; } return res; } int main() { int N; cin >> N; vector<pii> v; int l = -1, r = -1; int cnt = 0; for(int i = 0; i < N; ++i) { int a; cin >> a; if(a != -1) { l = r; r = a; if(l != -1) { v.emplace_back(r - l + 1, cnt); cnt = 0; } } else { cnt++; } } ll res = 1; for(auto& p : v) { ll P = 1; for(int i = p.first + p.second - 1; i >= p.first; --i) { P = (P * i) % M; } ll Q = 1; for(int i = 1; i <= p.second; ++i) { Q = (Q * i) % M; } Q = modpow(Q, M - 2); P = (P * Q) % M; res = (res * P) % M; } cout << res << endl; }
感想
nCr 求めるときに n がでかいとびびっちゃうことがたまにある．
だいたい r が小さいので求められるやんけ！というところまでセット．
Codeforces Round #356 (Div. 1) B. Bear and Tower of Cubes
問題概要
整数 m があたえられる．m 以下の整数 X で，以下を満たす (n, X) を求める．
- X を超えない最大の a^3 （立方数）を選び，X = X - a^3 と更新する．
- X に対して上記の操作を繰り返す．
- 上記のように貪欲的に操作を繰り返すと，最終的に X がちょうど 0 になる．
- このとき，n を上記の操作を繰り返した回数とする．
- このような (n, X) は複数考えられるが，(n, X) は std::pair と見たときの最大値であるとする．つまり，まず n を最大化し，次に X を最大化する．
・制約
1 <= m <= 10^15
解法
求める解を f(m) とおく．
まず，a^3 <= m を満たす最大の a を求める．
実は，最適解は，この a^3 か (a - 1)^3 のどちらか一方を使っていくことで求められることがわかる．以下でそれを確認する．
1. a^3 を選んだ場合．次に f(m - a^3) を考えれば良い．
2. (a - 1)^3 を選んだ場合．次に f(a^3 - 1 - (a - 1)^3) を考えれば良い．m - (a - 1)^3 でないのは，a は貪欲的に選んでいかなければならないので，a^3 を選ばないためには a^3 未満である必要があるためである．a^3 未満で最大を考えるのが当然最適なので，a^3 - 1 を選択する．
3. (a - 2)^3 を選んだ場合．同様に f((a - 1)^3 - 1 - (a - 2)^3) を求めれば良い．しかし，これは case 2 を選ぶより悪い．なぜなら，それぞれ
- a^3 - 1 - (a - 1)^3 > (a - 1)^3 - (a - 2)^3
- n はともに 1 増加
- 使用した数（総和がXに該当）はそれぞれ(a - 1)^3，(a - 2)^3だけ増加
つまり，case2 のほうが，より大きな数を残しつつ X にもより大きい数を加えられる．
よって，case 1 か 2 を繰り返し選択して行くDFSが考えられる．
問題は深さがいくらになるか．
じつは，そんなに大きくならないことがわかる．
(a + 1)^3 - 1 - a^3 = 3a^2 + 3a より，一回の操作で m のオーダーが 2/3 乗に落ちるからである．
したがって，case1 または case2 を繰り返し選択していくDFSを書けば，十分速い解答になる．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll INF = 1e18; pair<ll, ll> solve(ll total, ll cnt, ll used) { if(total == 0) { return make_pair(cnt, used); } ll next = 1; while(pow(next, 3) <= total) { next++; } next--; auto res = solve(total - pow(next, 3), cnt + 1, used + pow(next, 3)); if(next > 0) { res = max(res, solve(pow(next, 3) - 1 - pow(next - 1, 3), cnt + 1, used + pow(next - 1, 3))); } return res; } int main() { ll m; cin >> m; auto res = solve(m, 0, 0); cout << res.first << ' ' << res.second << endl; }
感想
n はたかだか18らしい．
こういうのは実験すると見えるんだろうか．
典型ではないらしいが，本番で解いてる人多いし，頑張って通したい問題．
AGC004 D - Teleporter
解法
首都が自己辺でなければならないのは，すぐ分かる．（ぱっとわからなくても実験すればわかるようになってる．）
あとは制約から，与えられたグラフが首都を根とする木になっていることがわかる．
首都が自己辺であれば，首都から距離 K 以内であればOKという問題に変わるので，その方向で考える．
この場合，葉から考えて，高さ K-1 の部分木を切っていくイメージでやるとよいことがわかる．
根から高さを数えてしまうと，根からの距離が K の節点に大量の葉がついているケースで死んでしまって，僕みたいに時間を溶かすのでだめ．
それがわかればDFSやるだけで求められる．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int INF = 1e9; using graph = vector<vector<int>>; int N, K; int dfs(int v, int prev, graph const& g, int& res) { int h = 0; for(auto to : g[v]) { h = max(h, dfs(to, v, g, res) + 1); } if(h == K - 1 && prev != 0 && v != 0) { res += 1; h = -1; } return h; } int main() { cin >> N >> K; graph g(N); int res = 0; for(int i = 0; i < N; ++i) { int a; cin >> a; a--; if(i == 0) { res += a != 0; } else { g[a].push_back(i); } } dfs(0, -1, g, res); cout << res << endl; }
感想
根から高さ数えてて，死ぬケースもわかってたんだけど単純に葉から数えればいいという発想がなかった．
難しい問題解く前にこういう当たり前の（逆から考える）発想ができるようになりたい．
Codeforces Round #363 (Div. 1) C. LRU
解法
10^100なので実質無限大の時間がたったと考えて良い．
正規マルコフだし，十分大きな時間が経過したあとは定常状態に落ち着く．
この時，過渡状態にいる確率はほぼ0で，キャッシュは（できるかぎり）満杯になっていることになる．
以降，出来る限り満杯になるときのキャッシュサイズを K と再定義する．
つまり，最後から見て直近 K 種類のビデオがなにかわかればいい．
このように後ろから考えることによって，途中でLRUの機能によってキャッシュから取り除く操作を考える必要がなくなる．
さて，現在の瞬間にみるビデオは，過去に見たビデオに影響されない．
したがって，
「最後からみて（相異なる）直近 i 種類のビデオが v1, v2, ..., vi である確率」
は
「最初からみて（相異なる）直近 i 種類のビデオが v1, v2, ..., vi である確率」
と等しい．
これは，bitDPで求めることができる．
直近みたビデオの集合をビットで管理することにして，それを S で表す．
つまり，dp[S] := 最初から考えて，初めて popcount(S) 種類になったときそれが S である確率 とする．
S -> S | (1 << i) の遷移では
dp[S | (1 << i)] += dp[S] * p[i] / (1 - q)
となる．ただし，q は S に含まれるビデオの確率の総和である．
なぜなら，この遷移で問題になるのは，S に含まれないビデオの中で，次に見たものは一体何か？ということだからである．
各時刻で見るビデオは過去の状態に無関係だから，S 以外で次にビデオ i を見る確率は単純に p[i] / (1 - q) として良い．
あとは，popcount(S) == K となっているものを考えて，和を取ればOK．
・補足
K をできるかぎり満杯のキャッシュサイズとしたのは，完全に満杯にならない場合があるからである．
それは，n 種類の中に確率0のビデオがある場合である．
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; int cnt = 0; vector<double> p(n); for(int i = 0; i < n; ++i) { cin >> p[i]; cnt += p[i] == 0; } k = min(k, n - cnt); vector<double> dp(1 << n); dp[0] = 1; for(int S = 0; S < (1 << n); ++S) { if(__builtin_popcount(S) >= k) { continue; } double q = 0; for(int i = 0; i < n; ++i) { if((S >> i) & 1) { q += p[i]; } } for(int i = 0; i < n; ++i) { if((S >> i) & 1) { continue; } dp[S | (1 << i)] += dp[S] * p[i] / (1 - q); } } vector<double> res(n); for(int S = 0; S < (1 << n); ++S) { if(__builtin_popcount(S) == k) { for(int i = 0; i < n; ++i) { if((S >> i) & 1) { res[i] += dp[S]; } } } } for(int i = 0; i < n; ++i) { cout << fixed << setprecision(10) << res[i] << " \n"[i == n - 1] << flush; } }
感想
後ろからやる～っていうのは頻出でよく見るんだけど，普通に遷移がわからなかった．
最近簡単な数学ができなくなっていて反省．
Codeforces Round #326 (Div.1) E. Duff as a Queen
問題概要
n 個の数からなる数列 {a_n} が与えられる．
また，q 個のクエリが投げられるものとする．クエリは以下の2種類．
ただし，以降は + を XOR, * を AND とする．
1. l <= i <= r なるすべての i に対して，a_i = a_i + k と更新．
2. a_l, ..., a_r からいくつか任意に選んで（全く選ばなくても良い），それらのすべての XOR を w とする．異なる w は何種類作れるか？
・制約
1 <= n <= 2 * 10^5
1 <= q <= 4 * 10^4
解法
全くわからなかったので教えてもらった．どうやら典型らしい．
まず，大前提として，二元体 F_2 上の (F_2)^n は線形空間をなす．
次に，a_l, ..., a_r に対し，c_l * a_l + ... + c_r * a_r (ここで，c_i は0または1である) 全体が作る集合は，これまた線形空間となっている．これを V_lr とおく．
さて，2種類目のクエリをどう処理するかを考える．
じつは，これは V_lr の次元を求めることと同じである．V_lr の基底を e_1, ..., e_k とする．
(because: 任意の w は 当然 V_lr の元である．よって，w = d_1 * e_1 + ... + d_k * e_k と「一意的に」表せる．一意性から，各 d_i の割り当てに対し，それぞれ1つの「異なる」 w が対応する．当然これが求めたいすべての w になる．各
d_i の割り当て方は2通りなので，全体として 2^k 通りの w が存在し，これが求める答えである．)
また，次元はたかだか32であることに注意する．（これは明らか）
さらに，1つ目のクエリをうまく処理しよう．
ここで，b_i := a_{i-1} + a_i とおく．この時，{a_l, b_{l+1}, ..., b_r} の基底は，{a_l, ..., a_r} の基底にもなっている．
(because: a_l + b_{l+1} = a_{l+1} であり，これを順番に繰り返せば，{a_l, ..., a_r} が生成できる．逆も当然可能．よって基底が一致する)
クエリ1が投げられたとき，この数列 b_n 上にどう影響するか考える．すると，実は区間の端だけ考えれば十分である事がわかる．なぜなら，区間の途中では，(a_i + k) + (a_{i+1} + k) = a_i + a_{i+1} となって相殺されるからである．
以上で得られたことをまとめる．
まず基底に関して，各区間における基底をセグメント木によって管理する方針が立つ．基底はたかだか32個しかないから，各ノードにすべての基底を保持しても問題ない．
基底のマージの仕方は，ガウスの消去法っぽくやる．すでに得られている基底に対して，別の基底の1要素 a を追加するとき，1が立っている最下位に注目する．
ただし，基底の任意の1要素 v に関して，v の1のビットの最下位では，v 以外の要素は 0 になっているものとする．（つまり，その位のビットを立てられるのは v のみ．）
各 v の最下位ビットを用いて a のビットをおろしていったとき，最終的に a が 0 でなければ，明らかに a は他の要素と直交しているので，新しい基底に含んで良い．
あとは，a の最下位の1のビットについて，先の基底の仮定を満たすように，各 v のビットをおろしていく（このとき，a は v の最下位の1ビットに影響しないことに注意）．
最後に a を追加する．この手順を繰り返せばOK．
・クエリ1について
{b_n} を考えるにしても，基底を考えるときに結局 {a_n} は必要なので，これはうまく求める必要がある．遅延セグメント木でも良さそうだが，実はBITで求められる．
最初に {a_n} の入力を取ったときに，BIT上の i 番目と i+1 番目に a_i を加えてやれば，sum(i) + sum(i-1) = a_i とできる．
あとは，
bit.add(l, k);
bit.add(r, k);
とすれば，sum(i) - sum(i-1) として k を xor したあとの a_i が得られる．
また，端に対応する b_i について，セグメント木のノードを更新する．
・クエリ2について
セグメント木上で [l+1, r) の区間の基底（つまり b_{l+1}, ..., b_r の基底）と，a_l を用いて，この区間の基底を求める．
基底のマージの仕方は先に述べた．
あとはこうして得られた基底から次元がわかるので，2^(次元) を出力すればよい．
ソースコード
長いので一部省略している．
#include <bits/stdc++.h> using namespace std; // segment_tree および fenwick_tree は省略 void binary_basis_insert(vector<int>& w, int a) { for(auto v : w) { if(v & (-v) & a) { a ^= v; } } if(a == 0) { return; } for(auto& v : w) { if(a & (-a) & v) { v ^= a; } } w.push_back(a); } vector<int> binary_basis(vector<int> const& w) { vector<int> res; for(auto v : w) { binary_basis_insert(res, v); } return res; } struct binary { using type = vector<int>; static type id() { return type(); } static type op(type l, type r) { if(l.size() < r.size()) { swap(l, r); } for(auto v : r) { binary_basis_insert(l, v); } return binary_basis(l); } }; int main() { int n, q; cin >> n >> q; vector<int> a(n); fenwick_tree<int> bit(n + 1); for(int i = 0; i < n; ++i) { cin >> a[i]; bit.add(i, a[i]); bit.add(i + 1, a[i]); } vector<int> b(n); for(int i = 1; i < n; ++i) { b[i] = a[i - 1] ^ a[i]; } vector<vector<int>> init(n); for(int i = 0; i < n; ++i) { init[i].push_back(b[i]); } segment_tree<binary> seg(init); for(int i = 0; i < q; ++i) { int t; cin >> t; if(t == 1) { int l, r, k; cin >> l >> r >> k; l--; bit.add(l, k); bit.add(r, k); seg.update(l, {bit.sum(l) ^ bit.sum(l - 1)}); if(r < n) { seg.update(r, {bit.sum(r) ^ bit.sum(r - 1)}); } } else { int l, r; cin >> l >> r; l--; auto res = seg.query(l + 1, r); binary_basis_insert(res, bit.sum(l)); cout << (1LL << res.size()) << endl; } } }
ARC006 C - 積み重ね
解法
貪欲解で解くひとが多いと思うので，それ以外の解法を．
この問題は，よく考えると「与えられたDAGの最小パス被覆を求めよ」と言い換えられる．
実際，x が y の上に積める，を y -> x という有向辺として表現すれば，DAGができる．
DAGの最小パス被覆は，頂点数からDAGを2部グラフと見たときの最大マッチングの数を引いたものである．
しかし，圧倒的に貪欲のほうが楽ではある．（自分はパット見てマッチングに帰着させてしまったけど．）
ソースコード
#include <bits/stdc++.h> using namespace std; using graph = std::vector<std::vector<int>>; // bipartite_matching は略． int main() { int N; cin >> N; vector<int> w(N); for(int i = 0; i < N; ++i) { cin >> w[i]; } graph g(N*2); for(int i = 0; i < N; ++i) { for(int j = i + 1; j < N; ++j) { if(w[i] >= w[j]) { g[i].push_back(j + N); } } } cout << N - bipartite_matching(g) << endl; }
