2018-07-27

AtCoder Regular Contest 097: F - Monochrome Cat

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

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

2018-07-24

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

2018-07-12

SoundHound Inc. Programming Contest 2018 -Masters Tournament-: E - + Graph

問題記録 AtCoder SoundHound2018Masters予選

https://beta.atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e

問題概要

N頂点M辺の単純連結無向グラフが与えられる。辺iには整数siが設定されている。すべての頂点にある整数を割り当てるとき、すべての辺において「辺の両端の2頂点に割り当てられた整数を足すとsiに等しい」という条件が満たされるような割り当て方は何通りあるか。

N, M <= 10⁵

解法

あるひとつの頂点に割り当てる値を仮にxとおくと、他の頂点に割り当てるべき値は必ず x+b あるいは -x+b という形になる。というわけでまずはDFSなりBFSなりで各頂点のこの一次式の形を求める。場合によっては途中で矛盾が生じるかもしれないが（その場合答えは0通り）、ここでやり始めるとごちゃごちゃするので自分の実装ではとりあえず最初に出たパターンを割り当てて矛盾チェックは後回しにしている。

一次式の割り当てが終わったら、矛盾チェックをする。具体的には全部の辺(u, v)を見て(uに割り当てた一次式)+(vに割り当てた一次式)がsと等しくなるかを確かめる。このとき(uの一次式)と(vの一次式)のxの符号が異なれば合計は定数になり、その定数!=sであれば矛盾なので答えは0通りになる。符号が同じならば2x=hogeみたいな式になって、xが正整数にならなければ同じく0通りになる。正整数になった場合にはxがひとつに定まることになるので、後で違うxの値がでてきたらやはり矛盾で0通りになる。

仮に矛盾がなければあとはxのとりうる範囲を求めて答えとする。ある頂点の一次式が x-b の形であるならば xはbより大きくなければならず、 -x+b ならば xはb未満でなければならないので、これらからxのとりうる上限と下限が出せる。

感想

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;

long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto G = new Tuple!(int, long)[][](N);
    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);
    }

    auto V = new Tuple!(long, long)[](N);
    fill(V, tuple(INF, INF));

    void dfs(int n, long a, long b) {
        if (V[n][0] != INF) return;
        V[n] = tuple(a, b);
        foreach (to; G[n]) {
            auto m = to[0];
            auto S = to[1];
            if (V[m][0] != INF) continue;
            dfs(m, -1*a, S-b);
        }
    }

    dfs(0, 1, 0);

    auto ans = INF;
    auto X = INF;

    foreach (i; 0..N) {
        long a1 = V[i][0];
        long b1 = V[i][1];
        foreach (e; G[i]) {
            int j = e[0];
            long S = e[1];
            long a2 = V[j][0];
            long b2 = V[j][1];
            if (a1 != a2) {
                if (b1 + b2 != S) {
                    writeln(0);
                    return;
                }
            } else if (a1 == 1) {
                long c = S - b1 - b2;
                if (c % 2 || c < 0) {
                    writeln(0);
                    return;
                }
                auto x = c / 2;
                if (X == INF || X == x) {
                    X = x, ans = 1;
                } else {
                    writeln(0);
                    return;
                }
            } else {
                long c = S - b1 - b2;
                if (c % 2 || c > 0) {
                    writeln(0);
                    return;
                }
                auto x = -c / 2;
                if (X == INF || X == x) {
                    X = x, ans = 1;
                } else {
                    writeln(0);
                    return;
                }
            }
        }
    }

    long lo = 1;
    long hi = INF;

    foreach (i; 0..N) {
        long b = V[i][1];
        if (V[i][0] == 1 && b < 0) {
            lo = max(lo, -b + 1);
        } else if (V[i][0] == -1 && b > 0) {
            hi = min(hi, b - 1);
        }
    }

    ans = min(ans, hi - lo + 1);
    ans = max(0, ans);
    ans.writeln;
}

2018-07-12

AtCoder Grand Contest 012: D - Colorful Balls

問題記録 AtCoder AGC AGC #012

