yukicoder : No.233 めぐるはめぐる (3)

こちらも★３になった問題。
http://yukicoder.me/problems/537

問題

"inabameguru"を並べ替えて出来る文字列のうち、以下を満たすものを１つ求めよ。

• 与えられた文字列集合Sに含まれない。
• ローマ字として成立する(子音の後には母音が続いている)

解法

"inabameguru"を並べ替えてできるローマ字として成立する文字列を列挙できれば、あとはSに含まれうか判断するだけ。

"inabameguru"には子音が5個、母音が6個あるので、子音の後に母音が続けても、１個母音があまる。
そこで以下のようにすると全文字列を列挙できる(重複するものが生成されることもある)

• 子音の並び順をnext_permutationで全列挙(5!通り)
• 母音の並び順をnext_permutationで全列挙(6!通り)
• 子音の1文字目・母音の1文字目・子音の2文字目・母音の2文字目…と並べた10文字の文字列を作る。最後に余った母音の6文字目をどこかに挿入する(11通り)

重複もあるが、上記手順で生成される文字列は計5!*6!*11=950,400通り。
毎回Sから存在判定してもまぁ間に合う。

int N;
set<string> S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>s, S.insert(s);
	
	string a,b;
	a="iaaeuu";
	b="nbmgr";
	sort(ALL(a));
	sort(ALL(b));
	do {
		do {
			string c="          ";
			FOR(i,5) c[i*2]=b[i],c[i*2+1]=a[i];
			FOR(i,11) {
				s=c.substr(0,i)+a[5]+c.substr(i);
				if(S.count(s)==0) return _P("%s\n",s.c_str());
			}
		} while(next_permutation(ALL(b)));
	} while(next_permutation(ALL(a)));
	return _P("NO\n");
}

まとめ

本問題に出てくるめぐるちゃんはyukicoderで上位ランカーとのことです。
色々事情もあるとは思いますが、個人的にはめぐるちゃんが再びyukicoderを席巻する日を期待しております。