解説に乗ってるけどちょっとわかりにくかったので自分の言葉に置き換えて整理します。 あとイラレの練習(
http://code-festival-2016-quala.contest.atcoder.jp/data/other/code-festival-2016-quala/editorial.pdf
)
要約
行列 が与えられる.
個の要素には, すでに値が記入されている.
すべての値は, 以下の条件を満たさなければならない.
条件1. すべての範囲内のに対して,
条件2.
問題の変形
この問題では, 変形が重要です.
条件1の変形
条件1を変形すると,
となり, 左右同士の差は上下で等しいことがわかります。図の矢印方向の差が等しいということですね
上下で等しい 上下で等しい… と下へ下へつなげていくと, 結局同じ列どうしの比較だと, 行にかかわらず差が等しいことがわかります。
さすがに, 列が違うと差は変わってきます.(同じだと思ってた時期が私にもありました…)
ここで, それぞれの行の一番左の値() を 簡単のために とおき,
を とおきます.
すると, と表記できることがわかります.
は と置き換えると,
と簡単にすることができます。(画像つくり忘れたんですけど, 矢印が左端からそのマスまでたどり着いてるイメージですね)
詳しい証明は解説参照で, ざっくりいうと, 条件1が成立するためには,
すべての を満たすような, , が存在しなければならない.
ということになります.
条件2の変形
条件2は, 条件1と組み合わせて,
すべての で,
が成立する必要があります. 全通り試すともちろん時間が足りないので, 工夫が必要です.
実は, のとり方はuniqueではありません. 例えば, を+1したら, を-1したら良いです.
一番小さいところからスタートして(), 一番小さい値を足す(負の数)と, の最小値が求まり, これが0以上になればOKっぽそうです
実装方針
を求める.
グラフを使って求めます. とを頂点と捉えます.
その間を入力を使って
と をつなぐ重さの辺を貼ります.
この時辺と頂点の関係を, と定義します.
二変数なので, なにか一つ値を決めないといけません. 一つ値を適当に0(なんでもいいです)と決めると, あとは随時決まっていくのがわかると思います.
(例えば, , という風に辺が張られていたら, と定めると, は自ずと決まってきます)
こんな感じでDFSで求めていきます.
条件2
DFSと一緒に, xの最小値とyの最小値を更新しながら探索していきます.
xの最小値+yの最小値 < 0 ならば, "No" となります.
実装する上での注意点
xの最小値とyの最小値の初期値に注意しなければなりません
処理をするときに, のように描いていると, オーバーフローするのでこのような実装をするならば, LLONG_MAX/2-1程度を上限にすると良いでしょう.
SourceCode
const ll INF = LLONG_MAX / 2 - 1; struct Edge { ll t; ll c; Edge(ll to, ll cost):t(to),c(cost){} Edge(){} }; vector<ll> weigh; ll R, C; bool DFS(ll node, vector<vector<Edge> >& edge, ll& xmin, ll& ymin) { if (node < R) xmin = min(xmin, weigh[node]); else ymin = min(ymin, weigh[node]); for (auto &to : edge[node]) { if (weigh[to.t] == INF) { weigh[to.t] = to.c - weigh[node]; if (not DFS(to.t, edge, xmin, ymin)) return false; } else { if (weigh[to.t] + weigh[node] != to.c) return false; } } return true; } void solve() { cin >> R >> C; ll N = in(); weigh.resize(R + C, INF); vector<vector<Edge> > edge(R+C); REP(i, N) { ll r, c, a; cin >> r >> c >> a; --r; --c; edge[r].emplace_back(R+c,a); edge[R+c].emplace_back(r, a); } bool res = true; ll xmin, ymin; REP(i, R + C) if(weigh[i] == INF and edge[i].size() > 0) { xmin = ymin = numeric_limits<int>::max(); weigh[i] = 0; if (not DFS(i,edge,xmin,ymin) or xmin+ymin < 0) { cout << "No" << endl; return; } } cout << "Yes" << endl;