問題概要

R行C列のグリッドがある。このうちN個のマスに非負整数が書き込まれている。まだ何も書き込まれていない残りすべてのマスに対して、以下のルールを満たしながら数字を書き込むことが可能か判定せよ。ルール1: マスに書き込めるのは非負整数のみ。ルール2: どの2×2のマスを取り出しても、左上＋右下＝右上＋左下が成り立つ。

R, C <= 10⁵

N <= 10⁵

解法

式変形をすると左上－左下＝右上－右下となる。つまりどの2つの行を取ってきても、隣り合う列の要素の差は等しい、ということになる。さらにこれを推移的に適用すると隣り合っているものだけなく、「どんな2つの列a, bに対しても、列aと列bの値の差はすべての行において等しい」（ルール2の言い換え）ということになる。

まずは上で言い換えたルールが既に書き込まれているマスの間で成り立っているかを確かめる。そのために以下のようなグラフを構築する。

頂点がC個（元のマス目の列に対応）
ある行において列a, b (a < b)に数字が書き込まれているとき、a->b に重み(b-a)の辺を、b->aに重み-(b-a)の辺を張る

このとき全部の書き込み同士で辺を張っているとO(N²)になってしまうので、ある行に列同士で辺を張る際は、書き込まれている中での隣接列同士だけに辺を張るようにする（列1, 3, 4に書き込みがあれば1-3, 3-4だけに張って、1-4は張らない）。こうして作ったグラフにおいて、上で言い換えたルールに違反するような矛盾が生じないかをDFSで確認することができる。具体的には以下のような手順で行う。

適当にDFSの始点を選ぶ。スタート時には数0を持っている。
ある頂点を初めて訪れたとき、持っている数をその頂点に割り当ててDFSを続行する
既に訪れている頂点に再び訪れたとき、今持っている数とその頂点に割り当てられている数が同じかどうかチェックする。もし同じであればtrueを返す。もし違っていれば矛盾が生じたことになるのでfalseを返す
この過程においてどこかで1回でもfalseが返ってきたらそもそも書き込まれている数字の時点でルール違反のため、問題の答えはNoとなる

以上の手順によってルール2の違反がないかを確かめることができる。実際には作ったグラフは必ずしも連結ではないので、各連結成分に対しそれぞれ独立に上のDFSを行う必要がある。もしここでルール違反がなかった場合、今度はルール1の違反がないかを確認する。つまり上で求めた差分関係のルールに従ってマスを埋めていったとき、どこかで非負整数が現れないかをチェックする。これは既に書き込まれているN個のマスをそれぞれ起点として、ルールに従って埋めたとき現れる最小値が0以上であることを確かめればよい。実装では先ほどのDFSで求めた相対的な値の割り当て表を再利用して、連結成分の中の最小値ひとつをチェックするだけでよい（たとえば今見ている既に書き込まれたマスの列に割り当てられた相対値が3, 同じ連結成分の中で最小の相対値が-5のとき、実際の最小値は（マスの数字-8）になる。連結成分のまとめにはUnionFind等を使う。

感想

最初等差数列だろとか思って全然通らなかった、あとあんまりエレガント感ないけどこれでいいんかいなと思いつつ地道に考察進めて書いたのが通ってよかった

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


void main() {
    auto s = readln.split.map!(to!int);
    auto R = s[0];
    auto C = s[1];
    auto N = readln.chomp.to!int;
    auto A = new Tuple!(int, long)[][](R);

    foreach (i; 0..N) {
        s = readln.split.map!(to!int);
        auto r = s[0] - 1;
        auto c = s[1] - 1;
        auto a = s[2].to!long;
        A[r] ~= tuple(c, a);
    }
    foreach (i; 0..R) A[i].sort!"a[0] < b[0]";

    auto G = new Tuple!(int, long)[][](C);

    foreach (i; 0..R) {
        foreach (j; 0..A[i].length.to!int-1) {
            G[A[i][j][0]] ~= tuple(A[i][j+1][0], A[i][j+1][1] - A[i][j][1]);
            G[A[i][j+1][0]] ~= tuple(A[i][j][0], A[i][j][1] - A[i][j+1][1]);
        }
    }

    auto used = new bool[](C);
    auto vals = new long[](C);

    bool dfs(int n, long x) {
        if (used[n]) return vals[n] == x;
        used[n] = true;
        vals[n] = x;
        foreach (m; G[n]) if (!dfs(m[0], x+m[1])) return false;
        return true;
    }

    foreach (i; 0..C) if (!used[i] && !dfs(i, 0)) {writeln("No"); return;}

    used.fill(false);
    auto mins = new long[](C);
    int[] g;

    long dfs2(int n, long x) {
        if (used[n]) return x;
        x = min(x, vals[n]);
        used[n] = true;
        g ~= n;
        foreach (m; G[n]) x = min(x, dfs2(m[0], x));
        return x;
    }

    foreach (i; 0..C) {
        if (used[i]) continue;
        g = [];
        auto m = dfs2(i, 1L<<59);
        foreach (j; g) mins[j] = m;
    }

    foreach (i; 0..R) {
        foreach (a; A[i]) {
            auto m = mins[a[0]];
            auto x = a[1] - (vals[a[0]] - mins[a[0]]);
            if (x < 0) {
                writeln("No");
                return;
            }
        }
    }

    writeln("Yes");
}

nebukuro09の日記

CODE FESTIVAL 2016 qual A: D - マス目と整数 / Grid and Integers

問題概要

解法

感想

コード (D言語)