https://beta.atcoder.jp/contests/agc012/tasks/agc012_d

問題概要

N個のボールが一列に並んでおり、各ボールには色と重さが設定されている。色が同じで合計の重さがX以下のボール2つの位置を入れ替える操作と、色が異なって合計の重さがY以下のボール2つの位置を入れ替える操作という2つの操作を好きな順序で何回でも行うことができる。最終的なボールの色の並びとしてありうるものは何通りか。

N <= 2*10⁵

解法

まず重要な点として入れ替え操作には推移的な関係がある。つまりボールAとボールBが入れ替え可能かつボールBとボールCが入れ替え可能であるならば、ボールAとボールCは（直接的には不可能でも）実質的に入れ替え可能とみなすことができる。（たとえばABCのような並びの場合、ABC->BAC->CAB->CBA のように交換していくことができ、最初と最後だけ見ればAとCを直接交換しているのと変わりがない）

このことを念頭におくと入替可能なボール同士はひとつのグループにまとめていくことができる(union-findのuniteのようなイメージ）。このようなグループ分けをすると「ひとつのグループ内でのボール移動は完全に自由」「異なるグループ間でのボール移動はありえない」ということがいえるので、あとは単なる組合せの問題になる（色a, b, cのボールがそれぞれx, y, z個ある。並び替え方は何通りか？）。

以上よりあとはグループ分けの仕方だけが問題となるが、これを効率的にやるためには各色の一番軽いボールに注目するとよい。入替の条件は重さの和なので、たとえば「色aの中で一番軽いボール」との入替が不可能ならば、当然それより重い同色のボールとの入替も不可能である。またこのように考えると、実は「異なる複数の色のボールを含みうるグループは高々1つである」ということも言える。全体の中で最も軽いボール(Aとする）の色がaだったとしたとき、a以外のボールが異なる色と繋がれるならば必ずAと繋がれることになるし、Aと同じ色のAより重いボールが異なる色と繋がれるならAも必ずそれと繋がれるからである。

というわけで答えは

同色の中で最も軽いボールとの和がX以下ならグループに入れる
異色の中で最も軽いボールとの和がY以下ならグループに入れる

という計算を行い、できたグループの中での色の並び替えを数えればよいということになる。

感想

最初不可能にしか見えなかったけどがんばったらできた

コード (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 = 10L^^9 + 7;

void main() {
    auto s = readln.split.map!(to!long);
    auto N = s[0].to!int;
    auto X = s[1];
    auto Y = s[2];
    auto A = new long[][](N);
    foreach (i; 0..N) {
        s = readln.split.map!(to!long);
        A[s[0].to!int-1] ~= s[1];
    }

    A = A.filter!(a => !a.empty).array;
    int M = A.length.to!int;
    
    foreach (i; 0..M) {
        A[i].sort!"a < b";
    }
    A.sort!"a[0] < b[0]";

    
    int[] B;
    
    foreach (i; 0..M) {
        if (i >= 1 && A[i][0] + A[0][0] > Y) {
            break;
        }
        
        int cnt = 1;
        long second = A.length > 1 ? A[1][0] : 1L<<59;
        
        foreach (j; 1..A[i].length) {
            if (i == 0) {
                if (A[i][0] + A[i][j] <= X || second + A[i][j] <= Y) {
                    ++cnt;
                }
            } else {
                if (A[i][0] + A[i][j] <= X || A[0][0] + A[i][j] <= Y) {
                    ++cnt;
                }
            }
        }
        B ~= cnt;
    }


    auto F = new long[](N+1);
    F[0] = 1;
    foreach (i; 0..N) {
        F[i+1] = F[i] * (i + 1) % MOD;
    }

    long ans = F[B.sum];
    foreach (b; B) {
        ans = ans * powmod(F[b], MOD-2, MOD) % MOD;
    }
    
    ans.writeln;;
}

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

2018-06-14

yukicoder No.95 Alice and Graph

yukicoder 問題記録

https://yukicoder.me/problems/no/95

問題概要

N頂点M辺の無向グラフが与えられる。グラフの頂点には0～(N-1)の番号が付いている。はじめプレイヤーは頂点0にいて、一度の移動で一辺で繋がれた2頂点間を移動できる。また頂点nをはじめて訪れたとき(2ⁿ - 1)点の得点がもらえる。K回まで移動できるとき、得られる最大の得点を求めよ。

N <= 60

M <= N(N-1)/2

K <= 15

解法

実はこれは結構おなじみのパターンで、スコアがなんかのべき乗になっているような場合は貪欲に解を構成していけることが多い。ここでは 2ⁿ > 2^n-1+2^n-2+...+2⁰ という関係が使える。つまり2ⁿが取れる場合それ以下の全部を取っても2ⁿの得点に満たないので、一番でかいやつから順番にひとつずつそれが取れるかを検討していけば最適な解が構成できる。上の不等式は2進表記で考えると直感的に理解できると思う(1000 > 0100 + 0010 + 0001)。

具体的な解法は、まず訪れる頂点集合S（初めはスタート地点の頂点0だけが入っている）を用意し、ここに新たな頂点nを加えても大丈夫かどうかを頂点番号の大きい順に見ていけばよい。もし頂点nを加えても大丈夫ならそのまま残しておけばいいし、だめなら取り除いて続行する。

ある頂点集合が条件を満たすかどうかは、K手の移動で含まれる頂点全部を回りきれるかで判定すればよい。これは巡回セールスマン問題っぽくなるが、ここでKの小ささが効いてくる。K<=15ということはスタート地点含め最大でも16頂点しか回れないということなので、以下のbitDPがO(K² 2^K)で回せる。

dp(mask, i): 頂点集合maskを訪れていて、最後に訪れた頂点がiであるときの最小移動距離

感想

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;

immutable int INF = 1 << 29;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    auto G = new int[][](N);
    auto D = new int[][](N, N);

    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= s[1]-1;
        G[s[1]-1] ~= s[0]-1;
    }

    foreach (i; 0..N)
        foreach (j; 0..N)
            D[i][j] = i == j ? 0 : INF;

    foreach (i; 0..N)
        foreach (j; G[i])
            D[i][j] = 1;

    foreach (i; 0..N)
        foreach (j; 0..N)
            foreach (k; 0..N)
                D[j][k] = min(D[j][k], D[j][i] + D[i][k]);

    
    bool can_travel(const int[] nodes) {
        int n = nodes.length.to!int;
        auto dp = new int[][](1<<n, n);
        foreach (i; 0..(1<<n)) fill(dp[i], INF);
        dp[1][0] = 0;

        foreach (mask; 1..(1<<n)) 
            foreach (i; 0..n) 
                if ((1 << i) & mask) 
                    foreach (j; 0..n) 
                        if (!((1 << j) & mask)) 
                            dp[mask|(1<<j)][j] = min(dp[mask|(1<<j)][j],
                                                     dp[mask][i] + D[nodes[i]][nodes[j]]);

        return dp[(1<<n)-1].reduce!min <= K;
    }

    int[] S = [0];
    
    foreach_reverse (i; 1..N) {
        S ~= i;
        if (!can_travel(S))
            S.popBack;
        if (S.length == K+1)
            break;
    }

    ulong ans = 0;
    foreach (n; S)
        ans += (1UL << n) - 1;
    ans.writeln;
}

2018-06-08

AtCoder Regular Contest 093: E - Bichrome Spanning Tree

問題記録 AtCoder ARC ARC #093 最小全域木

https://beta.atcoder.jp/contests/arc093/tasks/arc093_c

問題概要

N頂点M辺のグラフが与えられる。各辺にはコストがある。すべての辺をそれぞれ白か黒かで塗り分けるとき、以下の条件が満たされるような塗り方は何通りあるか。条件：「白の辺も黒の辺も少なくともひとつ含むような全域木が存在し、かつその中で最小コストを持つ全域木のコストはXに等しい」

N <= 1000

M <= 2000

解法

とりあえず元のグラフの最小全域木を適当にひとつ構成し、そのコストをYとおく。

まず簡単なケースとして、Y > X ならば条件を満たす全域木は存在しない（最小全域木よりコストの小さい全域木はないので）。

次に Y = X の場合。この場合、元のグラフの最小全域木としてありえるもののうち、少なくともひとつが黒と白の辺を両方含むのであればその塗り方はOKということになる。そしてそのような塗り方は「元のグラフの最小全域木に含まれうる辺（以下 safe edge と呼ぶ）の集合のうち、少なくともひとつの辺は集合内の他の辺と異なる色で塗る」という塗り方と同じである。仮にsafe edgeのうちひとつが黒、別のひとつが白だった場合、それら2つを両方含む最小全域木が必ず構成できる。逆にすべてのsafe edgeの色が同じだった場合、本来最小全域木に含まれない辺（＝使うと無駄なコストが発生する辺）を少なくともひとつ使って全域木を作らざるをえず、Y = Xという前提が崩れる。よってsafe edgeの数をかぞえてそれらがすべて同じ色にならない場合の数を数えればこのケースは過不足なく数えられる。

safe edgeの数え方だが、例えば以下のような方法がある。最初にひとつ適当につくった最小全域木におけるすべての頂点対(u, v)間で「(u, v)間のパス上に含まれる辺のうち最大のコストを持つもののコスト」(max_edge(u, v))を計算しておく。ここで元のグラフの辺(a, b)をひとつとったとき、辺のコストがmax_edge(a, b)と同じであればその辺はsafe edgeで、大きければsafe edgeではない。なぜなら辺(a, b)をつないだあとでmax_edge(a, b)にあたる辺を木から削除すれば、木の連結を保ったままコストは（追加した辺 - 削除した辺）の分増えることになるからである（差が0ならコストが増えない＝最小全域木のまま）。この要領で全部の辺をチェックすればsafe edgeの数をかぞえることができる。

最後に Y < X の場合。この場合、元の最小全域木からコストが(X-Y)増えた全域木を作ることが目的になる。このための条件は結構厳しくて、まず元の最小全域木は明らかに作れてはいけないので、safe edgeは全部同じ色にする必要がある。そのうえで余分な辺が使われるように塗るわけだが、余分な辺をひとつ追加することによって全域木のコストがどれくらい増えるかというと辺(a, b)のコスト - max_edge(a, b) である。これは「絶対使わなければいけない余分な辺(a, b)」を全域木にひとつ追加したとき、木の形を保つために元の木のパス(a, b)上の辺をひとつ落とすことになるが、落とすべき辺は明らかに最もコストの大きい辺なので、そういうことになる。しかも元の最小全域木に対して追加できる余分な辺は高々ひとつである。余分な辺を追加するためには少なくともsafe edgeは全部同色で塗った上で追加したい辺を別の色で塗る必要があるが、仮にひとつでも違う色を全域木に組み込めればあとは何の辺を使おうが自由なので、safe edgeだけを使っていくのが最適になるからである。そして追加される余分な辺も、safe edgeと違う色を持っているもののうちで edge_cost(a, b) - max_edge(a, b) がもっとも小さいものが自動的に選ばれることになる。以上より目的を達成するためには (1) safe edgeは全部同じ色で塗る (2) edge_cost(a, b) - max_edge(a, b) が X-Yより小さい辺もsafe edgeと同じ色で塗る (3) edge_cost(a, b) - max_edge(a, b) が X-Y と等しい辺のうち、少なくともひとつは safe edgeと別の色 (4) 残りの辺は自由という4つの条件を満たすように塗ればよい、ということになる。

感想

なんかこれまで書いたブログの中で最も意味不明の怪文書になってしまった気がする

感想として問題解いてるときは最小全域木が何通り作れるか？みたいなところに思考が行ってしまったんだけどそんなことを考える必要はなく、色を塗ると自動的に全域木が決まるのでそれを数える、というのが考えるべきことだったんだなあという感じです

コード (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;
immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto X = readln.chomp.to!long;
    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);
    }
    auto T = new Tuple!(int, long)[][](N);

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

    foreach (e; E) {
        if (uf.find(e[0]) == uf.find(e[1]))
            continue;
        T[e[0]] ~= tuple(e[1], e[2]);
        T[e[1]] ~= tuple(e[0], e[2]);
        uf.unite(e[0], e[1]);
        mst_cost += e[2];
    }

    auto max_edge_cost = new long[][](N, N);

    void dfs(int n, int p, int root, long d) {
        max_edge_cost[root][n] = d;
        foreach (e; T[n]) {
            int m = e[0];
            long c = e[1];
            if (m != p) 
                dfs(m, n, root, max(d, c));
        }
    }

    bool is_safe_edge(Tuple!(int, int, long) e) {
        return max_edge_cost[e[0]][e[1]] >= e[2];
    }

    foreach (i; 0..N)
        dfs(i, -1, i, 0);
    long ans = 0;

    if (mst_cost == X) {
        long safe_edges_cnt = E.map!(e => is_safe_edge(e)).sum;
        ans = (powmod(2, safe_edges_cnt, MOD) - 2) * powmod(2, M - safe_edges_cnt, MOD) % MOD; 
        ans = (ans + MOD) % MOD;
    } else if (mst_cost < X) {
        long diff = X - mst_cost;
        long a = E.map!(e => e[2] - max_edge_cost[e[0]][e[1]] < diff).sum;
        long b = E.map!(e => e[2] - max_edge_cost[e[0]][e[1]] == diff).sum;
        long c = E.map!(e => e[2] - max_edge_cost[e[0]][e[1]] > diff).sum;
        ans = 2 * (powmod(2, b, MOD) - 1) % MOD * powmod(2, c, MOD) % MOD;
        ans = (ans + MOD) % MOD;
    }

    ans.writeln;
}


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 : (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);
        table[x] += table[y];
        table[y] = x;
    }
}


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

