2019-02-25

Aizu Online Judge 2710: Marked Ancestor

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2170

問題概要

N頂点の木とQ個のクエリが与えられる。木は常に頂点1が根である。また初めは頂点1だけにマークがされている。クエリにはMとQの2種類があり、Mクエリでは指定された頂点にマークを付ける。Qクエリでは指定された頂点の祖先でマークが付いているもののうちその頂点から最も近い頂点を求める（祖先には自分も含む）。Qクエリで求めた頂点番号の合計を出力せよ。

N, Q <= 10⁵

解法

マークを付ける操作を考えると、これは「マークを付けた頂点を根とする部分木を木から切り離す」操作ともいえる。切り離された部分木に含まれるノードたちにとっては、その時点での最も近いマークされた祖先はその部分木の根である。

このように見るとこれはもともとひとつだった集まりをクエリごとに分断していき、途中途中でその集まりの親を聞かれている問題と捉えることができる。このような操作を要求される問題に対する典型テクとして「操作を逆順で見ていく」というのがあり、この問題にもそれを使うことができる。

なぜ逆順で見るのがいいかというと、「集合を切って分割していく操作」というのは扱いづらいが、これを逆から見た「分割されている集合たちを繋いでいく操作」はかなり扱いやすい性質を持っているからである。具体的にはUnionFindが使える。

というわけでクエリを逆回しに見ていくことにしたいので、まずクエリを先に読んですべてのマークがついたことにしてしまう。そしてこの時点でマークがついていないノードはすべてそのノードの親とuniteする。このようにしてできる集合たちが上述の「部分木を切り離していく操作」を最後まで行ったときのそれぞれの部分木に対応する。あとはここからまたクエリを逆順に見ていく。

逆順に見ていってQクエリが飛んできた場合、指定された頂点が属する集合の根に当たる頂点、すなわち最も深さが小さい頂点を答えればよい。これはUnionFindを適当に改造してそのような情報を持たせることにすれば実装できる。

Mクエリが飛んできた場合、その頂点からマークを剥がすことになる。これはつまり部分木を元の木にくっつける作業で、マークを剥がす頂点とその直接の親をuniteすればよい。ただしその頂点に何度もマークが行われているときは注意が必要で、この場合いちばん最初につけられたマーク以外には意味がないため、他は無視しないといけない。

感想

AOJ-ICPC軽く埋めたろかと思って見たけど普通にむずくて解けなかった

木の頂点をUFで管理するという発想がなかったのは反省

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

bool solve() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto Q = s[1];
    if (N == 0) return false;

    auto G = new int[][](N);
    auto D = new int[](N);
    auto P = new int[](N);
    P[0] = -1;

    foreach (i; 1..N) {
        auto n = readln.chomp.to!int;
        P[i] = n-1;
        G[i] ~= n-1;
        G[n-1] ~= i;
    }

    void dfs(int n, int p, int d) {
        D[n] = d;
        foreach (m; G[n]) if (m != p) dfs(m, n, d+1);
    }

    dfs(0, -1, 0);

    Tuple!(int, int)[] queries;
    auto marked = new int[](N);

    foreach (i; 1..Q+1) {
        auto t = readln.split;
        auto n = t[1].to!int - 1;
        if (t[0] == "M" && !marked[n]) {
            queries ~= tuple(0, n);
            marked[n] = i;
        } else if (t[0] == "Q") {
            queries ~= tuple(1, n);
        }
    }

    auto uf = new UnionFind(N, D);
    foreach (i; 0..N) if (!marked[i]) uf.unite(i, P[i]);
    long ans = 0;

    foreach_reverse (q; queries) {
        if (q[0] == 0) {
            uf.unite(q[1], P[q[1]]);
        } else {
            ans += uf.find(q[1]) + 1;
        }
    }

    ans.writeln;

    return true;
}

void main() {
    while (solve()) {}
}


