yukicoder : No.145 yukiover

貪欲で解いた。
http://yukicoder.me/problems/236

問題

N個のアルファベットが与えられる。
これらのアルファベットを幾つかのグループに分け、かつ並べ替えてそれぞれで単語を作る。
'yuki'より辞書順で大きい単語をいくつ作れるか。

解法

yukiは幸いアルファベット降順に並んでいる。
以下の順で貪欲にアルファベットを貪欲に使っていく。

• 'yuki'+('i'未満の文字)
• 'yukii'
• 'yukj'
• 'yukk'
• 'yu'+('l'～'t')
• 'yuu'
• 'y'+('v'～'x')
• 'yy'
• 'z'

int N;
string S;
int abcdefgh,i,j,k,lmnopqrst,u,vwx,y,z;
int ret;

void solve() {
	int x; string s;
	
	cin>>N>>S;
	FOR(x,N) {
		if(S[x]=='z') z++;
		else if(S[x]=='y') y++;
		else if(S[x]>'u')  vwx++;
		else if(S[x]=='u') u++;
		else if(S[x]>'k')  lmnopqrst++;
		else if(S[x]=='k') k++;
		else if(S[x]>'i')  j++;
		else if(S[x]=='i') i++;
		else abcdefgh++;
	}
	
	while(y && u && k && i && abcdefgh) ret++, y--, u--, k--, i--, abcdefgh--;
	while(y && u && k && i>=2)          ret++, y--, u--, k--, i-=2;
	while(y && u && k && j)             ret++, y--, u--, k--, j--;
	while(y && u && k>=2)               ret++, y--, u--, k-=2;
	while(y && u && lmnopqrst)          ret++, y--, u--, lmnopqrst--;
	while(y && u>=2)                    ret++, y--, u-=2;
	while(y && vwx)                     ret++, y--, vwx--;
	while(y>=2)                         ret++, y-=2;
	while(z)                            ret++, z--;
	
	cout<<ret<<endl;
}

まとめ

min(y,(y+それ以外)/2)みたいな処理も考えたけど、場合分けが面倒で力技にしてしまった。
でもこういうネタ回答も結構好きだったり。