558C - Amr and Chemistry
- 本番これ以降の問題は溶けなかった...。なかなか C 問題の壁を超えられない...。
- 実は全探索＋枝刈りっぽい話。
- bfs + メモ化でなんとかなってしまうのか...。
- solve2,solve3 は Codeforces Round #312 (Div. 2) Editorial - Codeforces あたりで話題になっていた解法。遷移状態を二分木にしてノードを下りながら dp することで求める解法。こんなのよく思いつくなぁ...。
class Div2C { public: // a[i] = 10101111100001 のような二進表現にすると operations は // // a[i] <<= 1 // a[i] >>= 1 // // なので取りうる遷移の状態は // // 10101111100000 や 1010000000 や 1010 など prefix+0...0 のような数字になる // // max{a[i]} よりも大きくなるように a[i]*=2 する必要はないので max{a[i]} のビット長を m // とすると一般の a[i] の遷移は最大 // // (1+2+...+m)+1 = m(m+1)/2+1 となる(+1 は自分自身への遷移) // // なぜなら // // (1111111 -> 1000000, 1100000, 1110000, ...) のように // bits = ((1<<m)-1) から // bits -> { (bits>>k)<<k | 0<=k<=m-1 } と m 個の遷移が考えられるため。 // // よって計算量は O(n*m^2) 程度なので全探索でやる // // O(n*m^2+maxA) void solve1(void) { int N; cin>>N; vector<int> a(N,0); int maxA = 0; REP(i, N) { cin>>a[i]; maxA = max(a[i], maxA); } vector<int> cnt(maxA+1,0); // cnt[x] := a[i]-> x に遷移できたものの数 vector<int> step(maxA+1,0); // step[x] := a[i]->x に遷移したときのstep総数 // bfs で取りうる遷移の最小ステップを求める // O(N*m^2) REP(i, N) { queue<pair<int,int>> que; vector<bool> vis(maxA+1,false); que.emplace(a[i], 0); vis[a[i]] = true; ++cnt[a[i]]; while (!que.empty()) { int x, s; tie(x,s) = que.front(); que.pop(); if (x/2 > 0 && !vis[x/2]) { vis[x/2] = true; ++cnt[x/2]; step[x/2] += (s+1); que.emplace(x/2, s+1); } if (x*2 <= maxA && !vis[x*2]) { vis[x*2] = true; ++cnt[x*2]; step[x*2] += (s+1); que.emplace(x*2, s+1); } } } // 結果の参照 // O(maxA) int minStep = (1<<30); FOR(x, 1, maxA+1) { if (cnt[x] != N) // 遷移が到達できないケースは飛ばす continue; minStep = min(minStep, step[x]); } cout<<minStep<<endl; } // 別解法 O(n*log(n)) // やることは同じく全探索だけど、探索範囲を枝刈りして計算量を O(n*log(n)) にする。 void solve2(void) { int N; cin>>N; vector<int> a(N,0); int maxA = 0; REP(i, N) { cin>>a[i]; maxA = max(a[i], maxA); } // // a[i] の遷移状態のグラフは二分木になる。 // // 1 / の遷移は可逆 // / * * の遷移は非可逆 // 2 3 // / * / * // 4 5 6 7 // // 部分木の中のノードに初期状態が全て含まれているならその部分木の根が終了状態の一つの候補となる // (グラフを上に上がることはいつでも可能なので) // 終了状態はこの部分木のなかのノードのどれかとなる。 // * の遷移は非可逆なので左部分木からの寄与が全くないときのみ右部分木を考えればよい // それ以外は左部分木を考えることになる。(右からの寄与は根を経由して加算する) // 部分木のサイズを小さくしつつ探索をしてゆく(log(N)) // // [1] 1 [2] を根とする部分木での cost = // [2] 3 -> [2] 3 2を根とする部分木の cost + // 4 [5] 4 [5] 2を根とする部分木の「外」から [2] へ到達する cost // [8] [8] // // ([2]を根とする部分木で考える) // 遷移グラフを表現した配列 vector<int> H(maxA+1,0); // 初期状態として取りうる数 vector<int> L(maxA+1,0); // L[x] : 状態 x へ左の部分木の初期状態からの最小 cost vector<int> R(maxA+1,0); // R[x] : 状態 x へ右の部分木の初期状態からの最小 cost vector<int> U(maxA+1,0); // U[x] : 状態 x へ x/2 からの遷移の最小 cost vector<int> step(maxA+1,0); // 終了状態 x への最小ステップ数 // O(N*log(N)) REP(i, N) { int x = a[i]; ++H[x]; // L,R を更新 // O(log(N)) int stp = 0; while (x != 1) { if (x&1) ++R[x/2]; else ++L[x/2]; x = x/2; ++stp; } // 最終状態として 1 は絶対にとり得るので加算しておく step[1] += stp; } int x = 1; int ans = step[x]; bool up = false; // O(log(N)) while (true) { // 左部分木からの寄与が全くないケースは右部分木で考える if (!L[x] && !H[x] && !up) x = 2*x + 1; else { // 必ず現在の node x を経由した遷移が存在するとき up = true にする // 次の node 移動時に確実に左部分木に移動したいから(右部分木には移動できないから) if (R[x] || H[x]) up = true; if (2*x <= maxA) // overflow しないためにチェックしてるだけ U[2*x] += U[x] + H[x] + R[x]; x = 2*x; } if (x > maxA) break; if (x & 1) // 右側からの寄与しかないので R[x/2] = step[x]-step[x/2] step[x] = step[x/2] - R[x/2]; // (全ての数字を 1/2 倍してx/2にするため) else // 同様。x を経由するので U[x] を加える step[x] = step[x/2] + U[x] - L[x/2]; ans = min(ans, step[x]); } cout<<ans<<endl; } // O(maxA) 解法 // 考え方的には solve2 と同じ。高速化版 void solve3(void) { int N; cin>>N; vector<int> a(N,0); int maxA = 0; REP(i, N) { cin>>a[i]; maxA = max(a[i], maxA); } vector<int> degree(2*maxA+2, 0); // x を根とする部分木の各ノードから x すべて移動させたときの重複度 vector<int> cost(2*maxA+2, 0); // x を根とする部分木の各ノードから x へ移動するための cost // 各ノードを初期化 REP(i, N) ++degree[a[i]]; // 根に向かって木を初期化 // O(maxA) for (int i = maxA; i >= 0; --i) { // cost[i] は degree[j](重複度最大)にするための cost[j] と // degree[j] 個の j を i に移動させるための costの和になる (j=2*i or 2*i+1) cost[i] = cost[2*i] + cost[2*i+1] + degree[2*i] + degree[2*i+1]; degree[i] += degree[2*i] + degree[2*i+1]; // 重複度を更新 } ll ans = (1<<30); function<void(int,ll,ll)> rec = [&](int i, // 部分木の根 ll sum, // i を終了状態にするように i を根とする部分木の // 外側のノードを i に遷移させた時の cost ll deg) {// i をこんとする部分木の外側から移動してくる状態数 if (i > maxA) return; ans = min(ans, cost[i]+sum); // 初期状態の degree int ideg = degree[i] - degree[2*i] - degree[2*i+1]; // 左側を探索 rec(2*i, cost[2*i+1] + // 次に探索しない右側の部分木の cost sum + // i を根とする部分木の外からの cost degree[2*i+1]+ // 2*i+1 -> i に移動させる cost deg+ // 2/i->i に移動させる cost (degree[i] - degree[2*i]), // (2*i+1->i,i/2->i の移動後に) i -> 2*i へ移動させるとき cost deg+(degree[i]-degree[2*i])); // 2*i+1 の外側からやってくる degree // 上・左からの寄与が一切ないとき、右側を探索 if (deg == 0 && degree[i]-degree[2*i+1] == 0) rec(2*i+1, 0, 0); }; // O(maxA) // 根から下にたどっていく rec(1,0,0); cout<<ans<<endl; } void solve() { //solve1(); //solve2(); solve3(); } };
