なかなか面白い問題。
http://codeforces.com/contest/395/problem/B2
問題
整数Nが与えられるので、以下の条件を見たし、大きさNの文字列を全て列挙せよ。
- 文字列はiとwで構成され、文字列中のiの大きさは1、wの大きさは2と計算される。
- ２つ目以降に列挙する文字列は、直前の文字列から以下のいずれかの処理を１回施して生成できるものでなければならない。
- 文字列中の"ii"を１か所"w"に置換する。
- 文字列中の"w"を１か所"ii"に置換する。
解法
なんらかの法則を見つけて列挙していかないといけないのは明らか。
試しにN=5やN=6で列挙すると以下のようになる。
N=5 iwii iww iiiw iiiii iiwi wwi wiii wiw N=6 iwiw iwiii iwwi iiiwi iiiiii iiiiw iiww iiwii wwii www wiiw wiiii wiwi
ここから、最初に先頭が"iw"のものが来て、ついで"ii"、最後に"w"で始まるものが来ている。
この事実から、N>=4において以下のように再帰的に生成すればよい。
- 大きさ(N-3)の文字列群の頭に"iw"を付けたものを列挙する。
- 大きさ(N-2)の文字列群の頭に"ii"を付けたものを列挙する。
- 大きさ(N-2)の文字列群を逆順にして、それぞれ頭に"w"を付けたものを列挙する。
こうすると再帰的に先頭が"iw"->"ii"->"w"となるルールも保持できる。
vector<string> S[21]; void dpdp(int N) { int i; FOR(i,S[N-3].size()) S[N].push_back("iw"+S[N-3][i]); FOR(i,S[N-2].size()) S[N].push_back("ii"+S[N-2][i]); FOR(i,S[N-2].size()) S[N].push_back("w"+S[N-2][S[N-2].size()-1-i]); } void solve() { int f,i,j,k,l,x,y; int N,mask; cin>>N; S[1].push_back("i"); S[2].push_back("ii"); S[2].push_back("w"); S[3].push_back("iw"); S[3].push_back("iii"); S[3].push_back("wi"); for(i=4;i<=N;i++) dpdp(i); ITR(it,S[N]) cout<<*it<<endl; }
まとめ
結構苦戦したけど自分で気づけて良かった。
