yukicoder No.491 10^9+1と回文

問題はこちら
No.491 10^9+1と回文 - yukicoder

s<10^9に対して、s*(10^9+1)は、文字列としては「s,(いくつかの0),sを連結したもの」と一致する
これが回文数であることはsが回文数であることと同値
よって問題は「N/(10^9+1)以下の回文数の個数を求めよ」と読み替えられる。
対象となる数は高々9桁なので、5桁以下の数を元に回文数を構成し、それが求める範囲に入るかチェックすれば良い

#include <stdlib.h>
int main(){
	long n,len,ans=0;
	int i,j;
	char s[10];

	scanf("%ld",&n);
	n/=1000000001;
	for(i=1;i<100000;i++){
		sprintf(s,"%d",i);
		len=strlen(s);
		//1234->12344321
		for(j=len-1;j>=0;j--)s[len*2-1-j]=s[j];
		s[len*2]=0;
		if(strtoll(s,NULL,10)<=n)ans++;
		//1234->1234321
		for(j=len-2;j>=0;j--)s[len*2-2-j]=s[j];
		s[len*2-1]=0;
		if(strtoll(s,NULL,10)<=n)ans++;
	}
	printf("%d",ans);
	return 0;
}

ということで、これをざっくり書き換えてみる

long n,s;
//bを反転してaの後ろにくっつける関数。例えばf(1234,567)=1234765
f(a,b){return b?f(a*10+b%10,b/10):a;}
main(i){
	scanf("%ld",&n);
	//n/=1e9+1とすると、nがdoubleに変換されてしまい精度が足りない
	n/=1000000001;
	for(;i<1e5;i++){
		//iが5桁のとき、f(i,i)は10桁となりオーバーフローの可能性がある
		//nは9桁以下なのでこのケースは予め弾いてよい
		if(i<1e4&&f(i,i)<=n)s++;
		if(f(i,i/10)<=n)s++
	}
	printf("%d",s);
	//c11準拠になったのでreturn文を省略しても勝手に0を返してくれるようになったらしい
}

これをぎゅっとする

long n,x=1e9+1,s;
//sへの加算までfの中でやってしまう
f(a,b){!b?s+=a<=n:f(a*10+b%10,b/10);}
main(i){
	scanf("%ld",&n);
	for(n/=x;i<1e5;f(i++,i/10))i<1e4&&f(i,i);
	printf("%d",s);
}

135B

ちなみに上記プログラムは明らかにO(√N)だが、次のようにしてO(logN)で解くこともできる

//nの上半分を下半分に反転してコピーする。第2引数は次にコピーする桁
//f(1234567,10^6)=1234321、f(123456,10^5)=123321
f(n,t){return t>1?f(n%t/10,t/100)*10+n/t*(t+1):n;}

int main(){
	long n;
	int keta,temp,ans=0;

	scanf("%ld",&n);
	n/=1000000001;
	if(n==0){
		puts("0");
		return 0;
	}
	keta=log10(n)+1;
	ans=n/pow(10,keta/2)+pow(10,keta/2)-1;
	temp=pow(10,keta-1);
	if(f(n,temp)>n)ans--;
	printf("%d\n",ans);
}

次のような方法で計算している
１．N/1000000001をnとする。
２．nの桁数を求めketaとする（実際にはnが10べきのときに1ずれるが多分いい感じになっている）
３．keta桁未満の回文数の個数は
ketaが奇数のとき
ketaが偶数のときで与えられる
（ちょうどk桁の回文数の総数がであることからわかる）
４．簡単のためまずnが回文数である場合について考える
ちょうどketa桁の回文数でn以下のものの個数は、nの上半分の桁を見ればわかり、個
（例えばn=1234321なら、1234-1000+1=235個、n=12344321なら1234-1000+1=235個）
５．nが回文数でないときに同様に上半分だけを見て確認すると、例えばn=654321のときにはn=654456と同じ計算をすることになるので、余分な回文数が入ってしまわないか確認するためにf(n,*)とnの大小関係を見る

この方針で縮めると156Bとなり全然及ばない

long n,x=1+1e9;
f(n,t){x=t>1?f(n%t/10,t/100)*10-n/t*~t:n;}
main(m){
	scanf("%ld",&n);
	printf("%d",n=~(f(n,x=pow(10,m=log10(n/=x)))>n)+(m=pow(10,-~m/2))+1.*n/m);
}