class UnionFind {
    int N;
    int[] table;
    int[] depth;

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

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

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

2019-02-14

AtCoder Regular Contest 084: F - XorShift

AtCoder ARC ARC #084 GCD 多項式問題記録

https://atcoder.jp/contests/arc084/tasks/arc084_d

問題概要

N個の非負整数Aiが黒板に書かれている。黒板に書いてある数に対して「数をひとつ選びそれを2倍したものを黒板に書き足す」「数をふたつ選びそれらのbitwise xorをとったものを黒板に書き足す」という操作を好きな順番で何度でも行えるとき、黒板に書かれうる数のうち大きさがX以下であるものが何種類存在するか求めよ。

1 <= N <= 6

1 <= X, Ai <= 2⁴⁰⁰⁰

解法

なぜそうするかはとりあえずおいといて、与えられた数の2進表記を多項式の係数とみなすことにする。 1111 は x³ + x² + x¹ + 1 となり、 101 は x² + 1 となる、いう具合である。このようにすると「ある数を2倍する操作」は「多項式にxをかける操作」とみなすことができるようになる。また「2つの数のxorをとる操作」は「多項式同士の足し算をする操作（ただし係数はmod2で考える）」になる。

ではこのような操作を繰り返していって作ることのできる多項式はどのようなものになるか？実はこれはGCDのような概念を考えることで解決することができる。どういうことかというと、「与えられたN個の多項式に上の操作を繰り返して作れる多項式の集合」を考えたとき、実はそれとまったく同じ集合を「ひとつの多項式だけが含まれる集合」から始めても作ることができる。その「ひとつの多項式」をここではGCDと呼んでいる。（普通の整数のGCDも、上の操作を「整数倍」と「足し算・引き算」に置き換えると同じような性質がある（あるよね？）（なかったらすいません））

GCDの求め方だが、互除法と同じ形でやれる。すなわち次数が大きい方の多項式をA, 次数の小さい方（同じでも良い）をBとして、最大次数が揃うまでBにxをかけてから足す。その結果をCとして再帰的に同じことをし続ける、という形である。これでGCDとなる多項式を求めることができる。

GCDとなる多項式Gが求まったら、あとはそれを使ってどんな数が作れるかを考えればよい。ここでGの最大次数をdとすると、実はd次より上の項はどんな組み合わせでも自由につくることができる。そして(d-1)次より下の項はそれに応じて自動的に一意に決まる。なぜなら x倍の操作でGを左にシフトしていくことはできるが右にシフトさせることはできないからである。もしd次以上の項の係数をフリップさせたいのであればGをそこまで左シフトさせてから足せばいいが、(d-1)次以下に対してはそれができないので自由にいじることはできない。

よって答えとしては、基本的にXのd次以上の項は全部自由に作れるので、そこの部分だけを切り取って2進数と見なした数は全部作ることができる。ただしひとつだけ例外があって、作った結果d次以上の全部の項がXと一致している場合、後ろの桁の結果によってはXをオーバーしている可能性がある。なのでそのケースだけは実際にGから構成してみてXを超えないか確かめる必要がある。もし超えていたらその数は作れないので除く。あとは0も数える対象であるのでそれを忘れず含めるようにする。

感想

わからんが、とにかく書いた

GCDが「集合の要素hoge倍する・または集合の要素同士を足し算（引き算）して集合に加えていく」という操作をするときの最小要素？的な感じになるというのはもっとちゃんと理解しておくべきことっぽい

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

immutable long MOD = 998244353;

int[] gcd(int[] a, int[] b) {
    while (true) {
        if (a.length < b.length) swap(a, b);
        if (b.length == 0) return a.dup;
        ulong msb = a.length;

        foreach (i; 0..a.length) {
            if (i < b.length) {
                a[i] ^= b[i];
            }
            if (a[i]) {
                msb = min(i, msb);
            }
        }

        a = a[msb..$];
    }
}

void main() {
    auto s = readln.split;
    auto N = s[0].to!int;
    auto X = s[1].map!(a => to!int(a == '1')).array;
    auto P = N.iota.map!(_ => readln.chomp.map!(a => to!int(a == '1')).array).array;

    auto G = P.front.dup;
    foreach (i; 1..N) G = gcd(G, P[i].dup);

    long ans = 0;

    for (long i = X.length.to!long - G.length.to!long, tmp = 1; i >= 0; i -= 1, tmp = tmp * 2 % MOD) {
        if (X[i]) {
            ans = (ans + tmp) % MOD;
        }
    }


    auto M = new int[](X.length);

    for (int i = 0; i + G.length <= M.length; ++i) {
        if (M[i] != X[i]) {
            for (int j = 0; j < G.length; ++j) {
                M[i+j] ^= G[j];
            }
        }
    }

    if (M <= X) {
        ans = (ans + 1)  % MOD;
    }

    ans.writeln;
}

2019-02-07

DISCO presents ディスカバリーチャンネルコードコンテスト2019 予選: D - チップ・ストーリー　～黄金編～

問題記録 AtCoder 中国剰余定理

https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d

問題概要

1以上10¹²以下の秘密の整数Nがある。Nをi進数で表したときの各桁の数字の和Ai (i = 2〜30) がそれぞれ与えられるので、条件を満たすNが存在するか判定せよ。存在する場合にはそのようなNをひとつ示せ。

解法

まず重要な事実として「整数nを(k-1)で割ったあまりと、nをk進数で表したときの桁和を(k-1)で割ったあまりは等しい」というものがある。つまり N = Ai (mod (i-1)) である。

このように見ると、「いろんな進数でのNの桁和」という情報は「いろんな数でNを割ったときのあまり」の情報として使うことができる。そしてこれは中国剰余定理と非常に似た形をしている。

中国剰余定理: あるひとつの整数nを互いに素ないくつかの数 m1, m2, ..., mk で割ったときのあまりがわかっているとき、nをm1×m2× ... ×mkで割ったときのあまりは一意に定まる。

この定理は解があるよ〜という話しかしていないが、実際に復元する手順についてもいろいろやり方が知られている（人のコードを見る限り競プロでは拡張ユークリッドの互除法を用いて実装するのが一般的っぽい（が、自分はそれをよく理解してないのでググって出てきた手計算での復元方法っぽいやつを実装した http://did2.blog64.fc2.com/blog-entry-86.html））。

さてこの定理を使うためにはmodがすべて互いに素でなければならない。というわけでi=2〜30の中からi-1が素数のものだけを抜き出してきて計算する。すると N の mod (2×3×5×...×29) での値を出すことができる(modは1〜29の中のすべての素数の積)。2×3×5×...×29 がだいたい 6.5*10⁹ くらいで、Nは10¹²以下という制約があるので、あとはこのmodの条件を満たす数を総当たりして、逐一条件を満たすかをチェックしていけばよい。

感想

中国剰余定理よく知らなくて解説読んだ後放置してたけどこの問題の範囲ではそんなに難しいことが要求されてるわけではなかった　整数論べんきょうしたいですね

コード(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 A = 29.iota.map!(_ => readln.chomp.to!long).array;
    A = 0 ~ A;

    const long[] P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
    const long PP = P.reduce!"a * b";
    long ans = 0;

    foreach (p; P) {
        // x * (PP / p) = A[p] (mod p)
        long x = A[p] * powmod((PP / p % p), p - 2, p) % p;
        ans += x * (PP / p) % PP;
        ans %= PP;
    }

    while (ans <= 10L^^12) {
        if (iota(1, 30).map!(i => digit_sum(ans, i+1) == A[i]).all) {
            ans.writeln;
            return;
        }
        ans += PP;
    }

    writeln("invalid");
}

long digit_sum(long x, long base) {
    long ret = 0;
    while (x > 0) {
        ret += x % base;
        x /= base;
    }
    return ret;
}

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;
}

