【競技プログラミング】AtCoder Beginner Contest 363_D問題

# 問題
https://atcoder.jp/contests/abc363/tasks/abc363_d

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1

このコードは、指定された順序 $ N $ 番目の回文数を効率的に計算するアルゴリズムである。

---

## **解法手順**

### 1. 入力の調整
```python
N = int(input())
N -= 1
```
- 入力として与えられた $ N $ は 1-based index（1番目から数える）だが、計算を簡単にするために 0-based index（0番目から数える）に変換する。

---

### 2. 1桁の回文数の処理
```python
if N < 10:
    print(N)
    exit()
```
- $ N $ が 10 未満の場合、回文数はそのまま $ N $ に対応する（例: 0, 1, ..., 9）。
- この場合、計算は不要で、直接出力して終了する。

---

### 3. 回文数の範囲探索
```python
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 $ 桁。
- **範囲外の場合**:
  - $ 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`) における回文数の総個数を計算する。
そして、以下のようなロジックで動作する

1. 現在の桁 (`now`) における回文数が $N$ を超えるかどうかを判定。
   - 超えない場合：その分だけ $N$ を減らし、次の桁へ進む。
   - 超える場合：その桁内で $N$ 番目の回文を生成する。

このようにして、効率的に目的の回文を探索する。

---


### 4. 回文数の生成
#### 偶数桁の場合
```python
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) $
    - この式で、該当する前半部分を生成する。
- **後半部分生成**:
  - 前半部分を反転して後半部分として利用する。
- **結合**:
  - 前半と後半を結合して完全な回文数を作る。

#### 奇数桁の場合:
```python
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 $番目の回文数を求めよ。

### 解答：
1. 累積個数から確認
   - $ n = 15 $ は2桁（1～9で9個、10～18で2桁）。
   - インデックス = $ n - 9 = 6 $。

2. 桁内インデックスから生成
   - 左右対称な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 $番目の回文数が求められる。