SoundHound Programming Contest 2018 Masters Tournament 本戦: E - Hash Swapping

問題記録 AtCoder SoundHound2018Masters本戦 平方分割

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_e

問題概要

長さNの文字列がM個与えられる。それらに対するQ個のクエリを順次処理せよ。

  • swapクエリ: x番目の文字列とy番目の文字列の、l番目からr番目の文字を入れ替える
  • hashクエリ: x番目の文字列のハッシュ値（問題文参照）を求めて出力する

N, Q <= 2*105

M <= 20

解法

TL長めなので平方分割でできる。平方分割に関しては前も同じことを書いたが↓の記事を見るのが一番わかりやすいと思う。

なお上の記事だと値をまとめる用のbucketSumと1個1個の値を持っておく用のdataをそれぞれ1個の配列で持っているが、この問題だとswap操作が若干めんどくさいので、bucketSumとdataをそれぞれ区間ごとに細切れにして持っておくみたいなことをしたら実装がある程度簡単になった。

感想

本番平方分割したらいいんじゃねまでは行ったけど全然時間足りず。落ち着いて書き直したら自分の中で平方分割の実装がなんとなく整理ついてきたので次回以降は何卒

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

immutable long MOD = 10^^9 + 7;
immutable long BASE = 10^^6;
immutable int SIZE = 450;
long BUCKET_BASE;

class Node {
    long big;
    long[] small;

    this(string s) {
        small = new long[](SIZE);
        foreach (i; 0..s.length) {
            small[i] = s[i] - 'a' + 1;
        }
        hash;
    }

    void hash() {
        big = 0;
        foreach_reverse (i; 0..SIZE) {
            big = big * BASE % MOD;
            big = (big + small[i]) % MOD;
        }
    }
}


long calc(const Node[] str, int l, int r) {
    long ret = 0;
    foreach_reverse (i; l/SIZE..(r-1)/SIZE+1) {
        int bl = i * SIZE;
        int br = i * SIZE + SIZE;
        if (l > bl || r < br) {
            foreach_reverse (j; max(l, bl)..min(r, br)) {
                ret = ret * BASE % MOD;
                ret = (ret + str[i].small[j%SIZE]) % MOD;
            }
        } else {
            ret = ret * BUCKET_BASE % MOD;
            ret = (ret + str[i].big) % MOD;
        }
    }
    return ret;
}

