yukicoder 254 文字列の構成

2015/07/25 (Sat) yukicoder 文字列

問題

問題文

方針

ababab... と繰り返す長さ $n$ の文字列に含まれる回文の数を $f(n)$ とおく．

$n$ が偶数のときは

  • a, b のパターンが $n$ 個
  • aba, bab のパターンが $n-2$ 個
  • ababa, babab のパターンが $n-4$ 個
  • …

となるので，合わせて $C(n/2,2) \times 2$ 個の回文が含まれる． ここで $C(i,j)$ は組み合わせ係数．

$n$ が奇数のときは，末尾の文字を使わないとき再帰的に $f(n-1)$ 個， 使うとき $(n+1)/2$ 個作れる．あわせて $f(n-1)+(n+1)/2$ 個である．

$f(k) \leq N$ となる最大の $k$ を求め，$N$ から引くということを，$N=0$ となるまで繰り返す． 毎回の ababa... を答えの末尾に足していく．ループのたびに cdcdc..., efefe... と変えていき， 異なる区間をまたぐような回文ができないようにする．

実装

int g(int n){
    return (1+n)*n/2;
}

int f(int n){
    if(n&1) return (n+1)/2 + f(n-1);
    else return g(n/2)*2;
}

int main(){
    ll n;
    cin >> n;
    ll rem = n, step = 0;
    string ans;
    while(rem){
        ll l = 0, r = 100010;
        while(l+1 < r){
            ll m = (l+r)/2;
            ll x = f(m);
            if(x <= rem) l = m;
            else r = m;
            rep(i,1000000);
        }
        rep(i,l) ans += char('a'+step*2+i%2);
        step++;
        rem -= f(l);
    }
    cout << ans << endl;
}