問題
既存投稿一覧ページへのリンク
解法手順1
このコードは、指定された順序 $ N $ 番目の回文数を効率的に計算するアルゴリズムである。
解法手順
1. 入力の調整
N = int(input())
N -= 1
- 入力として与えられた $ N $ は 1-based index（1番目から数える）だが、計算を簡単にするために 0-based index（0番目から数える）に変換する。
2. 1桁の回文数の処理
if N < 10:
print(N)
exit()
- $ N $ が 10 未満の場合、回文数はそのまま $ N $ に対応する（例: 0, 1, ..., 9）。
- この場合、計算は不要で、直接出力して終了する。
3. 回文数の範囲探索
now = 0
while N:
if N <= 10**(now//2) * 9:
...
break
N -= 10**(now//2) * 9
now += 1
-
nowの役割: 現在の回文数の「桁数」を管理する。 -
探索範囲の計算
- $ \text{10}^{\lfloor \text{now}/2 \rfloor} \times 9 $ は、
now桁の回文数が何個あるかを表す。- 奇数桁の場合: 前半部分は $ \lceil \text{now}/2 \rceil $ 桁。
- 偶数桁の場合: 前半部分は $ \text{now}/2 $ 桁。
- $ \text{10}^{\lfloor \text{now}/2 \rfloor} \times 9 $ は、
-
範囲外の場合:
- $ N $ が現在の桁数の回文数の個数より大きい場合、その分を引き算して次の桁へ進む。
-
範囲内の場合:
- $ N $ が現在の桁数内に収まる場合、その桁で回文数を生成する。
回文数の桁数と個数の関係
回文数は、左右対称な形を持つ数である。
そのため、桁数に応じて生成可能な回文数の個数には規則性がある。
1. 回文数の構造
-
偶数桁の回文数の場合：
- 回文数は「前半部分」を反転して後半部分を作る。
- 例：
123321→ 前半部分は123。 - 桁数が
2nの場合、前半部分はn桁の数字になる。
-
奇数桁の回文数の場合：
- 回文数は「前半部分」に中央の数字を挿入して作る。
- 例：
12321→ 前半部分は12、中央が3。 - 桁数が
2n+1の場合、前半部分はn+1桁の数字になる。
2. 各桁数で生成できる回文数の個数
- 前半部分が何通りあるかを考えると、回文数全体の個数がわかる。
- 前半部分は通常の整数（0を含まない）の範囲で生成される。
偶数桁の場合
- 桁数が
2nの回文数：- 前半部分は $ 10^{n-1}$ ～ $10^n - 1 $ の範囲。
- 個数：$ 10^{n} - 10^{n-1} = 9 \times 10^{n-1} $。
奇数桁の場合
- 桁数が
2n+1の回文数：- 前半部分も同様に $10^{n-1}$ ～ $10^n - 1$ の範囲。
- 個数：$ 9 \times 10^{n-1} $。
3. 一般化
各桁で生成できる回文数の個数を統一的に表すと、次のようになる
$$
\text{個数} = 9 \times 10^{\lfloor \text{now}/2 \rfloor}
$$
ここで：
- $\text{now}$ は現在探索している桁数。
- $\lfloor \text{now}/2 \rfloor$ は「回文の前半部分」の桁数を表す。
コード内での役割
コード内では、この式を使って現在の桁 (now) における回文数の総個数を計算する。
そして、以下のようなロジックで動作する
- 現在の桁 (
now) における回文数が $N$ を超えるかどうかを判定。- 超えない場合：その分だけ $N$ を減らし、次の桁へ進む。
- 超える場合：その桁内で $N$ 番目の回文を生成する。
このようにして、効率的に目的の回文を探索する。
4. 回文数の生成
偶数桁の場合
a = str(10**math.ceil(now/2) + (N-1))
b = a[:(len(a)//2)]
b = a[::-1]
a = a + b[1:]
print(a)
-
前半部分生成
- $ a = \text{10}^{\lceil \text{now}/2 \rceil} + (N-1) $
- この式で、該当する前半部分を生成する。
- $ a = \text{10}^{\lceil \text{now}/2 \rceil} + (N-1) $
-
後半部分生成:
- 前半部分を反転して後半部分として利用する。
-
結合:
- 前半と後半を結合して完全な回文数を作る。
奇数桁の場合:
a = str(10**math.ceil(now/2) + (N-1))
a = a[1:]
a = str(int(a[0]) + 1) + a[1:]
print(a + a[::-1])
- 奇数桁では、中央の数字が重複しないように調整が必要。
-
中央調整
- 中央部分（最初の数字）をインクリメントして調整。
-
結合:
- 前半と反転した後半を結合して回文数を作る。
回文数
正の整数 $ n $ が与えられたとき、$ n $番目の回文数を求めよ。
なお、回文数は十進法で表記し、1桁、2桁、3桁...と小さい順に並べるものとする。
解答
1. 回文数の分類
回文数は桁数に基づいて次のように分類できる
- 1桁の回文数: $ 1, 2, ..., 9 $ （計 $ 9 $ 個）
- 2桁の回文数: $ 11, 22, ..., 99 $ （計 $ 9 $ 個）
- 3桁の回文数: $ 101, 111, ..., 999 $ （計 $ 90 $ 個）
-
4桁の回文数: $ 1001, 1111, ..., 9999 $ （計 $ 90 $ 個）
一般に： - 奇数桁の場合：中央の数字を含む左右対称な構造。
- 偶数桁の場合：完全に左右対称な構造。
2. 累積個数から桁数を特定
まず、$ n $番目の回文数がどの桁数に属するかを特定する。
累積的な回文数の個数を計算する
- $ 1 $桁まで：$ 9 $
- $ 2 $桁まで：$ 9 + 9 = 18 $
- $ 3 $桁まで：$ 18 + 90 = 108 $
- $ k $桁まで：一般式で表すと、
- 奇数桁の場合：$ 9 \times 10^{\frac{k-1}{2}} $
- 偶数桁の場合：$ 9 \times 10^{\frac{k}{2} - 1} $
累積個数を比較して、$ n $番目が属する桁数を見つける。
3. 桁内でのインデックスを計算
次に、該当する桁内での位置（インデックス）を求める
$\text{インデックス} = n - (\text{前までの累積個数})$
4. 回文生成
該当する桁内でインデックスに応じた回文数を生成する
- 奇数桁の場合：
- 左半分（中央を含む）の数字を決定し、それを反転して右側を生成。
- 左半分は $ m = (\text{最小値}) + (\text{インデックス} - 1) $ として計算。
- 回文は次の形で表される。 $ P = L + R $ （ここで $ L $ は左半分、$ R $ はその反転）
- 偶数桁の場合：
- 左半分だけで構成される。
- 同様に左半分を決定し、それを反転して右側を生成。
具体例
問題
$ n = 15 $番目の回文数を求めよ。
解答：
-
累積個数から確認
- $ n = 15 $ は2桁（1～9で9個、10～18で2桁）。
- インデックス = $ n - 9 = 6 $。
-
桁内インデックスから生成
- 左右対称な2桁なので、左側は「6」。
- 回文は「66」。
答え：66
一般式による解法
以下は、奇数・偶数桁の場合に対応した一般式となる
奇数桁の場合（例：3, 5, ... 桁）:
$P(n) = L + R$
ここで
- $ L = (\text{左半分}) = (\text{最小値}) + (\text{インデックス} - 1) $
- $ R = (\text{反転した左半分})[中央以外] $
偶数桁の場合（例：2, 4, ... 桁）:
$P(n) = L + R$
ここで
- $ L = (\text{左半分}) = (\text{最小値}) + (\text{インデックス} - 1) $
- $ R = (\text{反転した左半分})[全体]$
この方法で任意の $ n $番目の回文数が求められる。