TopCoder SRM 627 Div1 Easy HappyLetterDiv1

SRM627に参加。今回は珍しくEasy,Mediumが順調に解けて良い順位が取れた。
http://community.topcoder.com/stat?c=problem_statement&pm=13274

問題

文字列Sが与えられる。
この文字列から、異なる２つの文字を取り除くという処理を残りの文字が１種類になるまで続ける。
最後に残すことができる文字をすべて答えよ。

解法

先に残す文字の種類と数を総当たりで決め打ちし、他の文字を全て消すことができるかチェックすればよい。
他の文字をすべて消せる条件は、消す文字数が偶数であることと、過半数を占める文字がないことである。
過半数を占める文字がなければ、異なる２つの文字を取り除いて消すことができる。

class HappyLetterDiv1 {
	public:
	int num[26];
	
	int okok() {
		int i,sum=0,ma=0;
		FOR(i,26) sum+=num[i],ma=max(ma,num[i]);
		if(sum%2) return 0;
		if(ma*2>sum) return 0;
		return 1;
	}
	
	string getHappyLetters(string letters) {
		int L=letters.size();
		string res="";
		int i,j;
		
		ZERO(num);
		FOR(i,L) num[letters[i]-'a']++;
		FOR(i,26) if(num[i]) {
			int ok=0;
			for(j=1;j<=num[i];j++) {
				num[i]-=j;
				ok|=okok();
				num[i]+=j;
			}
			if(ok) res+='a'+i;
		}
		return res;
	}
}

まとめ

色々な属性の集合から、異なるものを２つずつペアにするには過半数を占める同一要素があってはならない、というのは過去のSRMでも出てきたテクだね。