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

苦戦しまくった。
http://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_d

問題

R*Cのグリッドがある。
各セル(r,c)には非負整数f(r,c)を当てはめたい。
既に一部のセルには値が埋められている。

このグリッドから2*2のセル群を取ったとき、左上と右下のセルの整数の和と、左下と右上のセルの整数の和が一致するようにしたい。
条件を満たす非負整数の埋め方は存在するか判定せよ。

解法

2*2のセル群に対する条件から、２つの隣接列のセルの差はどの行も等しく、２つの隣接行のセルの差はどの列も等しくなければならないことがわかる。
これを達成するには、各行rに対し整数列P[r]、各行cに対し整数列Q[c]を考えると、f(r,c)=P[r]+Q[c]の形になればよい。

隣接でなくても良いので、同じ列にある２セル(r1,c),(r2,c)の値が分かればP[r1]とP[r2]の差がわかるし、同じ行にある２セル(r,c1),(r,c2)の値が分かればQ[c1]とQ[c2]の差がわかる。
そこで、入力で値が確定しているセル(r,c)に対しP[r],Q[c]が未確定なセルがあった場合、P[r]=f(r,c)、Q[c]=0で仮置きしよう。
するとそのセルと同じ行または列のセル(r',c')をDFSで探索していき、順次P[r']・Q[c']を求めていこう。

途中、こうして求めたP[r],Q[c]に対し入力で与えられた値と不一致になる場合がある。
その場合は解は「存在しない」となる。

また、P[r]の最小値とQ[c]の最小値の和が負の場合、値が負のセルができるのでやはり解は「存在しない」。
それ以外の場合は存在する。

int H,W;
int N;
int Y[101010],X[101010],A[101010];

ll XX[101010],YY[101010];
vector<pair<int,int>> XL[101010];
vector<pair<int,int>> YL[101010];

vector<int> LR[101010];
vector<int> UD[101010];

ll mix,miy;
int did[101010];

void dfs(int cur) {
	int cx=X[cur];
	int cy=Y[cur];
	
	if(XX[cx]!=-1LL<<60 && YY[cy]!=-1LL<<60 && XX[cx]+YY[cy]!=A[cur]) {
		cout<<"No"<<endl;
		exit(0);
	}
	if(did[cur]) return;
	did[cur]=1;
	
	if(XX[cx]==-1LL<<60 && YY[cy]==-1LL<<60) {
		XX[cx]=A[cur];
		YY[cy]=0;
		mix=XX[cx];
		miy=YY[cy];
	}
	if(XX[cx]==-1LL<<60) {
		XX[cx]=YY[cy]-A[cur];
		mix=min(XX[cx],mix);
	}
	if(YY[cy]==-1LL<<60) {
		YY[cy]=XX[cx]-A[cur];
		miy=min(YY[cy],miy);
	}
	
	FORR(e,LR[cur]) {
		XX[X[e]] = XX[cx] + (A[e] - A[cur]);
		mix=min(XX[X[e]],mix);
		dfs(e);
	}
	FORR(e,UD[cur]) {
		YY[Y[e]] = YY[cy] + (A[e] - A[cur]);
		miy=min(YY[Y[e]],miy);
		dfs(e);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,101000) XX[i]=YY[i]=-1LL<<60;
	
	cin>>H>>W>>N;
	FOR(i,N) {
		cin>>Y[i]>>X[i]>>A[i];
		Y[i]--;
		X[i]--;
		YL[Y[i]].push_back({X[i],i});
		XL[X[i]].push_back({Y[i],i});
	}
	FOR(y,H) if(YL[y].size()>1) {
		sort(ALL(YL[y]));
		FOR(i,YL[y].size()-1) {
			LR[YL[y][i].second].push_back(YL[y][i+1].second);
			LR[YL[y][i+1].second].push_back(YL[y][i].second);
		}
	}
	FOR(x,W) if(XL[x].size()>1) {
		sort(ALL(XL[x]));
		FOR(i,XL[x].size()-1) {
			UD[XL[x][i].second].push_back(XL[x][i+1].second);
			UD[XL[x][i+1].second].push_back(XL[x][i].second);
		}
	}
	
	FOR(i,N) if(XX[X[i]]==-1LL<<60 && YY[Y[i]]==-1LL<<60) {
		dfs(i);
		if(mix+miy<0) {
			cout<<"No"<<endl;
			return;
		}
	}
	
	cout<<"Yes"<<endl;
	
}

まとめ

なんでこんな手間取ったんだろう。