AtCoder Regular Contest 041: D - 辺彩色

問題記録 AtCoder ARC #041 ARC 逆順の操作

https://atcoder.jp/contests/arc041/tasks/arc041_d

問題概要

N頂点M辺の無向グラフが与えられる。このグラフの各辺を以下のルールに従って赤か青のどちらかで塗っていくとき、各辺を初めに指定されている色で塗ることができるか判定せよ。

ルール: 自由に始点を選び、隣接頂点に移動することを繰り返す。奇数回目の移動で通った辺を赤、偶数回目の移動で通った辺を青で塗る。このとき古い色は新しい色で上書きされる。

N, M <= 2000

解法

操作を逆順にして終点→始点の移動を考えると、彩色が「最後に通ったときの色」ではなく「最初に通ったときの色」になる。つまり上書きという条件を消して考えることができるようになる。このようにすると一度通った辺を逆戻りすることなどが好きなだけ行えるようになるので、単純なDFSとかで「辺を最初に通るときの色を指定された色にできるか」を判定することができるようになる（色があってるときだけ遷移を行うDFSをやって、最終的に全部の辺を塗れたならOK）。始点（＝普通の順で見た場合の終点）の選び方は自由なので、全部の頂点を始点として試してこのようなDFSをすればよい。なお操作を逆順で見ているので赤青どちらの色から始めるかにも自由度がある。これも2通り両方試せばよい。O(N(N+M))で十分間に合う。

ただ一点例外があり、閉路内のすべての辺を正しく塗ることができるような奇数長の閉路が存在する場合、その他の辺をすべて任意の色で塗ることができるようになる。なぜならその閉路内を一周することで色を切り替えた状態で元の頂点に戻ってくることができるので、塗りたい辺を塗った後また閉路に戻ってきて好きな色に切り替える、という操作が無制限に行えるようになるからである。よってこのような閉路を発見した場合、答えは必ずYESになる。

感想

はい天才　公式解説が既にわかりやすくてこれを見て解説ACした　最近解いた旧ARC-Dの中ではかなり最近のAtCoderっぽさを感じる

上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！上書きは逆順！

コード (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, core.stdc.string;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto G = new Tuple!(int, int)[][](N);
    foreach (_; 0..M) {
        auto t = readln.split;
        auto u = t[0].to!int - 1;
        auto v = t[1].to!int - 1;
        int c = t[2] == "r";
        G[u] ~= tuple(v, c);
        G[v] ~= tuple(u, c);
    }


    bool odd_cycle;
    auto dist = new int[](N);
    auto painted = new bool[][](N, N);

    void dfs(int n, int c) {
        dist[n] = c;
        int nc = c ^ 1;
        foreach (e; G[n]) {
            int m = e[0];
            if (e[1] != nc) {
                continue;
            }
            if (!painted[n][m]) {
                painted[n][m] = painted[m][n] = true;
            }
            if (dist[m] != -1) {
                if (dist[m] != nc) {
                    odd_cycle = true;
                }
            } else {
                dfs(m, nc);
            }
        }
    }

    foreach (u; 0..N) {
        foreach (c; 0..2) {
            odd_cycle = false;
            dist[] = -1;
            foreach (i; 0..N) foreach (e; G[i]) painted[i][e[0]] = false;
            dfs(u, c);
            if (odd_cycle || N.iota.map!(u => G[u].map!(e => painted[u][e[0]]).all).all) {
                writeln("Yes");
                return;
            }
        }
    }

    writeln("No");
}