問題はこちら
No.254 文字列の構成 - yukicoder
初見では解けずに解説を読んでしまったのだけど、見事な解説が書いてあって思わずなるほどとうなってしまった。
以下ではその解説の方針に従う
abab…babaと、a,bが交互に並ぶ文字列はaがn文字ある時、yukicoder No.111 あばばばば - メモでやったとおりn^2個の回文を含む
ということでまずN≧n^2となる最大のnを取り、abab…を作る。
NをN-n^2に更新して、以下同様に残った部分についてcdcd…,efef…とつなげていく
懸念点は２つあるがどちらも問題ない
・アルファベットが尽きないか
N-floor(√N)^2≦1+2floor(√N)なので5回以内に7以下になり、必ず12回以内に終わる
・文字長が10^5を超えないか
1+2floor(√N)個の文字を出力していくので
1回目で1+2*31622個以下
2回目で1+2*251個以下
この時点でNは503以下なので残りは503文字以下でたり、計7万字程度で足りる
ということでこんな感じでどうでしょう
int main(){ int n,m,s=0,i; scanf("%d",&n); while(n){ m=sqrt(n); n-=m*m; m=m*2-1; for(i=0;i<m;i++)putchar('a'+s*2+i%2); s++; } return 0; }
これを単純に潰して
n,s;main(i){for(scanf("%d",&n);n;s+=2)for(i=sqrt(n),n-=i*i,i*=2;--i;putchar(97+s+i%2));}
REにはならない。88B
