けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 115 B - Plus Matrix (茶色, 400 点)

「決めてから、整合性を確認する」というタイプの問題の典型例ですね!

問題概要

 N \times N の非負整数を成分とする行列  C が与えられる。

すべての  (i,j) について  C_{i,j} = A_{i} + B_{j} を満たすような非負整数列  A_{1}, \dots, A_{N} B_{1}, \dots, B_{N} の組が存在するか判定し、存在するなら一つ出力せよ。

制約

  •  1 \le N \le 500

考えたこと

条件を満たすような行列  C であれば、

1 7 5
3 9 7

というようになっている。つまり、

  • 2 行目 1 列目の 3 は、1 行目 1 列目の 1 に +2 したもの
  • 2 行目 2 列目の 9 は、1 行目 2 列目の 7 に +2 したもの
  • 2 行目 3 列目の 7 は、1 行目 3 列目の 5 に +2 したもの

というように、2 行目の値は一律に 1 行目に同じ値を足し引きしたものとなっている。つまり、

 A_{2} = A_{1} + 2

という風にするのが適切だということだ。

同じ理屈で、次のようなことが言える。

  •  A_{1}, \dots, A_{N} の各隣接項の差分については、1 列目のみを見れば一意に決まる
  •  B_{1}, \dots, B_{N} の各隣接項の差分については、1 行目のみを見れば一意に決まる

ということがわかる。たとえばサンプル 1 の

4 3 5
2 1 3
3 2 4

というケースであれば、

  •  A_{2} = A_{1} - 2 (4 と 2 を比較)
  •  A_{3} = A_{2} + 1 (2 と 3 を比較)
  •  B_{2} = B_{1} - 1 (4 と 3 を比較)
  •  B_{3} = B_{2} + 2 (3 と 5 を比較)

という関係が成立することが必要だと考えることができるのだ。ただしこの時点では、 A B相対的な値の関係がわかるのみであって、値が完全に決まるわけではないことに注意しよう。

とりあえず、相対的な値の関係がわかるので、最小値をとるところを 0 に設定してあげることにしよう。たとえば上のケースであれば、1 列目が (4, 2, 3) なので

 A = (2, 0, 1)

としてあげるのが良さそうだ。同様に

 B = (1, 0, 2)

としてあげれば OK。これだと行列  C に対して「ちょうど 1 だけ足りない」という感じなので、A か B のどちらかに一律に 1 を足せば OK。B に 1 ずつ足すと

  •  A = (2, 0, 1)
  •  B = (2, 1, 3)

となる。

ダメな場合

逆に、

  •  A = (2, 0, 1)
  •  B = (1, 0, 2)

というように、一行目と一列目のみを見て決定した  A, B に対して、

 C_{i, j} A_{i} + B_{j} との差

が一定でない場合は "No" ということになる。

もう一つ、その差が負の値になる可能性 (=  A B に負の整数が混ざってしまう可能性) があるのではないかと気になってしまうかもしれない。しかしそれはあり得ない。なぜなら、上記のような  A, B の作り方をした場合、 A_{i} + B_{j} の最小値は 0 になるのだ。 C_{i, j} の値はすべて 0 以上であることが保証されているので、 C_{i, j} - (A_{i} + B_{j}) が負になることはあり得ない。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N; cin >> N;
    vector<vector<long long>> C(N, vector<long long>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> C[i][j];
    vector<long long> X(N), Y(N);
        
    auto solve = [&]() -> bool {        
        long long mix = C[0][0], miy = C[0][0];
        for (int i = 0; i < N; ++i) chmin(mix, C[i][0]), chmin(miy, C[0][i]);
        for (int i = 0; i < N; ++i) X[i] = C[i][0] - mix, Y[i] = C[0][i] - miy;

        // 差分を一律に足す
        long long dif = C[0][0] - X[0] - Y[0];
        for (int i = 0; i < N; ++i) X[i] += dif;

        // 整合性を確認する
        for (int i = 0; i < N; ++i) 
            for (int j = 0; j < N; ++j) 
                if (X[i] + Y[j] != C[i][j])
                    return false;
        return true;
    };
    
    if (solve()) {
        cout << "Yes" << endl;
        for (int i = 0; i < N; ++i) cout << X[i] << " "; cout << endl;
        for (int i = 0; i < N; ++i) cout << Y[i] << " "; cout << endl;
    }
    else cout << "No" << endl;
}