読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.254 文字列の構成

問題はこちら
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…とつなげていく
懸念点は2つあるがどちらも問題ない
・アルファベットが尽きないか
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