2018-05-25

AtCoder Regular Contest 067: F - Yakiniku Restaurants

AtCoder 問題記録 ARC ARC #067

問題概要

N軒の焼肉屋が横一直線に並んでおり、それぞれの間の距離は数列Aで表される。またM枚のチケットを1枚ずつ持っており、チケットjを焼肉屋iがある地点で使うことでB(i, j)の幸福度を得ることができる。好きな地点からスタートして自由に移動してチケットを使うとき、(得られる幸福度 - 移動距離の和) の最大値を求めよ。

N <= 5×10³

M <= 200

解法

訪れる区間を固定して考える。訪れる中で最も左にある焼肉屋をl, 最も右にある焼肉屋をrとすると、求めるスコアは（各チケットごとの区間[l, r]での最大値）の和－（lからrまでの距離）となる（単純に端から端へ移動しながら区間内の一番高いところでチケットを使えばいいので）。

愚直に上の値を求めようとすると「各チケットごとの区間[l, r]での最大値」の部分がネックになる。区間の個数はO(N²)でありチケットの種類はM個あるため一個一個求めていく方法ではどう頑張ってもO(MN²)はかかってしまうためである。なのでここを何とかして高速にやる必要がある。以下ではこの値を max[l][r] = 区間[l, r]におけるそのチケットの最大値とおく。

