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 <= 105

解法

あるひとつの頂点に割り当てる値を仮に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;
}