「決めてから、整合性を確認する」というタイプの問題の典型例ですね!
問題概要
の非負整数を成分とする行列 が与えられる。
すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。
制約
考えたこと
条件を満たすような行列 であれば、
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 行目に同じ値を足し引きしたものとなっている。つまり、
という風にするのが適切だということだ。
同じ理屈で、次のようなことが言える。
- の各隣接項の差分については、1 列目のみを見れば一意に決まる
- の各隣接項の差分については、1 行目のみを見れば一意に決まる
ということがわかる。たとえばサンプル 1 の
4 3 5 2 1 3 3 2 4
というケースであれば、
- (4 と 2 を比較)
- (2 と 3 を比較)
- (4 と 3 を比較)
- (3 と 5 を比較)
という関係が成立することが必要だと考えることができるのだ。ただしこの時点では、 や の相対的な値の関係がわかるのみであって、値が完全に決まるわけではないことに注意しよう。
とりあえず、相対的な値の関係がわかるので、最小値をとるところを 0 に設定してあげることにしよう。たとえば上のケースであれば、1 列目が (4, 2, 3) なので
としてあげるのが良さそうだ。同様に
としてあげれば OK。これだと行列 に対して「ちょうど 1 だけ足りない」という感じなので、A か B のどちらかに一律に 1 を足せば OK。B に 1 ずつ足すと
となる。
ダメな場合
逆に、
というように、一行目と一列目のみを見て決定した に対して、
と との差
が一定でない場合は "No" ということになる。
もう一つ、その差が負の値になる可能性 (= か に負の整数が混ざってしまう可能性) があるのではないかと気になってしまうかもしれない。しかしそれはあり得ない。なぜなら、上記のような の作り方をした場合、 の最小値は 0 になるのだ。 の値はすべて 0 以上であることが保証されているので、 が負になることはあり得ない。
コード
#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; }