TopCoder SRM 812 : Div1 Medium ZeroBoard

まんまとミスしてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17154&rd=18805

問題

行列Aが与えられる。
縦または横で隣接する2要素を選択し、同じだけ値を増減する、という処理を繰り返すことを考える。
ただし途中で負の値が登場してはならない。

要素数の2.5倍以下の処理回数で、全要素を0にできるか。
できるならその手順を示せ。

解法

まず、要素を白黒市松模様状に塗り分けたとき、各処理は、白黒それぞれの総和を同数だけ変化させるので、初期状態で白黒の総和が一致していなければならない。
逆に一致していれば、必ず条件を満たせることを実際に構築で示す。

基本的には端から0にしていく。
A[y][x]＞0の場合、

• A[y][x]≦A[y][x+1]なら、両者をA[y][x]だけ減算すればよい
• A[y][x]≦A[y+1][x]なら、両者をA[y][x]だけ減算すればよい
• どちらも満たせないなら、A[y][x+1]とA[y][x+2]またはA[y][x+1]とA[y+1][x+1]またはA[y+1][x]とA[y+2][x]に不足分を足すことで、上記いずれかの条件を満たすようにしよう。

こうすると、1要素あたり2手で0にすることができる。
処理順によるが、例えばrow-major順で処理した場合、右下より一つ上の要素で、上記処理が行えない場合がある。
その場合、その要素は後回しにして、最下行の処理を行えば、右下角とその上の要素が同じ値になるので、最後に消すことができる。

int A[202][202];

class ZeroBoard {
	public:
	vector<int> ret;
	void down(int y,int x,int v) {
		ret.push_back(y);
		ret.push_back(x);
		ret.push_back(0);
		ret.push_back(v);
		A[y][x]+=v;
		A[y+1][x]+=v;
	}
	void right(int y,int x,int v) {
		ret.push_back(y);
		ret.push_back(x);
		ret.push_back(1);
		ret.push_back(v);
		A[y][x]+=v;
		A[y][x+1]+=v;
	}
	
	vector <int> solve(int R, int C, vector <int> data) {
		int y,x;
		ll sum=0;
		FOR(y,R) FOR(x,C) {
			A[y][x]=data[y*C+x];
			if((y+x)%2) sum+=A[y][x];
			else sum-=A[y][x];
		}
		if(sum) return {-1};
		ret.clear();
		FOR(y,R) FOR(x,C) if(A[y][x]) {
			if(y+1<R&&A[y][x]<=A[y+1][x]) down(y,x,-A[y][x]);
			else if(x+1<C&&A[y][x]<=A[y][x+1]) right(y,x,-A[y][x]);
			else if(x+2<C) {
				int dif=A[y][x]-A[y][x+1];
				right(y,x+1,dif);
				right(y,x,-A[y][x]);
			}
			else if(y+2<R) {
				int dif=A[y][x]-A[y+1][x];
				down(y+1,x,dif);
				down(y,x,-A[y][x]);
			}
			else if(y+1<R&&x+1<C) {
				int dif=A[y][x]-A[y+1][x];
				right(y+1,x,dif);
				down(y,x,-A[y][x]);
			}
		}
		if(A[R-1][C-1]) {
			if(R>=2&&A[R-1][C-1]==A[R-2][C-1]) {
				down(R-2,C-1,-A[R-1][C-1]);
			}
			else if(C>=2&&A[R-1][C-1]==A[R-1][C-2]) {
				right(R-1,C-2,-A[R-1][C-1]);
			}
			else {
				assert(0);
			}
		}
		
		return ret;
	}
}

まとめ

まんまと失敗しました。