void nswap(Node[] x, Node[] y, int l, int r) {
    foreach (i; l/SIZE..(r-1)/SIZE+1) {
        int bl = i * SIZE;
        int br = i * SIZE + SIZE;
        if (l > bl || r < br) {
            foreach (j; max(l, bl)..min(r, br)) {
                swap(x[i].small[j%SIZE], y[i].small[j%SIZE]);
            }
            x[i].hash;
            y[i].hash;
        } else {
            swap(x[i].big, y[i].big);
            swap(x[i].small, y[i].small);
        }
    }
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

void main() {
    BUCKET_BASE = powmod(BASE, SIZE, MOD);
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = M.iota.map!(_ => readln.chomp).array;
    
    auto strs = new Node[][](M, SIZE);
    foreach (i; 0..M) 
        foreach (j; 0..SIZE) 
            if (j*SIZE < N) 
                strs[i][j] = new Node(S[i][j*SIZE..min(N, j*SIZE+SIZE)]);
    
    auto Q = readln.chomp.to!int;
    
    while (Q--) {
        auto q = readln.split.map!(to!int);
        int type = q[0];
        int x = q[1] - 1;
        int y = q[2] - 1;
        int l = q[3] - 1;
        int r = q[4];
        
        if (type == 1) {
            nswap(strs[x], strs[y], l, r);
        } else {
            calc(strs[x], l, r).writeln;
        }
    }
}

SoundHound Programming Contest 2018 Masters Tournament 本戦: D - Propagating Edges

問題記録 AtCoder SoundHound2018Masters本戦

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_d

問題概要

N頂点0辺の無向グラフに対してQ個のクエリが飛んでくるので順次処理せよ。

  • addクエリ: 頂点u, v間に辺を張る
  • completeクエリ: 「頂点u」と「頂点uと連結な頂点」の集合に含まれるすべての頂点間に辺を張る
  • checkクエリ: 頂点u, v間に辺が張られているかどうかを答える

N <= 105

Q <= 2*105

解法

2頂点間に辺が張られるのは当然ながらaddクエリかcompleteクエリのどちらかの影響である。このうちaddクエリの結果張られた辺は全部覚えておくことができる。一方でcompleteクエリは愚直にやると時間も空間もO(N2)かかってしまうのでここをなんとかする必要がある。結論からいうとcompleteクエリは頂点の縮約操作と見なすことで効率的に処理することができる。具体的にはaddクエリによって追加された辺に基づいて普通にグラフを構築しておき、completeクエリが来たら頂点uと連結な頂点をDFSで列挙してひとつの頂点にまとめてしまう。まとめる操作はUnionFindで実現できる。こうしておくと頂点u, v間に辺が張られているのは 「addクエリの記録にu, vがある」もしくは「uとvがUnionFindで同じ集合にまとめられている」ときのみであるから、checkクエリの際にはこれだけチェックすればよい。以降のaddクエリ、completeクエリは縮約後の頂点に読み替えて操作を行えばよい（ただし「addクエリの直接的な記録」は元の頂点で持っておく）。縮約操作は1つの頂点につきたかだか1回しか行われないので、計算量は増えない。

感想

すいません本番で通したんですが完全に嘘解法でした　自分で一瞬で撃墜してしまった

改めてちゃんとした解法を見てやったらUnionFindで管理してるのが連結頂点の集合ではなくcompleteになった集合というところで頭がこんがらがって大変だった

コード

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 s = readln.split.map!(to!int);
    auto N = s[0];
    auto Q = s[1];
    
    auto uf = new UnionFind(N);
    auto added = new bool[int][](N);
    auto G = new bool[int][](N);
    bool[int] used;

    void dfs(int n) {
        if (n in used) return;
        used[n] = true;
        foreach (m; G[n].keys) {
            if (m in used) continue;
            dfs(m);
        }
    }

    while (Q--) {
        auto q = readln.split.map!(to!int);
        int type = q[0];
        int u = q[1] - 1;
        int v = q[2] - 1;
        int up = uf.find(u);
        int vp = v >= 0 ? uf.find(v) : 0;
        if (type == 1) {
            added[u][v] = true;
            added[v][u] = true;
            G[up][vp] = true;
            G[vp][up] = true;
        } else if (type == 2) {
            auto hoge = used.keys.dup;
            foreach (h; hoge) used.remove(h);
            dfs(up);
            foreach (k; used.keys) {
                uf.unite(up, k);
                hoge = G[k].keys.dup;
                foreach (h; hoge) G[k].remove(h);
            }
        } else {
            if (v in added[u] || up == vp) {
                writeln("Yes");
            } else {
                writeln("No");
            }
        }
    }
}

