Atcoder Grand Contest 004 F. Namori

Atcoder Grand Contest 004 F. Namori

F: Namori - AtCoder Grand Contest 004 | AtCoder

感想

解にたどり着くまでに考えることがたくさんある。ケースに応じて適切なアルゴリズムに落とし込んでいくのが、おもしろい。

解法

まず連続する同色の頂点を反転させるという操作は、(白、白）->（黒、黒）と（黒、黒）->（白、白）の2パターンがあるため、考えるのが難しい。そこで、どんな操作も（白、黒）->（黒、白）という操作に変えることができれば、扱うのが容易になるだろう。そこで、二部グラフの要領で白黒に塗ってしまったグラフを考え、そのグラフとの$\ XOR\ $をとったような色の状態を考えることにする。すると、ある連続する2点を選んだ時に、その一方のみが$\ XOR\ $をとったようなものになるはずなので、（白、黒）->（黒、白）という操作のみに落とし込むことができる。

さらにこれを「反転の操作」ではなく、「黒の位置を白の位置に動かす操作」に見ることができることに気付く。すると結局、すべての黒い部分を白い部分に移動させるために必要な操作回数を求める問題になる。

この発想を思いつくのは難しいのだが、下の類題を見れば、割と典型であることに気付くだろう。下の問題は反転の操作を駒を動かす操作に見立てるところまで同じである（反転と$\ XOR\ $のテク）。

F: Prime Flip - AtCoder Regular Contest 080 | AtCoder

ここまでくれば、$\ m = n - 1\ $の場合は易しい問題に変わる。まずグラフが木なので、二部グラフの要領で黒を塗っていく。そのあと、この黒を白に移動させていくのだが、まずこの個数が一致していなければ明らかに不可能であることがわかる。逆に一致していれば有限回の操作で可能である。

さて、グラフが木であることを利用すると、ある辺に注目したときに、どちらかの部分木を見て、そこに黒の頂点が$\ B\ $個、白の頂点が$\ W\ $個あったとすると、無駄なく移動させるためには、この辺を経由する回数というのは明らかに$\ |B - W|\ $回であることが言える。よって各辺についてこの値を計算し、その総和をとれば答えである。これは簡単な$\ DFS\ $によって$\ O(n)\ $で計算可能である。

次に、$\ m = n\ $の場合を考える。これはNamoriグラフと呼ばれ、一つだけ閉路を含む木のような構造である。この閉路が偶閉路なのか奇閉路なのかで場合分けをする。

まずグラフが偶閉路をもつ場合を考える。この場合は木の場合と同様に（グラフが二部グラフなので）白黒に塗っておくことができる。これらの白黒の個数が一致していない場合はやはり不可能である。

さて、閉路上にない辺は、上のようにしてどちらかの部分木の白黒の数を数えて$\ |B - W|\ $なる数を加算していけば良い。閉路上の辺については、どこか一つの辺の移動量を固定しないと計算できない。そこで、ある閉路上の辺$\ (s, t)\ $について、ここを移動する黒の数を$\ 0\ $と仮定し、この辺を切ってしまうことにする。

このあとに、上と同じように移動量を考えていくのだが、閉路上の辺については、$\ B - W\ $の値を一旦vector flowなどに保管しておくことにする。そして、このflowから閉路上の移動量がどうなっているのかを求めよう。

$\ s\ $と$\ t\ $の間の移動量を$\ 0\ $に仮定した場合の移動量がflowに格納されている。したがって、この場合の答えは、flowのそれぞれの値の絶対値の総和をとればよい。仮に$\ s, t\ $間の移動量を$\ 1\ $にした場合は、このflowのそれぞれの数から$\ 1\ $を引いた数の絶対値をとったものの総和をとり、それに$\ 1\ $を足すことで答えになる。一般に$\ s, t\ $の移動量が$\ x\ $だったとすると、答えは$\ \sum |flow_i - x| + |x|\ $となる。この式をぐっと睨むとこれは下に凸だと気付くので、三分探索して最小値をとればそれが答えになる。この計算量は$\ O(n \log n)\ $である。

ある辺が閉路上の辺であるかどうかの判定は、ある頂点を根にして$\ DFS\ $しているときに、ある頂点以下に$\ s, t\ $がそれぞれ含まれているかどうかをみる配列を用意しておき、どちらか一方のみ含まれているならば、その辺は閉路上の辺であることがわかる。

三分探索は、終わらせ方がよくわからなかったので、幅が$\ 3\ $とかになったら終了して、あとは幅$\ 20\ $くらいで適当に最小値を見つけるようにした。

最後に、グラフが奇閉路をもつ場合を考える。この場合は、そもそも二部グラフではないので白黒に塗り分けることができないのだが、閉路は一つなので、塗り分け不可能な部分は必ず一つである。その辺が結ぶ2点上では、（白、白）->（黒、黒）あるいは（黒、黒）->（白、白）の操作をしてよいものとして考えることにする。ここで白黒の個数調整ができると考えると、初期状態で白と黒の偶奇が一致していれば可能であることがいえる。

この個数調整を回数を$\ cnt\ $としておくと、$\ s, t\ $においては黒$\ cnt\ $分多くみて考え、この辺を切ってしまえば、あとは木の場合と全く同様に$\ O(n)\ $で処理することができる。

解法がめちゃくちゃ長くなった。

実装

#include "bits/stdc++.h"
using namespace std;

vector<int> g[101010];
int color[101010];
int black, white, type, cnt;
int s, t;
long long ans;
bool in_s[101010], in_t[101010];
vector<long long> flow;

void check(int v, int prev, int d) {
        color[v] = d;
        if (d & 1) black ++;
        else white ++;
        for (auto u : g[v]) if (u != prev) { 
                if (color[u] == -1) {
                        check(u, v, 1 - d);
                } else {
                        s = v, t = u;
                        if (color[u] == 1 - d) type = 1;
                        else type = 2;
                }
        }
}

pair<int, int> dfs(int v, int prev, int d) {
        int b = 0, w = 0;
        for (auto u : g[v]) if (u != prev) {
                pair<int, int> get = dfs(u, v, d + 1);
                b += get.first;
                w += get.second;
        }
        if (d & 1) b ++;
        else w ++;
        if (type == 2 && (v == s || v == t)) b -= cnt;
        ans += abs(b - w);
        return make_pair(b, w);
}

pair<int, int> dfs2(int v, int prev, int d) {
        int b = 0, w = 0;
        in_s[v] = false, in_t[v] = false;
        in_s[v] |= v == s;
        in_t[v] |= v == t;
        for (auto u : g[v]) if (u != prev) {
                pair<int, int> get = dfs2(u, v, d + 1);
                in_s[v] |= in_s[u];
                in_t[v] |= in_t[u];
                b += get.first;
                w += get.second;
        }
        if (d & 1) b ++;
        else w ++;
        if ((in_s[v] && in_t[v]) || (!in_s[v] && !in_t[v])) ans += abs(b - w);
        else flow.push_back(b - w);
        return make_pair(b, w);
}

int main() {
        int n, m;
        scanf(&quot;%d%d&quot;, &n, &m);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf(&quot;%d%d&quot;, &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        type = 0;
        memset(color, -1, sizeof color);
        check(0, -1, 0);
        if ((type == 0 && black != white) ||
            (type == 1 && black != white) ||
            (type == 2 && black % 2 != white % 2)) {
                puts(&quot;-1&quot;);
                return 0;
        }
        if (type == 0) dfs(0, -1, 0);
        g[s].erase(remove(g[s].begin(), g[s].end(), t), g[s].end());
        g[t].erase(remove(g[t].begin(), g[t].end(), s), g[t].end());
        if (type == 1) {
                dfs2(0, -1, 0);
                int lb = -101010, ub = 101010;
                while (ub - lb > 3) {
                        int left = (lb * 2 + ub) / 3;
                        int right = (lb + ub * 2) / 3;
                        long long left_ans = 0, right_ans = 0;
                        for (auto f : flow) {
                                left_ans += abs(left + f);
                                right_ans += abs(right + f);
                        }
                        left_ans += abs(left); //self
                        right_ans += abs(right); //self
                        if (left_ans < right_ans) ub = right;
                        else lb = left;
                }
                long long res = 1LL << 60;
                for (int i = lb - 10; i < lb + 10; i ++) {
                        long long sum = 0;
                        for (auto f : flow) sum += abs(i + f);
                        sum += abs(i); //self
                        res = min(res, sum);
                }
                ans += res;
        }
        if (type == 2) {
                cnt = (black - white) / 2;
                dfs(0, -1, 0);
                ans += abs(cnt);
        }
        printf(&quot;%lld\n&quot;, ans);
        return 0;
}