kmjp's blog

競技プログラミング参加記です

Codeforces #658 Div1 C. Mastermind

これさっさとCやればよかった。
http://codeforces.com/contest/1381/problem/C

問題

1~(N+1)のうち任意の整数を取れるN要素の数列Aを当てるマスターマインドを考える。
入力で与えられる数列Bを指定したところ、ヒットがX、ヒットとブローの和がYだった。
条件を満たすAを構築せよ。

解法

数列はN+1個の値から選択可能なので、Bのうち(N-Y)個を選択し、Bに現れない値をAに入れれば、Yを狙った値にできる。
あとはXを合わせることを考える。

もしAの一部とBの一部が完全にヒットまたはブローの関係にある場合、Bの過半数が同じ値だとXを0にできない。
そう考えると、逆に上記手順でYを調整する際は、Bのうち登場回数が過半数な値を積極的に書き換えていくのが良い。

あとはXを合わせる際は同様に、登場回数の多い順にA[i]=B[i]となるよう合わせていこう。
最後、ブローではあるがヒットではない要素については、よくある数列を半分rotateするテク(厳密には、Aが未確定の位置について、Bの要素を昇順に並べて半分rotateして元の位置に戻すテク)を使えばよい。

int T;
int N,X,Y;
int C[101010];
int A[101010];
int B[101010];
vector<int> M[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X>>Y;
		int ma=0;
		FOR(i,N+2) M[i].clear();
		
		FOR(i,N) {
			cin>>A[i];
			B[i]=-1;
			M[A[i]].push_back(i);
		}
		set<pair<int,int>> cand;
		FOR(i,N+2) cand.insert({-(int)M[i].size(),i});
		int emp=0;
		for(i=1;i<=N+1;i++) if(M[i].empty()) emp=i;
		
		while(X) {
			X--,Y--;
			x=cand.begin()->second;
			cand.erase(cand.begin());
			y=M[x].back();
			B[y]=A[y];
			M[x].pop_back();
			cand.insert({-(int)M[x].size(),x});
		}
		
		vector<int> step;
		FORR(m,cand) {
			FORR(c,M[m.second]) step.push_back(c);
		}
		
		Y=step.size()-Y;
		
		FOR(i,step.size()) {
			B[step[(i+step.size()/2)%step.size()]]=A[step[i]];
		}
		FORR(s,step) if(A[s]==B[s] && Y) B[s]=emp, Y--;
		FORR(s,step) if(B[s]!=emp && Y) B[s]=emp, Y--;
		
		
		int ng=0;
		FORR(s,step) if(A[s]==B[s]) ng=1;
		if(ng==0) {
			cout<<"YES"<<endl;
			FOR(i,N) cout<<B[i]<<" ";
			cout<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
		
	}
}

まとめ

昔過ぎて、こんな問題あったこと忘れそう。