AtCoder が提供しているABC（AtCoder Beginner Contest）363 D問題をC++とPythonで解いてみました。ABC363は、2024年7月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Palindromic Number（Difficulty : 975）
問題の詳細は、リンク先をご覧ください。
ある桁数の数字のうち、回文数がいくつあるかを考察します。AtCoder Problems による Difficulty は 975 でした。
解答案
1桁の回文数は、以下の10個あります。
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
2桁の回文数は、以下の9個あります。
11, 22, 33, 44, 55, 66, 77, 88,99
3桁の回文数は、以下の90個あります。先頭の桁が9種類、それぞれの2番目の桁が10種類です。
101, 111, … , 191, 202, 212, … , 292, 303, …, 393, 404, … , 909, …, 999
4桁の回文数は、以下の90個あります。先頭の桁と2番目の桁が10から99までの90種類です。
1001, 1111, 1221, 1331, …., 9889, 9999
5桁の回文数は、3桁の回文数と同じ理屈で900個あります。
6桁の回文数は、4桁の回文数と同じ理屈で900個あります。
7桁以降も同じで、桁数を $k$ とすると、$9 \times 10^{(k-1)/2}$ 個となります。
$N$ の最大値は、$10^{18}$ と大きいですが、入力例3でこの最大値について出力が提示されています。結果的に35桁の整数の左半分は18桁に収まっています。64ビット整数で演算できる範囲です。
C++ プログラム例（ABC363D）
2桁までの回文数である $N \leqq 19$ の範囲は個別処理します。
while 文で奇数桁と偶数桁について処理します。出力の左半分は同じです。奇数桁の場合は、折り返しの右半分の桁数が1桁少なく、偶数桁の場合は、左半分をそのまま折り返します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
ull n;
cin >> n;
if (n <= 10) {
cout << n - 1 << endl;
return 0;
} else if (n <= 19) {
cout << (n - 10) * 11 << endl;
return 0;
}
n -= 19;
ull p = 90;
while (1) {
if (n <= p) {
string t1 = to_string(n - 1 + p / 9);
string t2 = t1;
reverse(t2.begin(), t2.end());
cout << t1 + t2.substr(1) << endl;
return 0;
}
n -= p;
if (n <= p) {
string t1 = to_string(n - 1 + p / 9);
string t2 = t1;
reverse(t2.begin(), t2.end());
cout << t1 + t2 << endl;
return 0;
}
n -= p;
p *= 10;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC363D）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 363 D"""
import sys
n = int(input())
if n <= 10:
print(n - 1)
sys.exit()
elif n <= 19:
print((n - 10) * 11)
sys.exit()
n -= 19
p = 90
while True:
if n <= p:
t1 = str(n - 1 + p // 9)
t2 = t1[::-1]
print(t1 + t2[1:])
sys.exit()
n -= p
if n <= p:
t1 = str(n - 1 + p // 9)
t2 = t1[::-1]
print(t1 + t2)
sys.exit()
n -= p
p *= 10こちらも「AC」と判定されました。
最後に
コンテストでは、E問題を解くことができましたが、D問題は時間切れでした。解く速さも重要になってきました。
引き続き ABC の問題を紹介していきます。
