kmjp's blog

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

Code Formula 2014 本選 : E - ab文字列

その他コンテスト

これも何とか自力回答。
http://code-formula-2014-final.contest.atcoder.jp/tasks/code_formula_2014_final_e

問題

文字列 F_{n,k}は以下のように定義される。

  • F_{1,0}="b"
  • F_{2,0}="a"
  • n \ge 3かつ 0 \ge k \gt 2^{n-2}の時
    • kが偶数なら F_{n,k} = F_{n-1,k/2} + F_{n-2,k/4}
    • kが奇数なら F_{n,k} = F_{n-2,k/4} + F_{n-1,k/2}

F_{n,k}である、ある文字列Sが与えられるのでn,kを求めよ。

解法

F_{n,k}におけるaとbの数はnで決まり、kに依存しない。また文字列長もnで決まる。
（そもそも F_{n,k}の文字列長はフィボナッチ数列になる）

よってSの文字列長からnは容易に求められる。
あとはkを総当たりする。
S = F_{n,k}と仮定して F_{n,k}を F_{n-1,k/2}と F_{n-2,k/4}で再帰的に分割していき、a,bの数がSの部分文字列と一致するか判定していく。

ただ、下記のコードでは高速化のためn≦11の範囲は F_{n,k}を全パターン列挙し、直接一致判定をして再帰をそこで終了している。

string S;
string FF[12][5000];
int F[3][55];
int num[2][20001];

int okok(int level,int k,int offset) {
	if(level<10) return S.substr(offset,FF[level][k].size())==FF[level][k];
	int len=F[2][level];
	if(num[0][offset+len]-num[0][offset]!=F[0][level]) return 0;
	if(num[1][offset+len]-num[1][offset]!=F[1][level]) return 0;
	
	if(k%2) return okok(level-2,k/4,offset) && okok(level-1,k/2,offset+F[2][level-2]);
	else return okok(level-1,k/2,offset) && okok(level-2,k/4,offset+F[2][level-1]);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	if(S=="a") return _P("2 0\n");
	if(S=="b") return _P("1 0\n");
	FOR(i,S.size()) num[0][i+1]=num[0][i]+(S[i]=='b');
	FOR(i,S.size()) num[1][i+1]=num[1][i]+(S[i]=='a');
	
	FF[1][0]="b";
	FF[2][0]="a";
	for(i=3;i<=11;i++) FOR(k,1<<(i-2)) {
		if(k%2) FF[i][k]=FF[i-2][k/4]+FF[i-1][k/2];
		else FF[i][k]=FF[i-1][k/2]+FF[i-2][k/4];
	}
	
	F[0][1]=F[2][1]=1;
	F[1][2]=F[2][2]=1;
	for(i=3;i<=25;i++) F[0][i]=F[0][i-1]+F[0][i-2];
	for(i=3;i<=25;i++) F[1][i]=F[1][i-1]+F[1][i-2];
	for(i=3;i<=25;i++) F[2][i]=F[2][i-1]+F[2][i-2];
	
	for(x=3;x<=35;x++) if(F[2][x]==S.size()) break;
	FOR(y,1<<(x-2)) if(okok(x,y,0)) return _P("%d %d\n",x,y);
}

まとめ

aとbの数で簡易判定することには割とさっくり到達できたので良かった。