2019-02-02

AtCoder Grand Contest 025: D - Choosing Points

問題記録 AtCoder AGC AGC #025 2部グラフ格子点独立集合

https://atcoder.jp/contests/agc025/tasks/agc025_d

問題概要

正整数N, D1, D2が与えられる。xy平面上で 0 <= x < 2N, 0 <= y < 2N に存在する整数座標の点の集合であって、要素数がN²個でありかつ集合の中のどの2点を取ってもその2点の距離がsqrt(D1)でもsqrt(D2)でもないという条件を満たす集合をひとつ構成せよ。このような集合は必ず存在する。

N <= 300

D1, D2 <= 2*10⁵

解法

2次元平面上で距離が定数Dであるような整数座標の点を繋いでできるグラフは必ず2部グラフになる。sqrt(D1), sqrt(D2)でそれぞれこのような2部グラフを作った上でそれぞれの点を2色で塗り分けると、すべての点は以下の4種類のいずれかひとつに分類されることになる。

D1のグラフで色1, D2のグラフで色1
D1のグラフで色1, D2のグラフで色2
D1のグラフで色2, D2のグラフで色1
D1のグラフで色2, D2のグラフで色2

作ったグラフの性質上、これら4つの集合においては集合内のどの相異なる2点を持ってきてもそれらの距離がsqrt(D1), sqrt(D2)になることはない（その距離になるためには元のグラフで隣接している必要があるが、2部グラフで同色になるならば隣接ではありえない）。

