D - Palindromic Number
解説
回文は、左右対称であることから、左半分を決めれば右半分を決めることができる。したがって、左半分として考えられるものの個数を考えれば良い。
以上の 桁の整数を考える。 桁の回文数の個数は
-
が偶数の場合: 左半分としてあり得るのは から
-
が奇数の場合: 左半分としてあり得るのは で、中心に がくるため、
よって、 桁の回文数の個数を とすると、
となる。(ただし、 は 桁とする。)
となる最小の を求めることで、 番目の回文数の桁数を求めることができる。また、そのような に対して、 番目の回文数は、 桁の回文数のうち、 番目のものとなる。
桁の回文数のうち、 番目の回文数は、
-
が偶数の場合: 左半分を として、右半分を左半分の逆順にしたものをくっつける
-
が奇数の場合: 左半分を として、右半分を左半分の逆順にしたものの最初の文字を取り除いたものをくっつける
となる。
提出コード
- Go
func nthPalindrome(k int, n int) string {
halfLength := (k + 1) / 2
start := pow(10, halfLength-1)
halfNumber := start + n - 1
halfStr := fmt.Sprintf("%d", halfNumber)
palindrome := halfStr
for i := k % 2; i < halfLength; i++ {
palindrome += string(halfStr[halfLength-1-i])
}
return palindrome
}
func main() {
n := readInt()
if n == 1 {
writeLine("0")
return
}
n--
x := 9
for i := 1; ; i++ {
if n < x {
writeLine(nthPalindrome(i, n))
return
}
n -= x
if i%2 == 0 {
x *= 10
}
}
}
- C++
string nthPalindrome(int k, ll n) {
ll halfLength = (k + 1) / 2;
ll start = pow(10, halfLength - 1);
ll halfNumber = start + n - 1;
string halfStr = to_string(halfNumber);
string palindrome = halfStr;
for (ll i = k % 2; i < halfLength; ++i) {
palindrome += halfStr[halfLength - 1 - i];
}
return palindrome;
}
int main() {
ll n; cin>>n;
if (n == 1) {
cout << 0 << endl;
return 0;
}
n--;
ll x = 9;
for (int i = 1;;i++) {
if (n - x <= 0) {
cout << nthPalindrome(i, n) << endl;
return 0;
}
n -= x;
if (i % 2 == 0) x *= 10;
}
}