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

kmjp's blog

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

Rockethon 2014 Trial Contest: B2. iwiwi

なかなか面白い問題。
http://codeforces.com/contest/395/problem/B2

問題

整数Nが与えられるので、以下の条件を見たし、大きさNの文字列を全て列挙せよ。

  • 文字列はiとwで構成され、文字列中のiの大きさは1、wの大きさは2と計算される。
  • 2つ目以降に列挙する文字列は、直前の文字列から以下のいずれかの処理を1回施して生成できるものでなければならない。
    • 文字列中の"ii"を1か所"w"に置換する。
    • 文字列中の"w"を1か所"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;
	
}

まとめ

結構苦戦したけど自分で気づけて良かった。

広告を非表示にする