Codeforces #709 Div1 : A. Basic Diplomacy

中盤詰まりすぎてダメダメだった回。
https://codeforces.com/contest/1483/problem/A

問題

M個の空でない数列が与えられる。
それぞれから1つずつ値を選ぶとき、同じ値が過半数選ばれないようにしたい。
そのような選び方を1つ求めよ。

解法

もし過半数の数列で登場する値がなければ、適当に各数列から1個ずつ値を選べばよい。
そうでない場合、まず最多登場の値を求めよう。

あとは、そこからいくつかその値の登場頻度を減らし、過半数にならないようにする。
これは、最多登場の値が過半数である間、その値を含んで2要素以上ある数列があれば、最多登場ではない方の値を選ぶことにすればよい。
最多登場の値がちょうど半数現れるようにすれば、他の値が過半数登場してしまうことはない。

int T,N,M;
vector<int> V[101010];
int C[202020];
int R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) C[i+1]=0;
		FOR(i,M) {
			cin>>x;
			V[i].resize(x);
			FOR(j,x) {
				cin>>V[i][j];
				C[V[i][j]]++;
			}
		}
		int ma=0;
		for(i=1;i<=N;i++) if(C[i]>C[ma]) ma=i;
		int del=max(0,C[ma]-(M+1)/2);
		FOR(i,M) {
			if(count(ALL(V[i]),ma)) {
				if(del==0) {
					R[i]=ma;
				}
				else if(V[i].size()>1) {
					del--;
					if(V[i][0]==ma) R[i]=V[i][1];
					else R[i]=V[i][0];
				}
				else {
					R[i]=ma;
				}
			}
			else {
				R[i]=V[i][0];
			}
		}
		if(del==0) {
			cout<<"YES"<<endl;
			FOR(i,M) cout<<R[i]<<" ";
			cout<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
		
	}
}

まとめ

もっと短く書けそう。