Codeforces Round #407 (Div. 2) D. Weird journey
解法
まず，同じ辺を2回通るパスという時点でオイラーツアーが思い浮かびます．
自己辺を考えるのはめんどうなので，とりあえずない場合を考えると，条件を満たすパスがあるかどうかは，「一度のDFSによって辿れる頂点の次数の総和が，辺の個数 m の2倍になっている」ことと同値である（よね？）とわかります．
この時，隣接する任意の2つの辺について，それら2つを1回だけ通り，その他の辺を2回通るパスが明らかに存在します．
なので，この隣接する2辺のペアを適当に求めます（1つの頂点に着目して，出てる辺から2つ選べば良いです）．
最後に自己辺ですが，まあ実験すればすぐわかるんですけど，こいつらは自由に使えます．
なので，最後に 自己辺の数 * (自己辺を除くその他の辺) + (自己辺から2つ選ぶ選び方) を足してやれば解けます．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using graph = vector<vector<int>>; int dfs(graph const& g, int v, int p, vector<bool>& used) { int res = g[v].size(); used[v] = true; for(auto to : g[v]) { if(to == p || used[to]) { continue; } res += dfs(g, to, v, used); } return res; } int main() { int n, m; scanf("%d %d", &n, &m); graph g(n); int root = -1; vector<vector<int>> v(n); int self_cnt = 0; for(int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); a--; b--; root = a; if(a == b) { g[a].push_back(a); self_cnt++; } else { g[a].push_back(b); g[b].push_back(a); v[a].push_back(i); v[b].push_back(i); } } vector<bool> used(n); if(dfs(g, root, -1, used) + self_cnt != 2 * m) { printf("0\n"); } else { ll res = 0; for(auto x : v) { if(x.size() != 0) { res += x.size() * (x.size() - 1) / 2; } } res += self_cnt * (m - self_cnt); res += self_cnt * (self_cnt - 1) / 2; printf("%lld\n", res); } }
感想
あくまで辺を頂点と見たグラフが連結であればよいので，頂点自体が連結である必要はないです（罠）．
あと入力が 10^6 だったのを忘れて cin で TLE 食らってしまった．
Codeforces Round #404 (Div.2) E. Anton and Permutation
解法
平方分割 + 2次元BITで解いた．[0...m] x [0...n] で二次元．m は n / sqrt(n)．
l[i] から r[i] の間に完全に含まれているブロックは BIT 上で計算し，端っこの部分は生で持っている配列を使って計算する．
bit.sum(lb, a, rb, b) とすると lb から rb - 1 までのブロックにおける [a..b) の数を求められる．
計算量は O(Q * (sqrt(N) + log^2(N)))．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <typename T> class fenwick_tree2d { public: fenwick_tree2d(int h, int w) : H(h), W(w), dat(H, std::vector<T>(W)) {} void add(int i, int j, T value) { for(; i < H; i |= i + 1) { int jj = j; for(; jj < W; jj |= jj + 1) { dat[i][jj] += value; } } } // [0..i] x [0..j] T sum(int i, int j) const { T res = 0; for(; i >= 0; i = (i & (i + 1)) - 1) { int jj = j; for(; jj >= 0; jj = (jj & (jj + 1)) - 1) { res += dat[i][jj]; } } return res; } // [i1...i2) x [j1...j2) T sum(int i1, int j1, int i2, int j2) const { return sum(i2 - 1, j2 - 1) - sum(i1 - 1, j2 - 1) - sum(i2 - 1, j1 - 1) + sum(i1 - 1, j1 - 1); } private: int const H, W; std::vector<std::vector<T>> dat; }; int main() { int n, q; cin >> n >> q; vector<int> l(q), r(q); for(int i = 0; i < q; ++i) { cin >> l[i] >> r[i]; l[i]--; r[i]--; if(l[i] > r[i]) { swap(l[i], r[i]); } } vector<int> a(n); for(int i = 0; i < n; ++i) { a[i] = i; } int const B = sqrt(n) + 1; fenwick_tree2d<int> bit(n / B + 1, n); for(int i = 0; i < n; ++i) { bit.add(i / B, i, 1); } ll inv = 0; for(int i = 0; i < q; ++i) { if(l[i] != r[i]) { int lb = l[i] / B, rb = r[i] / B; if(lb + 1 < rb) { int l_lt = bit.sum(lb + 1, 0, rb, a[l[i]]); int l_gt = bit.sum(lb + 1, a[l[i]] + 1, rb, n); int r_lt = bit.sum(lb + 1, 0, rb, a[r[i]]); int r_gt = bit.sum(lb + 1, a[r[i]] + 1, rb, n); inv += l_gt - l_lt + r_lt - r_gt; } if(lb == rb) { for(int j = l[i] + 1; j < r[i]; ++j) { inv += (a[l[i]] < a[j] ? 1 : -1) + (a[r[i]] < a[j] ? -1 : 1); } } else { for(int j = l[i] + 1; j < (lb + 1) * B; ++j) { inv += (a[l[i]] < a[j] ? 1 : -1) + (a[r[i]] < a[j] ? -1 : 1); } for(int j = rb * B; j < r[i]; ++j) { inv += (a[l[i]] < a[j] ? 1 : -1) + (a[r[i]] < a[j] ? -1 : 1); } } inv += (a[l[i]] < a[r[i]] ? 1 : -1); bit.add(l[i] / B, a[l[i]], -1); bit.add(r[i] / B, a[r[i]], -1); swap(a[l[i]], a[r[i]]); bit.add(l[i] / B, a[l[i]], 1); bit.add(r[i] / B, a[r[i]], 1); } cout << inv << endl; } }
感想
メモリもTLEも怖すぎる．
Codeforces Round #404 (Div.2) D. Anton and School - 2
解法
条件に合う部分列の，一番右端の "(" の位置を総当りして計算します．
その位置から左に（その位置自体も含めて）"(" が $x$ 個あり，右に ")" が $y$ 個ある時，求める答えは $\displaystyle \sum_{i = 1}^{\min (x, y)}({_{x-1}C_{i-1}} \times {_yC_i})$ となります．簡単のため $x < y$ の時を考えます．
右辺の各 i についての式 $_{x-1}C_{i-1} \times _yC_i$ が意味するものを考えます．式変形して，$_{x-1}C_{x-i} \times _yC_i$ としておきます．
これは $x - 1$ 人からなるグループから $x - i$ 人を選び，$y$ 人からなるグループから $i$ 人を選ぶ組み合わせに対応します．つまり，$x - 1 + y$ 人から $x$ 人を選ぶ方法のうち，$x - 1$ 人の方から $x - i$ 人を選ぶときの組み合わせに対応します．
すると，$i$ を $1$ から $x$ まで動かした時，$x - 1 + y$ 人から $x$ 人を選ぶ方法すべてを網羅することになります．よって，
$\displaystyle \sum_{i = 1}^{x}({_{x-1}C_{i-1}} \times {_yC_i}) = _{x+y-1}C_x$
が成り立ち，求めたい値を O(1) で求めることができます．（前計算は必要です．）
・おまけ
ちょっと一般化すると
$\displaystyle \sum_{i=0}^z{_xC_i}{_yC_{z-i}} = _{x+y}C_{z}~ (z \leq x)$
で，$z = x$ とすれば
$\displaystyle \sum_{i=0}^x{_xC_i}{_yC_i} = _{x+y}C_{x}$
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; // modulo は略 const int MOD = 1000000007; using mod = modulo<MOD, true>; int main() { string s; cin >> s; int n = s.size(); vector<int> left(n + 1), right(n + 1); for(int i = 0; i < n; ++i) { left[i + 1] = left[i] + (s[i] == '('); right[n - i - 1] = right[n - i] + (s[n - i - 1] == ')'); } mod res = 0; for(int i = 1; i <= n; ++i) { if(s[i - 1] != '(') { continue; } if(right[i] != 0) { res += comb<MOD>(left[i] + right[i] - 1, left[i]); } } cout << (ll)res << endl; }
感想
式はすぐ出て来るが，変形で詰まった．
Codeforces ECR #31 F. Anti-Palindromize
解法
最小費用流で解ける．
まず，各アルファベットに対応する26個の頂点と，N / 2 個からなる文字列の前半（ないし後半）に対応する頂点をもつグラフをつくる．
それぞれのアルファベットから，文字列の各位置に対して辺を張る．
以下ではアルファベットの頂点番号を N / 2 + (c - 'a') とする．
頂点 N / 2 + (c - 'a') から頂点 i (0 <= i < N / 2) にフローが流れることを，S[i] または S[N - 1 - i] にアルファベット c を配置するということに対応付ける．
こうする時，辺のコストは max(S[i] == c ? b[i] : 0, S[N - 1 - i] == c ? b[N - 1 - i] : 0) とすることができる．
もちろん容量は1である．
source からは各アルファベットに対して辺を張り，コストは0，容量はそれぞれのアルファベットの出現数とする．
また，文字列の各位置に対応する頂点から sink に辺を張るのだが，これはコスト0，容量2としておく．
以上のように辺をはると，同じ頂点 i (0 <= i < N / 2) に対して同じ文字は割り当てられず，それぞれの頂点にちょうど2個のアルファベットを割り当てることができる．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using weight = int; constexpr int INF = 1e9; struct edge { int to, cap; weight cost; int rev; }; using edges = std::vector<edge>; using graph = std::vector<edges>; void add_edge(graph& g, int from, int to, int cap, weight cost) { g[from].push_back(edge{to, cap, cost, (int)g[to].size()}); g[to].push_back(edge{from, 0, -cost, (int)g[from].size()-1}); } weight min_cost_flow(graph& g, int s, int t, weight f) { using P = std::pair<weight, int>; weight res = 0; std::vector<weight> h(g.size(), 0); std::vector<weight> dist(g.size()); std::vector<int> prevv(g.size()), preve(g.size()); while(f > 0) { std::priority_queue<P, std::vector<P>, std::greater<P>> que; std::fill(dist.begin(), dist.end(), INF); dist[s] = 0; que.push(P{dist[s], s}); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(dist[v] < p.first) { continue; } for(int i = 0; i < (int)g[v].size(); ++i) { edge& e = g[v][i]; if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push(P{dist[e.to], e.to}); } } } if(dist[t] == INF) { return -1; } for(int v = 0; v < (int)g.size(); ++v) { h[v] += dist[v]; } weight d = f; for(int v = t; v != s; v = prevv[v]) { d = min(d, g[prevv[v]][preve[v]].cap); } f -= d; res += d * h[t]; for(int v = t; v != s; v = prevv[v]) { edge& e = g[prevv[v]][preve[v]]; e.cap -= d; g[v][e.rev].cap += d; } } return res; } int main() { int N; string S; cin >> N >> S; vector<int> b(N); for(int i = 0; i < N; ++i) { cin >> b[i]; } vector<int> cnt(26); for(auto c : S) { cnt[c - 'a']++; } graph g(N / 2 + 26 + 2); int const source = N / 2 + 26; int const sink = source + 1; for(int i = 0; i < 26; ++i) { add_edge(g, source, N / 2 + i, cnt[i], 0); } for(int i = 0; i < N / 2; ++i) { add_edge(g, i, sink, 2, 0); for(int j = 0; j < 26; ++j) { int cost = 0; if(S[i] - 'a' == j) { cost = max(cost, b[i]); } if(S[N - 1 - i] - 'a' == j) { cost = max(cost, b[N - 1 - i]); } add_edge(g, N / 2 + j, i, 1, -cost); } } cout << -min_cost_flow(g, source, sink, N) << endl; }
AOJ 2294 Entangled with Lottery
解法
ゴールから見るDPでやります．
dp[i][j][k] := 高さ (H から) i まで見た時に，位置 j にいて，それまでに猫が k 本引いているような確率
とします．
高さ 1 から i までに，うさぎがすでに引いている本数を m とすると，猫が引ける高さは残り i - m 箇所です．
今見ている高さがすでにうさぎによって線が引かれていれば，単純に swap するだけです．
引かれていないなら，今見ている高さに猫が線を引く確率 q は，
$\displaystyle q = \frac{_{i - m - 1}C_{K - k - 1}}{_{i - m}C_{K - k}} = \frac{K - k}{i - m}$
となります．
引いた上で，今見ている位置 j に関係する部分に線が引かれる確率 p は，端ならば $\displaystyle p = \frac{1}{N - 1}$，端でなければ $\displaystyle \frac{2}{N - 1}$ です．
あとは，dp[i][j][k] を，「その高さに線をそもそも引かない」「その高さに線を引き，かつそれが j に関係する」「その高さに線を引き，かつそれが j に関係しない」場合の3つに遷移させるだけです．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { cout << fixed << setprecision(10); int H, N, P, M, K; cin >> H >> N >> P >> M >> K; P--; vector<int> sw(H, -1); for(int i = 0; i < M; ++i) { int a, b; cin >> a >> b; sw[a - 1] = b - 1; } vector<int> sum(H + 1); for(int i = 0; i < H; ++i) { sum[i + 1] = sum[i] + (sw[i] != -1); } vector<vector<double>> dp(N, vector<double>(K + 1)); dp[P][0] = 1; double p = 1.0 / (N - 1); for(int i = H - 1; i >= 0; --i) { vector<vector<double>> nxt(N, vector<double>(K + 1)); for(int j = 0; j < N; ++j) { for(int k = 0; k <= K; ++k) { if(dp[j][k] == 0) { continue; } if(sw[i] == -1) { double q = (double)(K - k) / (i + 1 - sum[i]); // put possibility if(k == K) { nxt[j][k] += dp[j][k] * (1 - q); // (1 - q) == 1 } else { if(j != 0) { nxt[j - 1][k + 1] += dp[j][k] * p * q; } if(j != N - 1) { nxt[j + 1][k + 1] += dp[j][k] * p * q; } nxt[j][k] += dp[j][k] * (1 - q); if(j == 0 || j == N - 1) { nxt[j][k + 1] += dp[j][k] * q * (N - 2) / (N - 1); } else { nxt[j][k + 1] += dp[j][k] * q * (N - 3) / (N - 1); } } } else { if(sw[i] == j) { nxt[sw[i] + 1][k] += dp[j][k]; } else if(sw[i] + 1 == j) { nxt[sw[i]][k] += dp[j][k]; } else { nxt[j][k] += dp[j][k]; } } } } dp = move(nxt); } double res = 0; for(int i = 0; i < N; ++i) { res = max(res, dp[i][K]); } cout << res << endl; }
AOJ 2556 Integer in Integer
解法
やり方は色々あると思うんですが，僕は桁DPっぽくやりました（正直実装方針かなりミスっていると思う．）
まず，[0..N] までの答え f(N) を求めることができれば，f(B) - f(A - 1) で求められるので，f(N) を考えましょう．
dp[i][j][k] := i 桁目まで見たときに，C と先頭 j 桁が一致していて，その桁まで見たときに N 以下であるかが k であるような，leading zero を除いた場合の数
dp0[i][j][k] := i 桁目まで見たときに，C と先頭 j 桁が一致していて，その桁まで見たときに N 以下であるかが k であるような，leading zero である場合の数
dp2[i][j][k] := i 桁目まで見たときに，N 以下であるかが j であり，leading zero であるかが k であるようなもので，含まれる C の数
まず dp を計算する前に，C と先頭 j 桁が一致しているときに d （1桁の数）を付け加えたら何桁一致することになるかを match[j][d] として求めておきます（これは全探索で求められる）．
match[j][d] をつかって各 dp テーブルを更新していくのですが，流れとしては
という感じになります．コードはごちゃごちゃしてるけど遷移は自然．
dp と dp0 は，あくまで i 桁目までみて先頭が C と一致しているような数を求めているだけにすぎないです（i + 1 桁目以降は存在しないとして数えている）．
(例．C = 11 なら，3桁目までみて 11x となるのは 10 通り，2桁目まででは 11 の 1 通り．x の値によって，dp に入るか dp2 に入るかが変わってくる）
答えは dp2[i][0][0] + (i != |N| ? dp2[i][1][0] : 0) の総和です．
C = 0 のときはちょっと注意が必要です．
書いてて自分でもよくわからなくなってきた（？？？）
オーダーは O(2 * 10 * |C| * |A|) の 10^8 ぐらいで実際はもうちょい遅いかな～ぐらいです．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int M = 1e9 + 7; int solve(string A, string C) { int const n = A.size(); int const m = C.size(); reverse(A.begin(), A.end()); reverse(C.begin(), C.end()); vector<vector<int>> match(m + 1, vector<int>(10)); for(int d = 0; d <= 9; ++d) { char ch = '0' + d; for(int i = 0; i <= m; ++i) { int len = 0; for(int j = min(i + 1, m); j >= 1; --j) { if(C.substr(0, j) == C.substr(i - j + 1, j - 1) + ch) { len = j; break; } } match[i][d] = len; } } vector<vector<int>> dp(m + 1, vector<int>(2)); vector<vector<int>> dp0(m + 1, vector<int>(2)); // leading zero vector<vector<vector<int>>> dp2(n + 1, vector<vector<int>>(2, vector<int>(2))); dp[0][0] = 1; int res = 0; for(int i = 0; i < n; ++i) { vector<vector<int>> nxt(m + 1, vector<int>(2)), nxt0(m + 1, vector<int>(2)); for(int k = 0; k < 2; ++k) { for(int d = 0; d <= 9; ++d) { char ch = '0' + d; bool nk = k && ch == A[i] || ch > A[i]; if(d == 0) { (dp2[i + 1][nk][1] += dp2[i][k][0]) %= M; (dp2[i + 1][nk][1] += dp2[i][k][1]) %= M; } else { (dp2[i + 1][nk][0] += dp2[i][k][0]) %= M; (dp2[i + 1][nk][0] += dp2[i][k][1]) %= M; } } } for(int j = 0; j <= m; ++j) { for(int k = 0; k < 2; ++k) { for(int d = 0; d <= 9; ++d) { char ch = '0' + d; bool nk = k && ch == A[i] || ch > A[i]; int nj = match[j][d]; if(d == 0) { (nxt0[nj][nk] += dp[j][k]) %= M; (nxt0[nj][nk] += dp0[j][k]) %= M; } else { (nxt[nj][nk] += dp[j][k]) %= M; (nxt[nj][nk] += dp0[j][k]) %= M; } } } } (dp2[i + 1][0][0] += nxt[m][0]) %= M; (dp2[i + 1][0][1] += nxt0[m][0]) %= M; (dp2[i + 1][1][0] += nxt[m][1]) %= M; (dp2[i + 1][1][1] += nxt0[m][1]) %= M; dp = move(nxt); dp0 = move(nxt0); } for(int i = 1; i <= n; ++i) { (res += dp2[i][0][0]) %= M; if(i != n) { (res += dp2[i][1][0]) %= M; } } if(C == "0") { (res += 1) % M; } return res; } string decrement(string A) { for(int i = A.size() - 1; i >= 0; --i) { if(A[i] > '0') { A[i]--; break; } else { A[i] = '9'; } } if(A[0] == '0' && A.size() > 1) { return A.substr(1); } else { return A; } } int main() { string A, B, C; cin >> A >> B >> C; if(A != "0") { cout << (solve(B, C) - solve(decrement(A), C) + M) % M << endl; } else { cout << solve(B, C) << endl; } }
感想
通ったからいいけど，桁DPっぽくやったのは失敗だったかなあと思っています．
今真っ白な状態から書くなら，j 桁目が C であるような N 以下の数っていうのを求めていく感じになりそう．[X] ... C ... [Y] の X と Y を N を越えないように数えるみたいな．
AOJ 2614 Almost Same Substring
解法
ローリングハッシュでやります．
同じ長さの文字列 S, T に対して，「左からみて何文字一致しているか」と「右からみて何文字一致しているか」をそれぞれ二分探索で求めます．
もし S と T が一文字だけ異なるなら，左からの一致文字数と右からの一致文字数の和が，長さから1だけ小さいものになっているはずです．
よって，問題で与えられた S, T' について，S[a..a+|T'|-1] と T' に対し，先程やったことをすれば求まります．
ソースコード
#include <bits/stdc++.h> using namespace std; // 1-indexed // s[1...n] class rolling_hash { public: rolling_hash(std::string const& s) : n(s.size()), mod({999999937LL, 1000000007LL}) { for(int i = 0; i < 2; ++i) { hs[i].resize(n + 1); p[i].resize(n + 1); hs[i][0] = 0; p[i][0] = 1; for(int j = 0; j < n; ++j) { hs[i][j + 1] = (hs[i][j] * base + s[j]) % mod[i]; p[i][j + 1] = p[i][j] * base % mod[i]; } } } // s[i...] long long query(int idx, int i) const { return hs[i][idx]; } // s[l + 1...r] long long query(int l, int r, int i) const { return ((hs[i][r] - hs[i][l] * p[i][r - l]) % mod[i] + mod[i]) % mod[i]; } private: int n; std::vector<long long> hs[2]; std::vector<long long> p[2]; const std::array<long long, 2> mod; static const long long base = 29LL; }; int main() { string S, T; cin >> S >> T; rolling_hash hs1(S), hs2(T); int res = 0; for(int i = 1; i + T.size() - 1 <= S.size(); ++i) { int lb = i - 1, ub = i + T.size(); while(ub - lb > 1) { int m = (ub + lb) / 2; if(hs1.query(i - 1, m, 1) == hs2.query(0, m - i + 1, 1)) { lb = m; } else { ub = m; } } int l = lb; lb = i - 1, ub = i + T.size(); while(ub - lb > 1) { int m = (ub + lb) / 2; if(hs1.query(m - 1, i + T.size() - 1, 1) == hs2.query(m - i, T.size(), 1)) { ub = m; } else { lb = m; } } int r = ub; res += l + 2 == r; } cout << res << endl; }
感想
ローリングハッシュ使う時いっつもインデックスで混乱する．