また鳩の巣原理よりこれら4つの分類のうち必ずひとつ以上には (全体の点の数 / 4) 個以上の点が属することになる。この問題で考えるべき格子点は4N²個なので、これらのうち必ずひとつはN²個以上になる。よってそれを答えとすればよい。

なおグラフを作るのを愚直にやるとO(N⁴)になってしまうが、最初に「原点からの距離がsqrt(D1), sqrt(D2)となる整数座標の点」を前計算で列挙しておけば、これは各x座標においてたかだか2点しか存在しないので、各点においてO(N)で距離sqrt(D1), sqrt(D2)の点が列挙できるためO(N³)で済む。

作ったグラフが必ず2部グラフになることの証明は公式解説に詳しい。

感想

わかりません……　格子点をある定数の距離で結ぶと2部グラフになる　は覚えとくとべんりそう

あと参考にした解説記事 (AtCoder Grand Contest 025 - Unhappy Go Lucky!) で印象に残った文章があるので教訓として引用しときます

まずは与えられたグラフの特徴を考察する。独立集合は、二部グラフであれば楽勝で取れる。これが「独立集合」と聞いた瞬間に「二部グラフでは」と行かないと辛い。 AtCoder Grand Contest 025 - Unhappy Go Lucky!

コード (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 D = [s[1], s[2]];
    auto G = new int[][][](2, 4*N*N);
    auto C = new int[][](2, 4*N*N);
    C[0][] = C[1][] = -1;

    auto xyd = new int[][](2, 2*N);

    foreach (i; 0..2) {
        xyd[i][] = -1;
        foreach (x; 0..2*N) {
            foreach (y; 0..2*N) {
                if (x*x+y*y == D[i]) {
                    xyd[i][x] = y;
                }
            }
        }
    }


    foreach (i; 0..2) {
        foreach (x1; 0..2*N) {
            foreach (y1; 0..2*N) {
                foreach (x2; x1..2*N) {
                    if (xyd[i][x2-x1] == -1) continue;
                    foreach (k; [-1, 1]) {
                        int y2 = y1 + k * xyd[i][x2-x1];
                        if (y2 < 0 || y2 >= 2*N) continue;
                        G[i][x1*2*N+y1] ~= x2*2*N+y2;
                        G[i][x2*2*N+y2] ~= x1*2*N+y1;
                    }
                }
            }
        }
    }

    foreach (i; 0..2) {
        foreach (x1; 0..2*N) {
            foreach (y1; 0..2*N) {
                if (C[i][x1*2*N+y1] == -1) {
                    dfs(x1*2*N+y1, 0, G[i], C[i]);
                }
            }
        }
    }

    int cnt = 0;

    foreach (i; 0..2) {
        foreach (j; 0..2) {
            if (iota(4*N*N).map!(k => C[i][k] == i && C[j][k] == j).sum < N*N) continue;
            foreach (x; 0..2*N) {
                foreach (y; 0..2*N) {
                    if (C[0][x*2*N+y] == i && C[1][x*2*N+y] == j) {
                        writeln(x, " ", y);
                        ++cnt;
                        if (cnt >= N * N) {
                            return;
                        }
                    }
                }
            }
        }
    }
}

void dfs(int n, int c, ref int[][] G, ref int[] C) {
    if (C[n] != -1) return;
    C[n] = c;
    foreach (m; G[n]) if (C[m] == -1) dfs(m, c^1, G, C);
}

