くれなゐの雑記

例を上げて 自分で手を動かして学習できる入門記事を多めに書いています

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

競技プログラミング

解説に乗ってるけどちょっとわかりにくかったので自分の言葉に置き換えて整理します。 あとイラレの練習(
http://code-festival-2016-quala.contest.atcoder.jp/data/other/code-festival-2016-quala/editorial.pdf
)

問題

code-festival-2016-quala.contest.atcoder.jp

要約

行列A = [a_{i,j}], (i \in [1,R], j \in [1,C]) が与えられる.
N個の要素には, すでに値が記入されている.
すべての値は, 以下の条件を満たさなければならない.

条件1. すべての範囲内のi,jに対して, a_{i,j}+a_{i+1,j+1} = a_{i+1,j} + a_{i,j+1}
条件2. a_{i,j} >= 0

問題の変形

この問題では, 変形が重要です.

条件1の変形

条件1を変形すると,
a_{i,j}-a_{i,j+1} = a_{i+1,j} - a_{i+1,j+1}
となり, 左右同士の差は上下で等しいことがわかります。図の矢印方向の差が等しいということですね
f:id:kurenaif:20160925221650j:plain
上下で等しい 上下で等しい… と下へ下へつなげていくと, 結局同じ列どうしの比較だと, 行にかかわらず差が等しいことがわかります。
f:id:kurenaif:20160925222232j:plain

さすがに, 列が違うと差は変わってきます.(同じだと思ってた時期が私にもありました…)
ここで, それぞれの行の一番左の値(a_{1,1} ,\cdots,a_{R,1}) を 簡単のためにx_1, \cdots, x_R とおき,
a_{i,0}-a_{i,1}, a_{i,1}-a_{i,2}, \cdots, a_{i,C-1}-a_{i,C} を y_1, \cdots, y_C とおきます.
f:id:kurenaif:20160925223126j:plain

すると, a_{i,j} = x_i + y_1 + y_2 + \cdots + y_C と表記できることがわかります.

y は y_j = y_1 + y_2 + \cdots + y_j = \sum_{i=1}^{j} y_i と置き換えると,

a_{i,j} = x_i + y_j と簡単にすることができます。(画像つくり忘れたんですけど, 矢印が左端からそのマスまでたどり着いてるイメージですね)

詳しい証明は解説参照で, ざっくりいうと, 条件1が成立するためには,
すべてのa_{i,j} = x_i + y_j を満たすような, (x_1,\cdots,x_R), (y_1,\cdots,y_C) が存在しなければならない.
ということになります.

条件2の変形

条件2は, 条件1と組み合わせて,
すべての i,jで,
a_{i,j} = x_i + y_j >= 0
が成立する必要があります. 全通り試すともちろん時間が足りないので, 工夫が必要です.
実は, x_i, y_j のとり方はuniqueではありません. 例えば, x_iを+1したら, y_jを-1したら良いです.
一番小さいところからスタートして(x), 一番小さい値を足す(負の数)と, a_{i,j} の最小値が求まり, これが0以上になればOKっぽそうです

実装方針

a_{i,j} = x_i + y_j を求める.

グラフを使って求めます. x_iとy_iを頂点と捉えます.
その間を入力r,c,aを使って
x_r と y_c をつなぐ重さaの辺を貼ります.
この時辺と頂点の関係を, x_r + y_c = a と定義します.

二変数なので, なにか一つ値を決めないといけません. 一つ値を適当に0(なんでもいいです)と決めると, あとは随時決まっていくのがわかると思います.
(例えば, x_0 + y_1 = 3, x_0+y_2 = 4 という風に辺が張られていたら, x_0=0と定めると, y_1, y_2は自ずと決まってきます)

こんな感じでDFSで求めていきます.

条件2

DFSと一緒に, xの最小値とyの最小値を更新しながら探索していきます.
xの最小値+yの最小値 < 0 ならば, "No" となります.

実装する上での注意点

xの最小値とyの最小値の初期値に注意しなければなりません
処理をするときに, x_i + y_j のように描いていると, オーバーフローするのでこのような実装をするならば, 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;