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 桁の整数のうち、
であり、これらを合計すると 44322 個である。 10^9+1 の倍数かつ回文数であるような L 桁未満の整数のうち、
であり、これらを合計すると 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$%,$/
