読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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)みたいな処理も考えたけど、場合分けが面倒で力技にしてしまった。
でもこういうネタ回答も結構好きだったり。

広告を非表示にする