SRM 317 Div1 Easy PalindromicNumbers

問題概要

ある数nが回文数であるとは、nの数字を逆順に並べて書いた数n'がnと等しくなるような数である。（例：121, 987656789）

lower以上upper以下の回文数の数を求めよ。ただしlower≦upper≦10^9である。

解法

10^9個の整数に対して回文判定をするとTLEになってしまう。（と思うけど）

回文を直接生成するようにすればO(sqrt(n))になるので、ナイーブにそれを実装すればよい。
奇数桁、偶数桁の回文数にわけてそれぞれを生成する。

ソースコード

	int countPalNums(int lower, int upper) 
	{
		pw[0]=1;
		rep(i,9)pw[i+1]=pw[i]*10;
		
		return calc(upper)-calc(lower-1);
	}
	int calc(int n)
	{
		int cnt=0;
		//11
		for(int d=1;;d++)
		{
			int t=pw[d-1];
			for(;t<pw[d];t++)
			{
				if(t*pw[d]+rev(t)>n)goto OUT1;
				cnt++;
			}
		}
		OUT1:;
		//121
		for(int d=1;;d++)
		{
			int t=pw[d-1];
			for(;t<pw[d];t++)
			{
				if(t*pw[d-1]+rev(t/10)>n)goto OUT2;
				cnt++;
			}
		}
		OUT2:;
		return cnt;
	}
	int rev(int n)
	{
		int d[10],nd;
		
		for(nd=0;n;n/=10)d[nd++]=n%10;
		rep(i,nd)n*=10,n+=d[i];
		
		return n;
	}

System Test

Passed.大きいケースで6msほど。