これさっさと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; } } }
まとめ
昔過ぎて、こんな問題あったこと忘れそう。