Codeforces #959 : G. Minecraft

コードはそこまで長くない。
https://codeforces.com/contest/1994/problem/G

問題

2進数K桁の整数Sと、2進数K桁の整数N個からなる整数列Aが与えられる。

2進数K桁の整数Xのうち、sum(A[i] xor X)がSとなるようなものがあるか判定せよ。

解法

Xの下の桁から0または1を定めたとき、以下を考える。
f(n,c) := 下からn桁目までXを定めたとき、それがSと一致していてかつ上の桁への繰り上がりがcである場合が存在するか。存在するならn桁目の0/1がどちらか

cはO(N)程度まで考えればいいので、このf(n,c)はO(NK)で埋められる。
あとはDPの復元をすればよい。

int T,N,K;
string S[2020202];
vector<pair<int,int>> dp[2020202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N+1) {
			cin>>S[i];
			reverse(ALL(S[i]));
		}
		FOR(i,K+2) {
			dp[i].clear();
			dp[i].resize(N+1,{-1,-1});
		}
		dp[0][0]={0,0};
		FOR(i,K) {
			x=0;
			FOR(j,N) if(S[j+1][i]=='1') x++;
			y=N-x;
			FOR(j,N+1) if(dp[i][j].first>=0) {
				if((j+x)%2==S[0][i]-'0') dp[i+1][(j+x)/2]={j,0};
				if((j+y)%2==S[0][i]-'0') dp[i+1][(j+y)/2]={j,1};
			}
		}
		if(dp[K][0].first==-1) {
			cout<<"-1"<<endl;
		}
		else {
			string V;
			int ca=0;
			for(i=K;i>0;i--) {
				auto p=dp[i][ca];
				V+='0'+p.second;
				ca=p.first;
			}
			cout<<V<<endl;
		}
		
		
		
		
	}
		
}

まとめ

そこまで難しくないけど、Fで時間切れで本番中に解き切れなかった…。