TopCoderOpen 2019 Round2B : Easy MedianFaking

なんかMedium早解きでHighest更新した。
https://community.topcoder.com/stat?c=problem_statement&pm=15525

問題

F人の人がそれぞれM要素の整数列を持つ。
このうち何人かの要素を書き換え、中央値がTとなるようにしたい。

• 要素を書き換える人数は最小何人か
• その時書き換える総要素数は最小何個か

解法

F*M個の要素を、T未満・T・Tより大きい、の3通りに分類しよう。
T未満またはTより大きい値が中央値に来ているなら、中央値を超過している分だけTにしなければいけない。
この時点で総要素数は確定する。

あとは要素を書き換える人数を最小にしたいので、書き換える対象の要素を多く持っている人から順に選ぼう。

class MedianFaking {
	public:
	vector <int> minimize(int F, int M, vector <int> data, int goal) {
		int C[3]={};
		int N=F*M;
		FORR(d,data) {
			if(d<goal) d=0;
			else if(d>goal) d=2;
			else d=1;
			C[d]++;
		}
		
		int target,del;
		int x,y;
		vector<int> V;
		if(C[0]>=(N+1)/2) {
			target=0;
			del=C[0]-(N+1)/2+1;
			
		}
		else if(C[2]>=N/2+1) {
			target=2;
			del=C[2]-(N/2+1)+1;
		}
		else {
			return {0,0};
		}
		
		FOR(x,F) {
			int sum=0;
			FOR(y,M) if(data[x*M+y]==target) sum++;
			V.push_back(sum);
		}
		sort(ALL(V));
		reverse(ALL(V));
		
		int lef=0;
		FOR(x,F) {
			lef+=V[x];
			if(lef>=del) return {x+1,del};
		}
		
		return {};
	}
}

まとめ

Easyだけど自分も周りも割と手間取った感じ。