Codeforces #375 Div2 C. Polycarp at the Radio

不参加でした。
http://codeforces.com/contest/723/problem/C

問題

N個の曲があり、i番目の歌はA[i]組目のバンドが歌う。
なお、ここで曲構成を考える人は1～M組目までのバンドが好きで、それ以外は嫌いである。

幾つかの曲を歌うバンドを変え、好みのバンドが歌う回数の最小値を最大化したい。
また、その最大化した最小値を叶えるうえで、変えるバンドの数を最小化する変え方を答えよ。

解法

問題文がかなり罠で、(M+1)組目以降のバンドがいても構わない。
つまり、先頭M組までのバンドがN/M回ずつ登場すればよいことになる。

よって以下のようにする。

• (M+1)組目以降が歌う予定のバンドがある場合、1～M組目のうち登場回数がN/M回未満のものがあれば、それに変える。
• それでも1～M組目がまだN/M回ずつ登場しない場合、1～M組目のうちN/M回を超えて歌っている箇所を見つけて、不足している箇所に変える。

int N,M;
int A[2020];
int num[2020];
int ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	int tar=N/M;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]<=M) num[A[i]]++;
	}
	FOR(i,N) {
		if(A[i]>M || num[A[i]]>tar) {
			x=min_element(num+1,num+M+1)-num;
			if(num[x]>=tar) break;
			ret++;
			if(A[i]<=M) num[A[i]]--;
			A[i]=x;
			num[A[i]]++;
		}
	}
	
	_P("%d %d\n",*min_element(num+1,num+M+1),ret);
	FOR(i,N) _P("%d%c",A[i],(i==N-1)?'\n':' ');
	
}

まとめ

好きじゃないバンドといいつつ、残してもいいというのがひどい罠。確かに問題文中に全部消せとは書いてないけどさぁ。
CFのサイト上でも割と非難されていた。