ここであるチケットがとりうる最大値を考えてみる。もしあるチケットが焼肉屋xで最大値vを取るのであれば、xを含むどの区間[l, r]においてもmax[l][r]は全部vになるはずである。この手続で「xを含む区間」の最大値は全部わかるので、次はxを含まない区間[1, x)と(x, N]で同じ手続きを行う。……というように区間を分割しながら再帰的に同様の手続きを続けていくと、最終的に全部の区間の最大値を埋めることができる。そしてこの一連の手続きは必ずN回で終了する。なぜなら一回の手続で区間内から必ずひとつインデックスが消えるからである。

このように上の手続自体はN回で済むので、1回の手続にかかる計算量を抑えることができればmax[l][r]のテーブルを埋めることができる。まず必要な処理は「指定された区間の中で最大の値をもつインデックスを取得する」で、これはおなじみのRMQを用いれば1回につきO(logN)で済む。難しいのがもうひとつの処理「区間[l, r]で最大値vをとるインデックスxについて、[l, r]内でxを含むすべての区間に値vを割り当てる」だが、これはmax[l][r]のテーブルを2次元的に考えることでうまくやることができる。実はこの2次元テーブルにおいては、「区間[i, j]においてインデックスxを含むようなすべての区間」は長方形の形をとる。

