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

37.50.48

%20 の ブログ

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

この記事は、yukicoder No.491 10^9+1と回文 の解説です。

N の桁数を L とする。
10^9+1 の倍数かつ回文数であるような 1 以上 N 以下の整数のうち最大のものを M とする。
M が求まれば、最終的な答えは簡単に求まる。

例えば、M=543212345543212345 (これを 54321... と表記する) の場合について考える。

10^9+1 の倍数かつ回文数であるような L 桁の整数のうち、

  • 5432x... のものは 54320... から 54321... までで 2 個
  • 上記以外で、543xx... のものは 54300... から 54319... までで 20 個
  • 上記以外で、54xxx... のものは 54000... から 54299... までで 300 個
  • 上記以外で、5xxxx... のものは 50000... から 53999... までで 4000 個
  • 上記以外で、xxxxx... のものは 10000... から 49999... までで 40000 個

であり、これらを合計すると 44322 個である。

10^9+1 の倍数かつ回文数であるような L 桁未満の整数のうち、

  • 10 桁未満のものは 0 個
  • 10 桁または 11 桁のものは 1... から 9... までで 9 個
  • 12 桁または 13 桁のものは 10... から 99... までで 90 個
  • 14 桁または 15 桁のものは 100... から 999... までで 900 個
  • 16 桁または 17 桁のものは 1000... から 9999... までで 9000 個

であり、これらを合計すると 19998 個である。

以上より、求める個数は 44322+19998=64320 である。

M を求めるには、M 候補を最初は (L 桁の) 0 にしておいて、上位の桁から順に floor((L-8)/2) 桁について、回文数になるように M を変更しつつ、M≦N を満たすように決めていけばよい。

10^9+1 の倍数かつ回文数であるような L 桁の整数の個数は、M の最上位の桁の値から 1 を引いたうえで、M の上位 floor((L-8)/2) 桁の値に 1 を足したものである。

10^9+1 の倍数かつ回文数であるような L 桁未満の整数の個数は、9*10^floor((i-10)/2) (i=10, 11, ..., L-1) の総和である。

これらの和が求める個数である。M が L 桁にならない場合、L 桁未満の数についてだけ考えればよい。

コード

$"='';
@M=(0)x(@N=<>=~/./g);
for($k=0;2*$k<=@N-10;++$k){
	@M[$k,$k+9,$#N-$k,@N-10-$k]=($|?9:$N[$k])x4;
	@M[$k,$k+9,$#N-$k,@N-10-$k]=($N[$k]-1)x4,$|=1if"@M">"@N"
}
$%="@M[0..(@N-10)/2]"+1if$M[0]--;
$%+=9*10**($_>>1)for 0..@N-11;
print$%,$/