Codeforces #704 Div2 : E. Almost Fault-Tolerant Database

Dまではすんなりだったのだけども。
https://codeforces.com/contest/1492/problem/E

問題

M要素の数列がN個与えられる。

M要素の数列のうち、各数列と異なる要素が高々2個であるものがあれば、1例を示せ。

解法

解を1個目の数列と仮置きし、DFSの要領で他の数列と比較していきながら、書き換える位置を決めていこう。
仮置きの解と各数列は、高々4個までしか差があってはならない。
もし3個または4個差があった場合、うち1個か2個は解と一致しなければならないので、DFSの要領で絞り込んでいく。

int N,M;
vector<int> S[252525];
vector<int> C;

int ok(int N) {
	int y,x;
	FOR(y,N+1) {
		int d=0;
		FOR(x,M) d+=C[x]!=S[y][x];
		if(d>2) return 0;
	}
	return 1;
}

void dfs(int cur) {
	vector<int> d;
	if(cur==N) {
		cout<<"Yes"<<endl;
		FORR(c,C) cout<<c<<" ";
		cout<<endl;
		exit(0);
	}
	
	int i;
	FOR(i,M) if(C[i]!=S[cur][i]) d.push_back(i);
	if(d.size()<=2) dfs(cur+1);
	if(d.size()==3) {
		FORR(v,d) {
			int p=C[v];
			C[v]=S[cur][v];
			if(ok(cur)) dfs(cur+1);
			C[v]=p;
		}
	}
	if(d.size()==4) {
		FORR(v1,d) {
			int p1=C[v1];
			C[v1]=S[cur][v1];
			FORR(v2,d) if(v1<v2) {
				int p2=C[v2];
				C[v2]=S[cur][v2];
				if(ok(cur)) dfs(cur+1);
				C[v2]=p2;
			}
			C[v1]=p1;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		FOR(j,M) cin>>x, S[i].push_back(x);
	}
	C=S[0];
	dfs(1);
	
	
	cout<<"No"<<endl;
	
	
}

まとめ

こういうのどうやったら本番中にサクっと思いつけるんだろうな。