2020-01-26

CODE FESTIVAL 2016 qual A D - マス目と整数 / Grid and Integers (橙色, 800 点)

AtCoder AtCoder800点 sparseな問題パズル Greedy:端から順に決まっていく Greedy グラフ二部グラフ可視化テク:二次元情報を二部グラフにして考える制約条件:長方形の4頂点についての条件連結成分条件の言い換え二次元グリッド二次元平面上のN点の問題橙色diff AGC-like 連結成分ごとに分解して考える

800 点埋めをしていく！！！
問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった

問題へのリンク

問題概要

$R$ 行 $C$ 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を $a$ とする):

どのマスの数値も非負な整数である
任意の $(i, j)$ に対して、 $a_{i, j} + a_{i+1, j+1} = a_{i+1, j} + a_{i, j+1}$ が成立する

マス目のうちの $N$ マスにはすでに整数値が書かれている。これらに矛盾しないようにマス目全体に数値を入れることが可能かどうかを判定せよ。

制約

$1 \le R, C, N \le 10^{5}$

考えたこと：条件の言い換え

パズルみたいな感じ。初見では、すごくコーナーケースが多くて間違いやすい問題に見えてしまった。でも落ち着いて整理すれば明快だった。とりあえず条件を言い換える

行 i と行 j を選んだとき、どの列についてもその差が等しい
列 i と列 j を選んだとき、どの行についてもその差が等しい

というのと同値であることがわかる。たとえば

3 4 6
5 6 8

は条件を満たしていて、1 行目と 2 行目の値の差はすべて 2 になっている。1 列目と 2 列目の差は 1 で、2 列目と 3 列目の差は 2 になっている。こういう風にとらえた方が、扱いやすそうである。

連結成分ごとに分ける

次に思ったことは、「埋まるところを埋める」というのを繰り返していくと、以下の問題と同じような感じで、ブロック長方形がたくさん生えるような感じになる。

drken1215.hatenablog.com

つまり、「長方形の 3 点に数値が埋まっている」という状態であったならば、残りの 1 点の数値が自動的に決まるので、それを繰り返していくと、「互いに行や列を共有しない長方形ブロックの塊」に分けられることになる。

そして、一度長方形ブロックにする部分で非負な部分が登場しなかったら、全体をきちんと埋められることもわかった。たとえば

3 4 - - -
5 6 - - -
- - 1 2 7
- - 2 3 8

という状況では、1 箇所「-」を埋めると残り全部が自動的に決まっていくことになる。今回はとりあえず右上を埋めることにする。このとき、

左上ブロックのうち、相対的な値が最小の行
右下ブロックのうち、相対的な値が最小の列

とが交わるところを 0 にすればよい。具体的には「3 4 の行」と「1 2 の列」が交わるところを 0 にする。そうすると

という風になる。これを繰り返していけば、全部のマスが非負になるように埋めることができる。

連結成分

以上から、各連結成分ごとの問題に帰着された。具体的には、二次元グリッドを

左ノードは行
右ノードは列
数値があるところが (i, j) マスのとき、行 i と列 j を辺で結ぶ

という風に対応させた二部グラフにおいて、各連結成分について考えれば良い。この連結成分では、マス目の値が一意に決まってしまう。その値が非負かどうかを check すればよい。

それをやるためには、

行のうち、相対値が最小の行
列のうち、相対値が最小の列

の値を見れば良い。相対値を求めるには、

二部グラフのうちのどこか一つのノードの値を 0 として
そこから辺をたどって「辺の両端の値が辺の数値」となるように値を次々と決めていく

という風にすれば OK。この値はあくまで相対値を求めるために、一つのノードを仮に 0 と置いているだけなので、非負にならなくても OK。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using Edge = pair<int, long long>;
using Graph = vector<vector<Edge>>;
const long long INF = 1LL<<60;

int R, C, N, M;
Graph G;

vector<int> tmp;
vector<long long> vals;

bool rec(int v, long long val) {
    vals[v] = val;
    for (auto e : G[v]) {
        if (vals[e.first] != -1) {
            if (val + vals[e.first] != e.second) return false;
            continue;
        }
        if (!rec(e.first, e.second - val)) return false;
    }
    tmp.push_back(v);
    return true;
}   

int main () {
    cin >> R >> C >> M;
    int N = R+C;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < M; ++i) {
        int r, c;
        long long a;
        cin >> r >> c >> a;
        --r, --c;
        c += R;
        G[r].push_back({c, a});
        G[c].push_back({r, a});
    }

    bool res = true;
    vals.assign(N, -1);
    for (int v = 0; v < N; ++v) {
        if (vals[v] != -1) continue;
        tmp.clear();
        if (!rec(v, 0)) res = false;
        long long lmi = INF, rmi = INF;
        for (auto t : tmp) {
            if (t < R) lmi = min(lmi, vals[t]);
            else rmi = min(rmi, vals[t]);
        }
        if (lmi + rmi < 0) res = false;
    }
    if (res) cout << "Yes" << endl;
    else cout << "No" << endl;
}