f:id:fluffyowl:20180525192744p:plain

上図は区間[0, 6]で最大値をとるインデックスが仮に4だった場合を示している。ここで「インデックス4を含むすべての区間」は図で青く塗ってある部分に等しい。つまりこの部分の長方形に一様にインデックス4での値を足すことができればよく、それを効率的に行えるアルゴリズムが存在する。いもす法である。これに関しては御本人の解説がそれそのものなので参照されたい。とにかくこれを使うと最後にテーブルの累積和をとる部分でO(N²)かかるが途中の一回一回の長方形への足し算はO(1)で可能になる。よってこれでひとつのチケットにおけるすべての区間での最大値をO(N²)で求めO(1)で参照できるようになった。さらに各チケットのスコアはただ足し算すればいいだけなので、ひとつの2次元テーブルで同じ加算をいっしょくたにやってしまっていい。これで全部のチケットを合わせた結果も同様の計算量で求まることになる。

求めたい値は（各チケットごとの区間[l, r]での最大値）の和－（lからrまでの距離）であった。これの前者は今まで述べてきたとおりO(1)で参照することができるようになり、後者は単純な累積和でこれも参照O(1)なので、区間をO(N²)で全探索しても十分間に合うことになる。

感想

どの解説漁っても突然いもす法が出てくるので？？？？（？？？？？？？？？？）になってたがpekempeyさんの記事の表とにらめっこしてやっと理解できた。なんかすごい汎用性ありそうなテクだ

