https://beta.atcoder.jp/contests/arc097/tasks/arc097_d

問題概要

N頂点の木が与えられる。木の各頂点には白か黒どちらかの色がついている。任意の頂点からスタートし、以下の2種類の動作を任意の順序で繰り返すとき、すべての頂点の色を黒にするために必要な動作の回数は最小で何回になるか求めよ。

隣接する頂点に移動し、移動した先の頂点の色を反転する
今いる頂点の色を反転する。

N <= 10⁵

解法

まず既に色が黒である葉は訪れる必要がない。そのような葉を順次取り除いていくと、すべての葉が白の木になる。こちらの方で考えても答えは変わらないので、以下ではすべての葉が白であるという条件のもとで考える。

すべての葉が白であるので、少なくとも1回は全部の頂点を訪れる必要がある。オイラーツアー（普通のDFS)をすればすべての辺をちょうど2回ずつ通ってスタート地点に戻ってくることができるが、この問題ではスタートに戻ってくる必要はなく、その分だけ移動回数で得をすることができる。具体的には木上のひとつの（葉から葉への）パスだけは往復せずに済む（イメージ的にはパス上を端から端へ移動しながらパスでない道に行けるときはそっちに寄り道してまた戻ってくる、という感じ）。というわけで問題はどのようにパスを選ぶべきか、という点に移る。

オイラーツアーの性質について考えてみると、オイラーツアーを行った場合すべての辺を町道2回ずつ相異なる向きで移動するわけなので、今回のような単純グラフの場合すべての頂点はちょうど（自分の隣接頂点の数）回訪問されることになる。そしてここから一本サボるパスを選んだとき、そのパス上の頂点だけは最後に戻ってくるときの訪問がないので（自分の隣接頂点の数 - 1）回の訪問になる。これによってどのような影響があるのかをまとめると以下のような形になる。

（隣接頂点の数）回反転したあとの色が黒の頂点 → パスとして選ぶと訪問回数が1回減るので色が白になり、追加の反転操作が必要。コスト的にはプラマイ0。
（隣接頂点の数）回反転したあとの色が白の頂点 → パスとして選ぶと訪問回数が1回減るので色が黒になる上、反転操作も必要なくなる。コスト的には-2（訪問コスト-1, 反転コスト-1）。

すべての頂点の色を（隣接頂点の数）回反転させたあとの世界で考えると、上の性質より「選んだパスに何個黒の頂点があってもコストには関係ない」「白の頂点はあればあるだけ得」ということがわかる。よってパスとして選ぶべきなのはなるべく多くの白を含むものということになる。これは木の直径を求めるのと同じようにDFSを2回すれば計算可能である。パスを決めれば各頂点の訪問コストと反転コストも決まるので答えが出せる。

感想

ひとつの頂点とかひとつの辺に着目してみるとなんかいい感じになるの木の問題あるあるっぽい

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

int N;
int[][] G;
string C;
int root;

void input() {
    auto n = readln.chomp.to!int;
    auto g = new int[][](n);
    foreach (_; 0..n-1) {
        auto s = readln.split.map!(to!int);
        g[s[0]-1] ~= s[1]-1;
        g[s[1]-1] ~= s[0]-1;
    }
    auto c = readln.chomp;

    root = -1;
    foreach (i; 0..n) if (c[i] == 'W') root = i;
    
    if (root == -1) {
        N = 0;
        return;
    }

    
    auto use = new bool[](n);
    use.fill(true);

    int dfs(int u, int p) {
        int ret = c[u] == 'W';
        foreach (v; g[u]) {
            if (v == p) continue;
            int tmp = dfs(v, u);
            if (tmp == 0) use[v] = false;
            ret += tmp;
        }
        return ret;
    }
    dfs(root, -1);

    N = use.sum;
    G = new int[][](N);
    auto comp = new int[](n);
    comp.fill(-1);

    for (int i = 0, cnt = 0; i < n; ++i) {
        if (use[i]) {
            comp[i] = cnt++;
            C ~= c[i];
        }
    }

    foreach (i; 0..n) {
        if (!use[i]) continue;
        foreach (j; g[i]) {
            if (!use[j]) continue;
            G[comp[i]] ~= comp[j];
        }
    }

    root = comp[root];
}

void main() {
    input();
    auto D = C.map!(c => c == 'W' ? 1 : 0).array;
    
    if (N <= 1) {
        N.writeln;
        return;
    }
    
    void dfs(int n, int p) {
        D[n] ^= 1;
        foreach (m; G[n]) if (m != p) dfs(m, n), D[n] ^= 1;
    }

    Tuple!(int, int) farest(int n, int p, int d) {
        int nd = d + D[n];
        auto ret = tuple(nd, n);
        foreach (m; G[n]) if (m != p) ret = max(ret, farest(m, n, nd));
        return ret;
    }

    D[root] ^= 1;
    dfs(root, -1);

    auto s = farest(root, -1, 0);
    auto t = farest(s[1], -1, 0);
    auto u = s[1];
    auto v = t[1];
    
    int ans = (N - 1) * 2;
    foreach (i; 0..N) if (G[i].length > 1 && D[i]) ans += 1;
    ans -= t[0] * 2;
    
    ans.writeln;
}

nebukuro09の日記

AtCoder Regular Contest 097: F - Monochrome Cat

問題概要

解法

感想

コード (D言語)