アプローチはすぐ思い浮かんだ。
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が取れて良かった。