コード (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 s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto A = readln.split.map!(to!long).array;
    auto B = N.iota.map!(_ => readln.split.map!(to!long).array).array;
    auto C = new long[](N);
    foreach (i; 0..N-1) C[i+1] = C[i] + A[i];

    auto table = new long[][](N+1, N+1);
    auto st = new SegmentTree!(Tuple!(long, int), (a, b) => max(a, b), tuple(-(1L<<59), -1))(N);
    auto stack = new Tuple!(int, int)[](N+10);

    foreach (m; 0..M) {
        foreach (i; 0..N) st.assign(i, tuple(B[i][m], i));
        stack[0] = tuple(0, N-1);
        int sp = 0;
        while (sp >= 0) {
            auto l = stack[sp][0];
            auto r = stack[sp][1];
            sp -= 1;
            auto t = st.query(l, r);
            auto v = t[0];
            auto p = t[1];
            table[l][p] += v;
            table[l][r+1] -= v;
            table[p+1][p] -= v;
            table[p+1][r+1] += v;
            if (l <= p-1) stack[++sp] = tuple(l, p-1);
            if (r >= p+1) stack[++sp] = tuple(p+1, r);
        }
    }

    long ans = 0;
    foreach (i; 0..N) foreach (j; 0..N) table[i][j+1] += table[i][j];
    foreach (j; 0..N) foreach (i; 0..N) table[i+1][j] += table[i][j];
    foreach (i; 0..N) foreach (j; i..N) ans = max(ans, table[i][j] - C[j] + C[i]);
    ans.writeln;
}


class SegmentTree(T, alias op, T e) {
    T[] table;
    int size;
    int offset;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new T[](size);
        fill(table, e);
        offset = size / 2;
    }

    void assign(int pos, T val) {
        pos += offset;
        table[pos] = val;
        while (pos > 1) {
            pos /= 2;
            table[pos] = op(table[pos*2], table[pos*2+1]);
        }
    }

    T query(int l, int r) {
        return query(l, r, 1, 0, offset-1);
    }

    T query(int l, int r, int i, int a, int b) {
        if (b < l || r < a) {
            return e;
        } else if (l <= a && b <= r) {
            return table[i];
        } else {
            return op(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b));
        }
    }
}