AtCoder ABC #164 : F - I hate Matrix Construction

最近のABCではかなりAC者が少なかった問題。
https://atcoder.jp/contests/abc164/tasks/abc164_f

問題

N*Nの行列の各要素に、0～(2^64-1)の範囲の整数値を埋めたい。
各行・列には、以下のいずれかの条件が1つずつ与えられる。

• 行ないし列の全要素のbitwise-orの値
• 行ないし列の全要素のbitwise-andの値

条件を満たす行列は構築可能なら構築せよ。

解法

2進数の桁毎に構築を試みよう。そうすると一度に考える値は0/1の2値になりシンプルになる。
まず、値が確定する箇所は埋めて行く。
例えばbitwise-orの値が0である箇所、bitwise-andの値が1である箇所は埋まる。
また、列と行で指定される値が一致する場合、その値を埋めておいて問題ない。

未確定の場所をとりあえず残りの場所を0で埋めることを考える。
そうすると、「bitwise-orが1である」という行・列のうち、まだ0がない場合、どこかの0を1にしなければならない。
その場合、どこかの「bitwise-andが0である列・行のうち、0が2個以上あるところがあればそこを1にする」ということをどん欲に行おう。
最後に、再度条件を満たすか判定する。
どこかで矛盾があれば解なし。

int N;
int S[505],T[505];
unsigned long long U[505],V[505];
unsigned long long A[505][505];
int B[505][505];
int R[505][2];
int C[505][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	FOR(i,N) cin>>T[i];
	FOR(i,N) cin>>U[i];
	FOR(i,N) cin>>V[i];
	
	FOR(r,64) {
		MINUS(B);
		ZERO(R);
		ZERO(C);
		FOR(i,N) {
			if(S[i]==1 && (U[i]&1)==0) {
				FOR(j,N) {
					if(B[i][j]==1)return _P("-1\n");
					B[i][j]=0;
				}
			}
			if(S[i]==0 && (U[i]&1)==1) {
				FOR(j,N) {
					if(B[i][j]==0)return _P("-1\n");
					B[i][j]=1;
				}
			}
			
			if(T[i]==1 && (V[i]&1)==0) {
				FOR(j,N) {
					if(B[j][i]==1) return _P("-1\n");
					B[j][i]=0;
				}
			}
			if(T[i]==0 && (V[i]&1)==1) {
				FOR(j,N) {
					if(B[j][i]==0) return _P("-1\n");
					B[j][i]=1;
				}
			}
		}
		
		
		FOR(y,N) FOR(x,N) {
			if((U[y]&1)==(V[x]&1)) B[y][x]=U[y]&1;
			if(B[y][x]==-1) B[y][x]=0;
			R[y][B[y][x]]++;
			C[x][B[y][x]]++;
		}
		
			
		FOR(y,N) if(S[y]==1&&(U[y]&1)==1) {
			if(R[y][1]) continue;
			FOR(x,N) if(T[x]==0&&(V[x]&1)==0&&C[x][0]>1) {
				B[y][x]=1;
				R[y][0]--;
				C[x][0]--;
				R[y][1]++;
				C[x][1]++;
				break;
			}
			if(x==N) return _P("-1\n");
		}
		FOR(x,N) if(T[x]==1&&(V[x]&1)==1) {
			if(C[x][1]) continue;
			FOR(y,N) if(S[y]==0&&(U[y]&1)==0&&R[y][0]>1) {
				B[y][x]=1;
				R[y][0]--;
				C[x][0]--;
				R[y][1]++;
				C[x][1]++;
				break;
			}
			if(y==N) return _P("-1\n");
		}
		FOR(y,N) {
			if(S[y]==0&&(U[y]&1)==1&&R[y][1]!=N) return _P("-1\n");
			if(S[y]==0&&(U[y]&1)==0&&R[y][1]==N) return _P("-1\n");
			if(S[y]==1&&(U[y]&1)==1&&R[y][1]==0) return _P("-1\n");
			if(S[y]==1&&(U[y]&1)==0&&R[y][1]!=0) return _P("-1\n");
		}
		FOR(x,N) {
			if(T[x]==0&&(V[x]&1)==1&&C[x][1]!=N) return _P("-1\n");
			if(T[x]==0&&(V[x]&1)==0&&C[x][1]==N) return _P("-1\n");
			if(T[x]==1&&(V[x]&1)==1&&C[x][1]==0) return _P("-1\n");
			if(T[x]==1&&(V[x]&1)==0&&C[x][1]!=0) return _P("-1\n");
		}
		
		FOR(y,N) FOR(x,N) if(B[y][x]) A[y][x]|=1ULL<<r;
		FOR(j,N) U[j]>>=1,V[j]>>=1;
	}
	
	
	
	FOR(y,N) {
		FOR(x,N) cout<<A[y][x]<<" ";
		cout<<endl;
	}
	
}

まとめ

難易度も高めだけど、どうしても実装量が増えるなぁ。