TopCoder SRM 568 Div1 Medium EqualSums

解けてないDiv1 Mediumを復習。
これ本番の正答率は相当低かったけど、Editorialを見るとあっけないほど簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=12364

問題

元の問題の文章はわかりにくいので意訳。
0以上の整数値で構成されるNxNの行列A[N][N]があるとする。
ここから、全体でN要素を選び、かつそれらは各列から１個、各行から１個ずつ選ぶようにする。
N要素をどう選んでも、その和が同じになるようにしたい。

NxNの行列のうちいくつかの要素が与えられたとき、条件を満たす残りの要素の埋め方を答えよ。
なお、事前に与えられる要素は、残りの要素の選び方が有限になるように設定される。

解法

Editorialを参照して解いた。

まず前提として、最初に与えられた要素においては、各列・各行に１つも要素がない列・行はない。
１つも要素が無い列・行はいくらでも大きな数字を入れられてしまい選び方が有限にならない。

まず、各列・各行から１個ずつ選んだ時に和が等しくなる行列の条件を考える。
これは、まずN個の列にそれぞれに0以上の整数値R[i]を割り当て、N個の行に同様に整数値C[j]を割り当てたとする。
このときA[i][j]=R[i]+C[j]となるようにするとよい。
このとき、N個の要素の和はR[0]+…+R[N-1]+C[0]+…+C[N-1]になる。

なお、R[0]～R[N-1]がすべて１以上の時、R[0]～R[N-1]から１引いて、C[0]～C[N-1]に1を加えてもそこから得られる行列Aは一致する。
よって、R[0]～R[N-1]の選び方のうち１個以上0を含むケースの選び方をDFSで処理すればよい。

• 未知のR[i]に0～9の任意の値を選ぶ。
• 各jについてA[i][j]が確定済みの場合、C[j]はA[i][j]-R[i]になる。
• C[j]が確定するので、同様に各kについてA[k][j]が確定済みの場合、R[k]はA[k][j]-C[j]となる。

上記手順を繰り返してR・Cを埋めていく。
R[i]・C[i]が負になった場合、その構成は実現不可。
実現可能なR[i]の構成のうち、１個以上0を含むケースの数が答え。

ll mo=1000000007;

class EqualSums {
	int N;
	vector <string> B;
	int vis[101];
	int num[101];
	public:
	
	int okok(int cur) {
		int ok=1;
		int x,y,z;
		
		vis[cur]++;
		if(cur<N) {
			// row
			FOR(x,N) {
				if(B[cur][x]=='-') continue;
				z=B[cur][x]-'0'-num[cur];
				if(z<0) return 0;
				
				if(num[x+N]==-1) {
					num[x+N]=z;
					if(okok(x+N)==0) return 0;
				}
				else if(num[x+N]!=z) return 0;
			}
		}
		else {
			// col
			cur-=N;
			FOR(y,N) {
				if(B[y][cur]=='-') continue;
				z=B[y][cur]-'0'-num[cur+N];
				if(z<0) return 0;
				
				if(num[y]==-1) {
					num[y]=z;
					if(okok(y)==0) return 0;
				}
				else if(num[y]!=z) return 0;
			}
		}
		return 1;
	}
	
	
	int count(vector <string> board) {
		int y,x,x2,y2,l,i;
		ll tot=1,totz=1;
		N=board.size();
		B=board;
		
		ZERO(vis);
		FOR(i,2*N) {
			if(vis[i]) continue;
			
			int z=0,noz=0;
			
			FOR(x,10) {
				fill(num,num+2*N,-1);
				num[i]=x;
				if(okok(i)) {
					y=0;
					FOR(l,N) if(num[l]==0) y++;
					if(y) z++;
					else noz++;
				}
			}
			tot=(tot*(noz+z)) % mo;
			totz=(totz*noz) % mo;
		}
		
		return (tot+mo-totz)%mo;
	}
};

まとめ

発想が面白い問題。
最初のRとCからA[i][j]=R[i]+C[j]を作れる、って発想にたどり着ければゴールは近いな。