AtCoder

ABC363 D問題(Palindromic Number)を解く

AtCoder_ABC363_D

AtCoder が提供しているABC(AtCoder Beginner Contest)363 D問題をC++とPythonで解いてみました。ABC363は、2024年7月20日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Palindromic Number(Difficulty : 975)

問題の詳細は、リンク先をご覧ください。

ABC363 D問題 Palindromic Number

ある桁数の数字のうち、回文数がいくつあるかを考察します。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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA