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; }
感想
ローリングハッシュ使う時いっつもインデックスで混乱する．
AOJ 2605 Social Monsters
解法
制約をよく読むと，（使えない辺を含める）与えられたグラフにおける各連結成分は，1つのパスまたは閉路になっていることがわかります．
各連結成分において計算して，最後にまとめあげることにします．
1つのパスについては，以下のDPで端から順番に計算します．
dp[i][j][k] := i 番目の頂点までみたとき，それまでに j 個の頂点を用いていて，直前の頂点を使ったかのフラグが k であるときの最大値
隣接してる2つが使えないなら，k == 0 となる場合しか今見ている頂点は使えない，みたいな遷移になります．
閉路については，追加で情報が必要です．閉路の始点は適当に決めて良いです．
dp[i][j][k][l] := i 番目の頂点まで見た時，それまでに j 個の頂点を用いていて，直前の頂点を使ったかのフラグが k であり，最初の頂点を使ったかのフラグが l であるときの最大値
最後に各連結成分でもとめた dp の値を合わせて全体の結果を得ます．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int INF = 1e9; struct edge { int to, cost; }; using edges = vector<edge>; using graph = vector<edges>; int N, M, K; int cost[2001][2001]; // true -> circuit bool dfs(graph const& g, int v, int p, vector<bool>& visited, vector<int>& res) { res.push_back(v); visited[v] = true; bool circuit = false; for(auto& e : g[v]) { if(e.to == p) { continue; } if(visited[e.to]) { circuit = true; } else { circuit |= dfs(g, e.to, v, visited, res); } } return circuit; } vector<int> calc_line(vector<int> const& line) { vector<vector<int>> dp(K + 1, vector<int>(2, -INF)); dp[0][0] = dp[1][1] = 0; for(int i = 1; i < (int)line.size(); ++i) { int pre = line[i - 1]; int v = line[i]; vector<vector<int>> nxt(K + 1, vector<int>(2, -INF)); for(int k = 0; k <= K; ++k) { if(dp[k][0] != -INF) { if(k + 1 <= K) { nxt[k + 1][1] = max(nxt[k + 1][1], dp[k][0]); } nxt[k][0] = max(nxt[k][0], dp[k][0]); } if(dp[k][1] != -INF) { if(cost[pre][v] != 0 && k + 1 <= K) { nxt[k + 1][1] = max(nxt[k + 1][1], dp[k][1] + cost[pre][v]); } nxt[k][0] = max(nxt[k][0], dp[k][1]); } } dp.swap(nxt); } vector<int> res(K + 1); for(int i = 0; i < K + 1; ++i) { res[i] = max(dp[i][0], dp[i][1]); } return res; } vector<int> calc_cycle(vector<int> const& cycle) { // (use, pre, first) vector<vector<vector<int>>> dp(K + 1, vector<vector<int>>(2, vector<int>(2, -INF))); dp[0][0][0] = dp[1][1][1] = 0; int const first = cycle[0]; for(int i = 1; i < (int)cycle.size(); ++i) { int pre = cycle[i - 1]; int v = cycle[i]; vector<vector<vector<int>>> nxt(K + 1, vector<vector<int>>(2, vector<int>(2, -INF))); for(int k = 0; k <= K; ++k) { for(int fuse = 0; fuse <= 1; ++fuse) { if(i == cycle.size() - 1 && fuse == 1) { if(dp[k][0][fuse] != -INF) { if(k + 1 <= K && cost[first][v] != 0) { nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][0][fuse] + cost[first][v]); } nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][0][fuse]); } if(dp[k][1][fuse] != -INF) { if(cost[first][v] != 0 && cost[pre][v] != 0 && k + 1 <= K) { nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][1][fuse] + cost[pre][v] + cost[first][v]); } nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][1][fuse]); } } else { if(dp[k][0][fuse] != -INF) { if(k + 1 <= K) { nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][0][fuse]); } nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][0][fuse]); } if(dp[k][1][fuse] != -INF) { if(cost[pre][v] != 0 && k + 1 <= K) { nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][1][fuse] + cost[pre][v]); } nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][1][fuse]); } } } } dp.swap(nxt); } vector<int> res(K + 1); for(int i = 0; i < K + 1; ++i) { res[i] = max({dp[i][0][0], dp[i][0][1], dp[i][1][0], dp[i][1][1]}); } return res; } int main() { cin >> N >> M >> K; graph g(N); for(int i = 0; i < M; ++i) { int a, b, c; cin >> a >> b >> c; a--; b--; g[a].push_back(edge{b, c}); g[b].push_back(edge{a, c}); cost[a][b] = cost[b][a] = c; } vector<vector<int>> line, cycle; vector<bool> visited(N); vector<int> sz; for(int i = 0; i < N; ++i) { if(!visited[i]) { vector<int> c; bool circuit = dfs(g, i, -1, visited, c); if(!circuit) { for(auto v : c) { visited[v] = false; } for(auto v : c) { if(g[v].size() == 1) { c.clear(); dfs(g, v, -1, visited, c); break; } } sz.push_back(c.size()); line.push_back(move(c)); } else { cycle.push_back(move(c)); } } } for(auto& c : cycle) { sz.push_back(c.size()); } vector<vector<int>> dp2; for(auto& l : line) { dp2.push_back(calc_line(l)); } for(auto& c : cycle) { dp2.push_back(calc_cycle(c)); } vector<int> dp(K + 1, -INF); dp[0] = 0; int total_sz = 0; for(int i = 0; i < (int)dp2.size(); ++i) { vector<int> nxt(K + 1, -INF); for(int k1 = 0; k1 <= total_sz; ++k1) { if(dp[k1] == -INF) { continue; } for(int k2 = 0; k2 <= sz[i] && k1 + k2 <= K; ++k2) { if(dp2[i][k2] != -INF) { nxt[k1 + k2] = max(nxt[k1 + k2], dp[k1] + dp2[i][k2]); } } } total_sz += sz[i]; dp.swap(nxt); } if(dp[K] == -INF) { cout << "Impossible" << endl; } else { cout << dp[K] << endl; } }
感想
実装が重い．うまくやれば実装量は減りそうだが，半分ぐらいは同じことをしてるコードなので，コード長の割には楽だったかもしれない．
AOJ 2449 Connect
解法
これは典型問題です．
$i$ 行目の $j$ 番目に文字を置くかどうか考えた時に関係してくるのは，$i$ 行目の $1$ から $j - 1$ 列目と，$i - 1$ 行目の $j$ から $C$ 列目だけです．
なので結局，一行分の状態をビットで持つ bitDP にできます．
$dp[i][j][S] := i$ 行目の $j$ 列目まで見た時，文字が配置されている状況が $S$ であるときの最大値
$S$ の下位 $j$ ビットが今の行の状態，上位 $C - j$ ビットが直前の行の状態を表しています．
$i$ 行目 $j$ 列目の位置に文字を配置する場合，直前に同じ文字が置かれているかと，前の行の同じ列に同じ文字が置かれているかを見ます．
今配置しようとしている文字のインデックスは $bitcount(S \& (1 << j) - 1)$ で得られます．
上の行で配置されている文字のインデックスは，後ろから何番目であるかを考えれば，$|s_i| - bitcount(S >> j)$ で得られます．
使わない選択をする場合は，あとに配置できる余地が十分であるかを確認する必要があります．
その他，$S$ の状態でありえないものは適宜無視すればよいです．
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int R, C; cin >> R >> C; vector<string> s(R); for(int i = 0; i < R; ++i) { cin >> s[i]; } vector<int> bitcount(1 << C); for(int i = 0; i < 1 << C; ++i) { bitcount[i] = __builtin_popcount(i); } vector<int> dp(1 << C, -1); dp[0] = 0; for(int i = 0; i < R; ++i) { for(int j = 0; j < C; ++j) { vector<int> nxt(1 << C, -1); for(int S = 0; S < (1 << C); ++S) { if(dp[S] == -1) { continue; } int idx = bitcount[S & (1 << j) - 1]; if(idx < s[i].size()) { int t = dp[S]; if(idx > 0 && (S & 1 << (j - 1)) && s[i][idx - 1] == s[i][idx]) { t++; } if(i > 0 && (S & 1 << j) && s[i][idx] == s[i - 1][s[i - 1].size() - bitcount[S >> j]]) { t++; } nxt[S | 1 << j] = max(nxt[S | 1 << j], t); } if(C - j > s[i].size() - idx) { nxt[S & ~(1 << j)] = max(nxt[S & ~(1 << j)], dp[S]); } } dp.swap(nxt); } } cout << 2 * *max_element(begin(dp), end(dp)) << endl; }
AOJ 2376 Disconnected Game
解法
石取りゲームだからいい感じにわかるんでは？と思ったけどよくわかんなかったのでメモ化再帰で解きます．
勝ちが決まるタイミングはは，連結成分の数が2であり，かつ自分の手番で辺を追加すると，追加できる辺の数が 0 になるときですね．（それはそう）
それまでは，異なる連結成分を連結させるか，連結成分内の頂点同士に辺を張るかのどちらかです．
残りの辺の数は愚直にもたずに偶奇で判定できますね．異なる連結成分同士を結ぶ辺以外で使える辺の数を $unused$ とします．
異なる連結成分同士を結んだ時，$unused$ も変化しますが，偶奇だけわかればいいので，連結成分のサイズの偶奇の情報を持つだけでいいです．
今，サイズが奇数，偶数の連結成分の数を $(odd, even)$ とします．
$(odd, even, unused)$ でメモ化再帰します．
自分の手番でできるパターンは以下の4通りあります．
- 大きさが偶数の連結成分同士を結ぶ．結果として，偶数の連結成分が1つ減り，新たに使える辺が奇数本増える．
- 大きさが奇数の連結成分同士を結ぶ．結果として，奇数の連結成分が2つ減り，偶数の連結成分が1つ増える．また，使える辺の数が偶数本増える．
- 大きさが偶数と奇数の連結成分を結ぶ．結果として，偶数の連結成分が1つ減る．また，使える辺の数が奇数本増える．
- 連結成分同士を結ばないように辺を張る．
4つ目の場合はメモ化再帰でループが発生してしまいますが，実は $unused$ を偶数から奇数に移す場合は無視できます．
なぜなら，こういう操作をされた場合，次の手番の人が $unused$ を奇数から偶数に移せば，先ほどと同じ状態になるため，いずれは連結成分同士を結ぶ状況に陥るからです．（つまり偶数から奇数に移す操作が最善手であることはない．そういう状況はすでに負け確定．）
これでループが解消できたので，安心してかけます．
ソースコード
#include <bits/stdc++.h> using namespace std; int dfs(int v, vector<string> const& g, vector<bool>& visited) { visited[v] = true; int res = 1; for(int i = 0; i < (int)g.size(); ++i) { if(g[v][i] == 'Y' && !visited[i]) { res += dfs(i, g, visited); } } return res; } int rec(int odd, int even, int unused, vector<vector<vector<int>>>& dp) { int& res = dp[odd][even][unused]; if(res != -1) { return res; } if(odd + even == 2) { return res = unused; } if(unused == 1 && !rec(odd, even, !unused, dp)) { return res = 1; } if(odd > 0 && even > 0 && !rec(odd, even - 1, !unused, dp)) { return res = 1; } if(odd >= 2 && !rec(odd - 2, even + 1, unused, dp)) { return res = 1; } if(even >= 2 && !rec(odd, even - 1, !unused, dp)) { return res = 1; } return res = 0; } int main() { int N; cin >> N; vector<string> g(N); for(int i = 0; i < N; ++i) { cin >> g[i]; } vector<bool> visited(N); int odd = 0, even = 0; int unused = 0; for(int i = 0; i < N; ++i) { if(!visited[i]) { int C = dfs(i, g, visited); unused += C * (C - 1) / 2; if(C & 1) { ++odd; } else { ++even; } } for(int j = i + 1; j < N; ++j) { unused -= (g[i][j] == 'Y'); } } unused %= 2; vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(N + 1, vector<int>(2, -1))); if(rec(odd, even, unused, dp)) { cout << "Taro" << endl; } else { cout << "Hanako" << endl; } }
感想
4つ目のパターンを書き忘れた状態で間違えて提出してしまったんですが，なぜか通ってしまい，ジャッジのケースが弱いのか，実は完全に無視して良いのかよくわからなくなった…．
もしあるなら O(1) 解をもっと考えればそのうちわかるかも（考えませんけどね）．
AOJ 2313 Box Witch
解法
ちゃんとフローがわかってるなら解ける問題．
まず辺の追加クエリは簡単で，単純に辺を増やすだけ．
問題は辺の削除クエリです．与えられた辺を $\{a, b\}$ とします．
今流れてるフローで与えられた辺が使われていないなら，単純に削除します（これは辺のキャパシティ $cap[u][v]$ を持っておいて，$cap[a][b] \neq 1$ であるかで判定できます．どっちが 0 かで流れている向きもわかる．）
使われている場合，残余グラフ上で $a \rightarrow b$ のパスが残っているなら，$a \rightarrow b$ のフローを1ながして $\{a, b\}$ を消せば，整合性を損なうことなく流量を維持できます．
もし $a \rightarrow b$ のパスがない場合，一旦 $n \rightarrow 1$ へのフローを1流し直して，そのあと $a \rightarrow b$ のフローを流すと，自然にもともとの $a \rightarrow b$ のフローを打ち消すことが出来ます．
あとは辺を消してフローを流し直すだけで終わります．
ソースコード
#include <bits/stdc++.h> using namespace std; using graph = vector<vector<int>>; int dfs(graph& g, vector<bool>& visited, vector<vector<int>>& cap, int v, int t) { if(v == t) { return 1; } visited[v] = true; for(auto to : g[v]) { if(visited[to] || cap[v][to] == 0) { continue; } if(dfs(g, visited, cap, to, t) == 1) { cap[to][v]++; cap[v][to]--; return 1; } } return 0; } int max_flow(graph& g, vector<vector<int>>& cap, int s, int t, int cnt = 100000) { vector<bool> visited(g.size()); int f = 0; while(cnt--) { fill(visited.begin(), visited.end(), false); if(dfs(g, visited, cap, s, t) == 1) { f++; } else { break; } } return f; } int main() { int N, E, Q; cin >> N >> E >> Q; graph g(N); vector<vector<int>> cap(N, vector<int>(N)); auto add_edge = [&](int from, int to) { g[from].push_back(to); g[to].push_back(from); cap[from][to] = cap[to][from] = 1; }; for(int i = 0; i < E; ++i) { int f, t; cin >> f >> t; f--; t--; add_edge(f, t); } int res = max_flow(g, cap, 0, N - 1); while(Q--) { int m, a, b; cin >> m >> a >> b; a--; b--; if(m == 1) { add_edge(a, b); } else { // used b -> a if(cap[a][b] == 2) { // doesn't exist circuit b -> a on residual graph if(max_flow(g, cap, b, a, 1) == 0) { max_flow(g, cap, N - 1, 0, 1); max_flow(g, cap, b, a, 1); res--; } } else if(cap[b][a] == 2) { if(max_flow(g, cap, a, b, 1) == 0) { max_flow(g, cap, N - 1, 0, 1); max_flow(g, cap, a, b, 1); res--; } } cap[a][b] = cap[b][a] = 0; g[a].erase(find(g[a].begin(), g[a].end(), b)); g[b].erase(find(g[b].begin(), g[b].end(), a)); } res += max_flow(g, cap, 0, N - 1); cout << res << endl; } }
感想
フローのいい練習になりそうな問題．
AOJ 2344 Multi Ending Story
解法
木DPで解きます．
まず部分木に注目しましょう．
冷静に考えると，この部分木のすべての葉を回収するのには，以下の3通りだけしかありません．この部分木の根を $v$，左右の子をそれぞれ $l, r$ とします．
- $v$ で quick save を使わず，それぞれの子の部分木でいい感じに quick save を用いて最適に回収する
- $v$ で quick save した後，まず $l$ の部分木の葉をすべて回収（この時 quick save は用いない）して，その後 $r$ の部分木で quick save を用いつつ最適に回収する
- 2つ目のパターンで左右を入れ替えたパターン
そこで以下のように定めます．
$dp[v] := v$ が根の部分木にあるすべての葉を quick save をいい感じに用いて最適に回収したときのコスト
$dp_2[v] := v$が根の部分木にあるすべての葉を， $v$ で quick save をしたとき（子の部分木では一切 quick save しない）の回収のコスト．ただし真の根から $v$ までのコストは除くものとする．
$cnt[v] := v$ の部分木に含まれる葉の個数
1つ目のパターンは，$v$ で quick save しないので真の根から $v$ までのコスト $depth[v]$ が余計にかかります．なので，このときのコストは
$dp[l] + dp[r] + depth[v] + 2$
となります．
2つ目（3つ目も同様）のパターンでは，$l$ の部分木の回収に $dp_2[l]$ と，
$v$ から $l$ に $cnt[l]$ 回移動することになるのでその分だけのコストがまずかかります．その後は，$r$ にうつって最適に回収するので，そのコストは $dp[r] + 1$ です．よって総コストは
$dp_2[l] + cnt[l] + dp[r] + 1$
となります．
あとはこれらのうちで最小のものが $dp[v]$ の値となります．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; // スタック拡張します int N; ll dp[500001], dp2[500001]; int leaf_cnt[500001]; int g[500001][2]; ll dfs(int v, int depth) { for(int i = 0; i < 2; ++i) { int to = g[v][i]; if(to == N) { leaf_cnt[v]++; } else { dfs(to, depth + 1); leaf_cnt[v] += leaf_cnt[to]; dp2[v] += dp2[to]; } } dp2[v] += leaf_cnt[v]; ll& res = dp[v]; int l = g[v][0], r = g[v][1]; dp[v] = min({dp2[l] + (leaf_cnt[l] == 0 ? 1 : leaf_cnt[l]) + 1 + dp[r], dp[l] + dp2[r] + (leaf_cnt[r] == 0 ? 1 : leaf_cnt[r]) + 1, dp[l] + depth + dp[r] + 2}); return dp[v]; } int main() { cin >> N; for(int i = 0; i < N - 1; ++i) { int a, b; cin >> a >> b; a -= (a != N); b -= (b != N); g[i][0] = a; g[i][1] = b; } cout << dfs(0, 0) << endl; }
感想
メモリの制約が厳しい上に，普通にスタックオーバーフローするので†スタック拡張†します．
DP部分は普通に難しかった……．
