https://beta.atcoder.jp/contests/arc079/tasks/arc079_d

問題概要

N頂点N辺の弱連結有向グラフが与えられる。すべての頂点にそれぞれひとつの非負整数aiを割り当てることを考える。「ある頂点uから伸びる有向辺(u, v)でuと繋がっているすべての頂点vに割り当てられた整数の集合をSとしたとき、uに割り当てられた数がSのmex（Sに含まれていない最小の非負整数）である」という条件がすべての頂点において成り立つように整数を割り当てることは可能か判定せよ。

N <= 2*10⁵

解法

まずグラフは弱連結で、かつ頂点と辺の数が同じという条件から、このグラフは無向グラフとして見ると木に辺を一本足した形をしている。なのでこのグラフには高々一つしか閉路が存在しえない。辺の向きによっては閉路がひとつも存在しないこともありえる。

まず閉路が存在しない場合には必ず割り当てを行うことができる。出次数が0の頂点から順次決めていくとmexの値を確定させていくことができるからである。

次に閉路がひとつ存在する場合。このときも閉路に含まれない頂点に関しては上のやり方であらかじめ値を割り当てておくことができる。閉路に含まれる頂点の値は未確定で残るが、閉路ということはすべての頂点が出次数・入次数ともに1であるので、実はこれらの頂点がとりうる値は2通りしかない。

辺が伸びている先の未確定の値は無視してmexをとったときの値
辺が伸びている先の未確定の値が1で取ったmexだと仮定したときのmex

閉路中のひとつの頂点の値を決めれば他の閉路の頂点の値も自動的に決まるので、結局は適当にひとつ閉路の頂点を持ってきてこの2パターンを試せばよい。どちらかのパターンで矛盾なく割り当てられればOK, そうでなければNG.

なおmexの計算には少なくともO(集合の要素数)時間かかるが、各頂点で一回ずつmexをとる操作をしたとしても全部で1回ずつひとつの辺を見るだけなので、ならしO(N)になる。

感想

バグらせまくってしまった　ムキになって解法の理解をちゃんとやらずに適当にコードを弄りまくってしまったのが反省点

コード (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;

void main() {
    auto N = readln.chomp.to!int;
    auto G = new int[][](N);
    auto H = new int[][](N);
    auto D = new int[](N);
    foreach (i, p; readln.split.map!(to!int).enumerate) {
        G[p-1] ~= i.to!int;
        H[i] ~= p-1;
        D[p-1] += 1;
    }
    auto A = new int[](N);
    fill(A, -1);

    
    int mex(int n) {
        auto X = G[n].map!(j => A[j]).filter!"a >= 0".array.sort().uniq().array;
        int m = X.length.to!int;
        foreach (i; 0..X.length.to!int) {
            if (i != X[i]) {
                m = i;
                break;
            }
        }
        return m;
    }

    bool check() {
        return N.iota.map!(i => mex(i) == A[i]).all;
    }
    
    void dfs(int n) {
        A[n] = mex(n);
        foreach (m; H[n]) {
            D[m] -= 1;
            if (D[m] == 0 && A[m] == -1) {
                dfs(m);
            }
        }
    }


    
    foreach (i; 0..N) {
        if (D[i] == 0 && A[i] == -1) {
            dfs(i);
        }
    }

    if (!A.canFind(-1)) {
        writeln("POSSIBLE");
        return;
    }

    foreach (i; 0..N) {
        if (A[i] == -1) {
            int k = -1;
            foreach (j; H[i]) if (A[j] == -1) k = j;
            
            int m = mex(i);
            auto AA = new int[](N);
            auto DD = new int[](N);
            foreach (j; 0..N) AA[j] = A[j], DD[j] = D[j];
            A[i] = m;
            dfs(k);
            if (check) {
                writeln("POSSIBLE");
                return;
            }
            
            foreach (j; 0..N) A[j] = AA[j], D[j] = DD[j];
            auto X = G[i].map!(j => A[j]).filter!"a >= 0".array ~ m;
            X = X.sort().uniq().array;
            m = X.length.to!int;
            foreach (j; 0..X.length.to!int) {
                if (j != X[j]) {
                    m = j;
                    break;
                }
            }
            A[i] = m;
            dfs(k);
            if (check) {
                writeln("POSSIBLE");
                return;
            }
            break;
        }
    }

    writeln("IMPOSSIBLE");
}

nebukuro09の日記

AtCoder Regular Contest 079: F - Namori Grundy

問題概要

解法

感想

コード (D言語)