class UnionFind {
    int N;
    int[] table;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
    }

    int find(int x) {
        return table[x] < 0 ? x : find(table[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (table[x] > table[y]) swap(x, y);
        table[x] += table[y];
        table[y] = x;
    }
}

SoundHound Programming Contest 2018 Masters Tournament 本戦: C - Not Too Close

問題記録 AtCoder SoundHound2018Masters本戦 DP

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_c

問題概要

N頂点の無向グラフで、頂点に1からNまでの番号がついており、自己辺・多重辺を持たず、すべての辺の長さを1としたとき頂点1-2間の最短距離がDであるようなものが何通りあるか求めよ。

D < N <= 30

解法

頂点1を基準として、「頂点1から距離1の頂点」「距離2の頂点」...という風にどんどん頂点をくっつけてグラフを構成していくことを考える。この数え上げは以下のDPで行える。

dp(i, j, k): 距離iまで構成し、j個の頂点を使い、最後にくっつけた距離iの頂点の数がk個であるグラフの数

距離dの頂点を追加するときは、以下のことを考慮に入れる。

  1. 何個の頂点を距離dとしてくっつけるか
  2. 頂点の選び方は何通りあるか
  3. 辺の張り方は何通りあるか

頂点の選び方は（未使用頂点の数）から（使用頂点の数）を選ぶ組合せなのでコンビネーションで計算できる。ただし頂点2の扱いに注意が必要で、距離がDではないときに頂点2を選んではいけないし、候補にも入れてはいけない。逆に距離がDの時は頂点2は必ず選ぶ。この点で上の組合せの計算には微妙に足し引きが入る。

辺の張り方に関しては以下のことを考慮に入れる → 距離(d-1)の頂点のうち少なくともひとつには辺を張らなければならない。距離(d-2)以下の頂点には辺を張ってはならない。また距離dの頂点同士は好きなだけ辺を張れる。

最後に作ったグラフのうち余った頂点がある場合、その余った頂点同士でいくらでも辺が張れるという点に留意する。

状態数がO(N3), 遷移がO(N)（何個頂点をくっつけるかの列挙）なのでO(N4). 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;

immutable long MOD = 10^^9 + 7;
long[] F;
long[] G;

void main() {
    F = new long[](50);
    G = new long[](50);
    F[0] = F[1] = 1;
    foreach (i; 2..50) F[i] = F[i-1] * i % MOD;
    foreach (i; 0..50) G[i] = powmod(F[i], MOD-2, MOD);

    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto D = s[1];

    auto dp = new long[][][](N, N+1, N+1);
    dp[0][1][1] = 1;

    foreach (d; 1..N) {
        foreach (using; 1..N+1) {
            foreach (used; 1..N+1) {
                if (using + used > N) continue;
                foreach (last; 1..N+1) {
                    long rest = d <= D ? N - used - 1 : N - used;
                    long k = d == D ? using - 1 : using;
                    if (rest < k) continue;
                    long tmp = comb(rest, k);
                    tmp = tmp * powmod(powmod(2, last, MOD) - 1, using, MOD) % MOD;
                    tmp = tmp * powmod(2, using * (using - 1) / 2, MOD) % MOD;
                    (dp[d][using+used][using] += dp[d-1][used][last] * tmp % MOD) %= MOD;
                }
            }
        }
    }

    long ans = 0;
    foreach (d; D..N)
        foreach (n; d+1..N+1)
            foreach (last; 0..N+1) {
                long tmp = dp[d][n][last];
                tmp = tmp * powmod(2, (N-n)*(N-n-1)/2, MOD) % MOD;
                ans = (ans + tmp) % MOD;
            }
    ans.writeln;
}

long powmod(long a, long x, long m) {
    a %= m;
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

long comb(long n, long k) {
    return F[n] * G[n-k] % MOD * G[k] % MOD;
}

SoundHound Programming Contest 2018 Masters Tournament 本戦: B - Neutralize

問題記録 AtCoder SoundHound2018Masters本戦 DP

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b

問題概要

N要素の数列Aが与えられる。Aの中から連続するK個の要素を選んでその値を全て0にするという操作を何度でも行えるとき、最終的なAの全要素の和の最大値を求めよ。

N <= 2×105

-109 <= Aの要素 <= 109

解法

まず「連続するK個を選んで」は「連続するK個以上を選んで」と言い換えられる。一度K個連続で潰したあとひとつずらしてまた潰せば(K+1)個連続で0にできるからである。

また操作の順番は最終的な結果に影響を及ぼさないので、左の要素から順に操作を行うかどうか決めていってよい。もしその要素を残すのであれば合計にその要素の値を組み入れて次の要素へ進む、潰すのであれば合計はいじらずK個以上先の要素へスキップする、という感じ。

ここまでを踏まえるとDPできそうな感じになる。K個以上先へのスキップという遷移を愚直にやるとO(N2）かかるのでNGだが、「直前でスキップした結果今見ている要素にたどりついたのであれば、1つ飛ばしのスキップが可能」（さっきの潰した区間をさらに1伸ばすイメージ）という風にみなせば「残して1個進む」「K個スキップする」「直前でスキップしてるので今の要素をスキップして1個進む」の3種類の遷移だけ考えればよくなるので（インデックス、直前にスキップしたか）を状態にとるDPができてO(N)になる。

感想

DPにたどり着くまで時間がかかって全然解けなかったのでかなり焦った

遷移は変な工夫しないでも遅延セグ木とかでできそう　もらうDPなら普通のセグ木でもいける？

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

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto K = s[1];
    auto A = N.iota.map!(_ => readln.chomp.to!long).array;
    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = B[i] + A[i];

    auto dp = new long[][](N+1, 2);
    foreach (i; 0..N+1) fill(dp[i], -INF);
    dp[0][0] = 0;

    foreach (i; 0..N) {
        dp[i+1][0] = max(dp[i+1][0], max(dp[i][0], dp[i][1]) + A[i]);
        dp[i+1][1] = max(dp[i+1][1], dp[i][1]);
        if (i+K <= N)
            dp[i+K][1] = max(dp[i+K][1], dp[i].reduce!max);
    }

    max(dp[N][0], dp[N][1], 0).writeln;
}

Codeforces Round #499 (Div. 1): D. Mars rover

問題記録 Codeforces CF #499

http://codeforces.com/contest/1010/problem/D

問題概要

N頂点の根付き木が与えられる。すべての葉にはあらかじめ1か0の入力が与えられており、葉以外の頂点はすべて「子から来たビットを入力として論理演算をし、その出力を親に送る」機能を持っている。演算の種類はNOT, AND, OR, XORであり、NOTの頂点はひとつの子、それ以外は2つの子を持つ。すべての葉について、その葉の入力のみ反転させたとき、最終的に根が出力するビットが何になるかを求めよ。

N <= 106

解法

まずあらかじめ与えられた入力での計算結果がどうなるかは事前にO(N)で計算できる。その上でまた根から順に「もし子が送ってくる出力が反転したら、この頂点の出力も反転するか」を求めていく。例えばANDの頂点で両方の子がともに0ならば、どちらかの子が反転したところで結局出力は0になる（＝その下の葉で入力が何になろうと最終的な答えは変わらない）。一方で左の子が1, 右の子が0だった場合、右の子が反転するとANDの出力も0から1に反転する。よって右の子の反転は最終的な結果も反転させうる（もちろんそれより上の頂点で反転が無意味になってたら駄目）。という感じで場合分けしてDFSしていくと最終的にそれぞれの葉で反転が有効か無効かがわかる。有効なら最初に求めた根の出力を反転させればいいし、そうでないならそのままの出力を使えばいい。

感想

まったく見当違いなことをしていた（NOTは縮約できるじゃん→そしたら2分木になるから高さlogNじゃん→は？）

コード (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() {
    enum OP {IN, NOT, AND, OR, XOR};
    auto N = readln.chomp.to!int;
    auto G = new int[][](N, 2);
    auto P = new int[](N);
    auto B = new bool[](N);
    auto V = new bool[](N);
    auto ops = new OP[](N);

    foreach (i; 0..N) {
        auto s = readln.split;
        string op = s[0];
        foreach (j; 1..s.length) {
            int a = s[j].to!int - 1;
            G[i][j-1] = a;
            if (op != "IN")
                P[a] = i;
        }
        
        if (op == "IN") {
            ops[i] = OP.IN;
            B[i] = s[1] == "1";
        } else if (op == "NOT") {
            ops[i] = OP.NOT;
        } else if (op == "AND") {
            ops[i] = OP.AND;
        } else if (op == "OR") {
            ops[i] = OP.OR;
        } else {
            ops[i] = OP.XOR;
        }
    }

    bool operate(int n) {
        bool a = G[n][0] >= 0 ? B[G[n][0]] : 0;
        bool b = G[n][1] >= 0 ? B[G[n][1]] : 0;
        if (ops[n] == OP.IN) {
            return B[n];
        } else if (ops[n] == OP.NOT) {
            return !a;
        } else if (ops[n] == OP.AND) {
            return a & b;
        } else if (ops[n] == OP.OR) {
            return a | b;
        } else if (ops[n] == OP.XOR) {
            return a ^ b;
        }
        return 0;
    }

    void init(int n) {
        if (ops[n] == OP.IN) {
            return;
        } else if (ops[n] == OP.NOT) {
            int a = G[n][0];
            init(a);
        } else {
            int a = G[n][0];
            int b = G[n][1];
            init(a);
            init(b);
        }
        B[n] = operate(n);
    }

    void dfs(int n, bool valid) {
        V[n] = valid;
        int a = G[n][0];
        int b = G[n][1];
        if (ops[n] == OP.NOT) {
            dfs(a, valid);
        } else if (ops[n] == OP.AND) {
            if (B[a] && B[b]) {
                dfs(a, valid);
                dfs(b, valid);
            } else if (B[a] && !B[b]) {
                dfs(a, false);
                dfs(b, valid);
            } else if (!B[a] && B[b]) {
                dfs(a, valid);
                dfs(b, false);
            } else {
                dfs(a, false);
                dfs(b, false);
            }
        } else if (ops[n] == OP.OR) {
            if (B[a] && B[b]) {
                dfs(a, false);
                dfs(b, false);
            } else if (B[a] && !B[b]) {
                dfs(a, valid);
                dfs(b, false);
            } else if (!B[a] && B[b]) {
                dfs(a, false);
                dfs(b, valid);
            } else {
                dfs(a, valid);
                dfs(b, valid);
            }
        } else if (ops[n] == OP.XOR) {
            dfs(a, valid);
            dfs(b, valid);
        }
    }

    init(0);
    dfs(0, true);
    N.iota.filter!(i => ops[i] == OP.IN).map!(i => V[i] ? !B[0] : B[0]).map!(i => i.to!int.to!string).join("").writeln;
}

AtCoder Regular Contest 097: F - Monochrome Cat

問題記録 AtCoder ARC ARC #097 オイラーツアー

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

問題概要

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

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

N <= 105

解法

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

すべての葉が白であるので、少なくとも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;
}

AtCoder Regular Contest 079: F - Namori Grundy

問題記録 AtCoder ARC ARC #079

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

問題概要

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

N <= 2*105

解法

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

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

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

  1. 辺が伸びている先の未確定の値は無視してmexをとったときの値
  2. 辺が伸びている先の未確定の値が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");
}