2019-01-31

全国統一プログラミング王決定戦予選 / NIKKEI Programming Contest 2019: E - Weights on Vertices and Edges

AtCoder 問題記録日経コン UnionFind 逆順の操作

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e

問題概要

N頂点M辺の連結な無向グラフが与えられる。グラフの各頂点と各辺には重みが設定されている。辺をひとつ選んでグラフから削除するという操作を何回でも行えるとき、削除されていないすべての辺について、その辺の重みがその辺の属する連結成分の全頂点の重みの総和を超えないという条件が満たされた状態するために最小何本の辺を削除する必要があるか求めよ。

N, M <= 10⁵

解法

明らかに重い辺ほど削除対象になりやすいことを考えると、以下のようなステップで問題を解くことができる。

まだ削除もマークもされていない中で最大の重みを持つ辺を見る。
その辺が条件を満たしていないならば、削除する。
その辺が条件を満たしているならば、その辺が属する連結成分のすべての辺は必ず条件を満たす。なのでそのような辺をすべて残存確定としてマークする。
削除もマークもされていない辺がなくなるまで1に戻ってこれを繰り返す。

これをそのまま実装しようとすると、辺の削除とそれに伴う連結成分の分割が必要になるが、そのような操作は基本的に難しい。なのでこの類の操作を要求される問題でよく用いられるテクニックである「操作を逆順で考える」をやる。つまりはじめは辺が全部削除された状態で頂点だけがあり、だんだん辺が追加されていく、というような形である。辺を追加して連結成分をくっつけていく操作はUnionFindのようなデータ構造で簡単に行えるため、こちらの方が操作もしやすく見通しがよい。

上の操作を逆順にやる場合、軽い辺から順に繋いでいくことになるが、上に書いたことをそのままやることは難しい。特にステップ3の他の辺を残存確定とするところが邪魔で、これを逆操作で再現するのはどうにも無理っぽい感じがする（逆から見ていく以上、その辺が残存確定になっているかどうかは知りようがないため）。なので逆操作をしやすくするために、上の操作を少し言い換える。具体的には毎ステップ必ず削除を行うようにして、逆操作における追加操作と対応がつくようにする。手順としては以下のようになる。

まだ見ていない中で最大の重みの辺を見る。
その辺が条件を満たしているならば、その辺が属する連結成分のすべて辺は必ず条件を満たす。なのでそのような辺をすべてマークする。
その辺を必ず削除する。ただしその辺がマークされている場合、最終的な答えの削除数にはカウントしない。
すべての辺を見るまでこれを繰り返す。

このようにすると毎回辺の削除が行われるので逆操作との対応がつきやすくなる。これに基づいた逆操作は以下のようになる。

まだ見ていない中で最小の重みの辺を見る。
その辺を繋げる。つまり辺が頂点(u, v)間を繋ぐとき、uの属する連結成分とvの属する連結成分をひとつの連結成分にまとめる。この操作は元の操作における削除に対応しているため、コストに+1を加算する。
辺の重みがこれによってできた連結成分内の全頂点の重みの総和未満である場合、この時点でこの連結成分に属している辺はすべて条件を満たす。よってそれらすべての辺の削除はなかったことにできるので、それらすべての辺によって足されたコストを無効にする。
すべての辺を見るまでこれを繰り返す。

実装上ではUnionFindの各連結成分にコストを持たせておくと管理しやすい（uniteするときはコストを足す、無効にするときはゼロにする、というようにすると最終的にひとつの連結成分になったときのコストが答えになる）。

感想

アルメリアさんのツイートを見て解けました

解法はなんかどう書いても天下り的な感じになってしまってむずかしい　おもいつきたいね

コード (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 X = readln.split.map!(to!long).array;
    auto G = new Tuple!(int, long)[][](N);
    auto E = new Tuple!(int, int, long)[](M);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long);
        G[s[1]-1] ~= tuple(s[0]-1, s[2].to!long);
        E[i] = tuple(s[0]-1, s[1]-1, s[2].to!long);
    }

    E.sort!"a[2] < b[2]";
    auto uf = new UnionFind(N, X);

    foreach (e; E) {
        uf.unite(e[0], e[1]);
        int u = uf.find(e[0]);
        if (uf.weights[u] >= e[2]) {
            uf.unused_edges[u] = 0;
        }
    }

    int u = uf.find(0);
    uf.unused_edges[u].writeln;
}



