kmjp's blog

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

yukicoder : No.600 かい文回

アプローチはすぐ思い浮かんだ。
https://yukicoder.me/problems/no/600

問題

No.599の逆である。
No.599の解がNとなるような文字列を生成せよ。

解法

No.599を先に解いてあるなら、それを使い色々いじってみよう。
g(S) := 文字列Sに対し条件を満たす分割の数
とすると、以下であることがわかる。

  • |S|=1ならg(S)=1
  • S=x + T + xと表現でき、
    • xがTの先頭・末尾と同じならg(S) = 2*g(T)
    • xがTの先頭・末尾と異なるならg(S) = g(T)+1

あとは再帰的に求めていけばよい。
異なる文字が必要な際はa~zを順につかっていこう。

string dfs(int N) {
	if(N==1) return "a";
	string S;
	if(N%2==0) {
		S=dfs(N/2);
		S=S[0]+S+S[0];
	}
	else {
		S=dfs(N-1);
		char c=S[0]+1;
		if(S[0]=='z') c='a';
		S=c+S+c;
	}
	return S;
}

void solve() {
	int N;
	cin>>N;
	cout<<dfs(N)<<endl;
	
}

まとめ

キリ番600回目でFAが取れて良かった。