class UnionFind {
    int N;
    int[] table;
    long[] weights;
    long[] unused_edges;

    this(int n, long[] X) {
        N = n;
        table = new int[](N);
        fill(table, -1);
        weights = new long[](N);
        foreach (i; 0..N) weights[i] = X[i];
        unused_edges = new long[](N);
    }

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

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

2019-01-31

AtCoder Grand Contest 016: D - XOR Replace

AtCoder AGC AGC #016 問題記録

https://atcoder.jp/contests/agc016/tasks/agc016_d

問題概要

長さNの数列A, Bが与えられる。Aの要素をひとつ選びその値をAのすべての要素のXORで置き換えるという操作を好きなだけ行えるとき、AをBに一致させることができるか判定せよ。また可能な場合には最小の操作回数も求めよ。

N <= 10⁵

解法

初期状態でのA全体のXORを仮にXと置く。このときXOR演算の性質から、仮にA[2]をXで置き換えたあとのA全体のXORはA[2]になる( x xor y xor z = w <=> w xor y xor z = x )。よって次にA[3]を選んだ場合、A[3]は初期状態のA[2]と置き換えられる。そして今度はA[3]がA全体のXORになる。このように、一度操作を行うとそのとき選んだ要素が次の「A全体のXOR」になるということがわかる。

なのでこの問題で行っている操作は結局単純なswapであるといえる。つまり初期状態でのA全体のXORをAの末尾にくっつけた数列A'を考えたとき、A'において末尾以外の要素と末尾をswapしているのとまったく同じことである。単なるswapなので当然操作の過程で新たな数が登場したりすることもない。よって一致可能性判定はかなり簡単にできて、Bに対しても末尾に全体のXORをくっつけた数列B'を考えたときにA'とB'の構成要素が同じかどうかを見ればよい。

これで一致させられるかどうかの判定はできたので、あとは最小操作回数を求めることになる。先程言い換えたようなswap操作で考えると、効率の良い一致のさせ方は「今の末尾にある数を、それを必要としている場所に送り込む -> 新たに末尾に入ってきた数を、それを必要としている場所に送り込む -> ...」という風に、玉突き的に値がずれていく感じの操作になる。別の言い方をすると、好きな順番でいくつかの要素（末尾は必ず含む）を選択し、選択した順で値をcyclic shiftさせるような操作をすると、最低限の操作回数で複数の値を一気に一致させることができる、ということになる。ただしこのとき注意しなくてはいけないのが「末尾は必ず含む」のところで、末尾の値が必要なかったとしても必ずシフトに巻き込まれることになってしまい、1回分余計に操作をする必要が生じる。以下で具体例を見ていく。

たとえばA'が{1, 2, 3, 0}でB'が{2, 3, 1, 0}だったとき、操作は {1, 2, 3, 0} -> {1, 2, 0, 3} -> {1, 3, 0, 2} -> {2, 3, 0, 1} -> {2, 3, 1, 0} と4回になる。{2, 3, 0, 1}の時点でcyclic shiftが完了しているのだが、末尾の0はもともとずれていた数の集合{1, 2, 3}には含まれていないので、それを元の位置に戻すために操作を+1回行っている。n個の要素のcyclic shiftには(n-1)回の操作が必要で今回はさらに+1回操作をしているため、結局4回の操作になった。

一方で{1, 2, 3}を{2, 3, 1}に一致させることを考えると、これは {1, 2, 3} -> {1, 3, 2} -> {2, 3, 1} と2回で済む。これは末尾の数が必要とされていたためで、このような場合はcyclic shiftを1回やるだけで各要素がぴったりはまるので、操作は(n-1)回で済む。

また別のパターンの例としてA'が{1, 2, 3, 4, 5, 1}でB'が{2, 3, 1, 5, 4, 1}のときを考える。このとき明らかに (1, 2, 3) と (4, 5) は別々にcyclic shiftを行っていくべきで、(1, 2, 3)の方は末尾の1のおかげで最後の合わせ+1回が必要ないが、(4, 5)の方は最後の+1回が必要となる。

上のようなパターンだと見て明らかに(1, 2, 3)と(4, 5)は別だとわかるが、一般的に解くためにはもう少し定式的にやる必要がある。どのようにやるかというと、A[i]!=B[i]となるiがあったとき、A[i]とB[i]をそれぞれグラフの頂点番号とみなして(A[i], B[i])間に辺を張ることにする。これをA', B'のすべてのi(0 <= i <= N)に対して行って出来たグラフにおいて、同じ連結成分内に属するものの集合をひとつのcyclic shiftの単位とみなすことができる（詳しい話は公式解説等参照）。連結成分だけが問題であるので実際にはグラフをつくる必要はなく、UnionFindとかで連結成分を管理すればよい（頂点番号が大きくなりうるので座標圧縮的なテクであらかじめ値を潰しておくとかはする必要がある）。

各連結成分内で必要な操作回数は、上で述べたように末尾の数を必要とするかどうかによって違いがあり、もし末尾と関わりのない連結成分であれば(要素数+1)回かかる。なおここでいう要素数はUnionFindで持ったときの要素数ではなく、その連結成分にA[i]が含まれており、かつA[i]!=B[i]であるようなiの数であることに注意する（グラフをつくる段階で同じ値の要素をひとつの頂点に潰してしまっているのでここは一致しない）。末尾と関わりのあるような連結成分であれば+1が必要なく単に要素数回の操作になる。ただしこのときA'の末尾!=B'の末尾であれば、それは要素数に含めなくてよい。なぜならここが等しくてもそうでなくても必ずcyclic shiftには巻き込まれるからで、さらに連結成分の性質からcyclic shiftの結果どちらにせよB'の末尾に等しい値が移動してくることがわかっているからである。

以上をまとめると、結局A[i]!=B[i]であるような箇所は末尾を除いて答えに+1の寄与があり、さらに末尾と関わりのない連結成分の数だけ余計な操作が+1されるので、この数をかぞえて足せば答えとなる。

感想

今回ばかりは本当に意味のわからない文章を書いてしまった手応えがあるので自分が解くとき参考にしたリンクを張りまくって逃げます

http://kmjp.hatenablog.jp/entry/2017/06/25/0900

https://camypaper.bitbucket.io/2017/06/20/agc016d/

https://www.hamayanhamayan.com/entry/2017/06/19/185428

https://kimiyuki.net/writeup/algo/atcoder/agc-016-d/

https://www.youtube.com/watch?v=kdQtQSgIYPI (解説放送)

コード (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 N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    auto B = readln.split.map!(to!int).array;

    A ~= A.reduce!((a,b) => a^b);
    B ~= B.reduce!((a,b) => a^b);

    if (A.dup.sort() != B.dup.sort()) {
        writeln(-1);
        return;
    }

    auto C = A.dup.sort().uniq.array;
    int M = C.length.to!int;

    int[int] D;
    foreach (i; 0..M) {
        D[C[i]] = i;
    }

    A.each!((ref a) => a = D[a]);
    B.each!((ref a) => a = D[a]);

    auto uf = new UnionFind(M);
    foreach (i; 0..N+1) {
        if (A[i] != B[i]) {
            uf.unite(A[i], B[i]);
            uf.edge[uf.find(A[i])] += 1;
        }
    }


    int ans = 0;

    foreach (i; 0..M) {
        if (uf.find(i) != i) continue;
        if (uf.edge[i] == 0) continue;
        if (uf.find(A.back) == i) {
            ans += uf.edge[i];
            if (A.back != B.back) ans -= 1;
        } else {
            ans += uf.edge[i] + 1;
        }
    }

    ans.writeln;
}



class UnionFind {
    int N;
    int[] table;
    int[] edge;

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

    int find(int x) {
        return table[x] < 0 ? x : (table[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);
        edge[x] += edge[y];
        table[x] += table[y];
        table[y] = x;
    }
}

2019-01-25

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");
}