概要

\(1\) 以上 \(N\) 以下の整数について、「左から奇数桁の和」と「左から偶数桁の和」の差の絶対値が \(D\) 以下になる個数を、桁 DP（Digit DP）で数え上げます。

考察

重要な気づき

整数 \(d_1d_2\ldots d_k\) に対して - \(S_{\mathrm{odd}} = d_1 + d_3 + \cdots\) - \(S_{\mathrm{even}} = d_2 + d_4 + \cdots\)

なので、差 [ S{\mathrm{odd}} - S{\mathrm{even}} ] は「左から見て奇数桁なら \(+d\)、偶数桁なら \(-d\) を足していく」累積和として扱えます。

つまり、左から順に桁を決めるとき、必要なのは「今どこまで決めたか」と「現在の差がいくつか」だけです。

素朴解が無理な理由

\(N \le 10^{15}\) なので最大で \(10^{15}\) 個を全探索することになり、桁和計算をしても到底間に合いません（TLE）。

どう解決するか

「桁を左から順に決める DP（桁 DP）」で、条件を満たす個数だけを効率よく数えます。

さらに「\(N\) 以下」という制約は、典型的に - \(N\) より短い桁数は自由に全列挙（ただし先頭ゼロなし） - \(N\) と同じ桁数は、上限に引っかかる（tight）かどうかを管理 で処理できます。

アルゴリズム

以下では差を [ \Delta = S{\mathrm{odd}} - S{\mathrm{even}} ] とします。

1. 桁数が \(L\) の整数をすべて数える（\(L < \mathrm{len}(N)\)）

DP を - \(dp[\Delta] =\) 「左から pos 桁目まで決めたとき、差が \(\Delta\) になる個数」 として進めます。

pos 桁目の数字を \(d\) とすると、 - pos が奇数（1,3,5,…）なら \(\Delta \leftarrow \Delta + d\) - pos が偶数（2,4,6,…）なら \(\Delta \leftarrow \Delta - d\)

先頭桁だけは \(d \in \{1,\dots,9\}\)、それ以外は \(d \in \{0,\dots,9\}\) です。

最後に \(|\Delta| \le D\) を満たす \(\Delta\) の個数を合計します。

2. \(N\) と同じ桁数で、\(N\) 以下を数える（tight / loose）

\(N\) の各桁を digs とし、状態を 2 種類に分けます。

• tight[Δ]：ここまでの prefix が ちょうど \(N\) と一致している場合の個数
• loose[Δ]：すでに prefix が \(N\) より 小さい ことが確定している場合の個数

pos 桁目で、上限は - tight からは \(0 \sim \text{limit}\)（ただし先頭は \(1 \sim \text{limit}\)） - loose からは \(0 \sim 9\)（ただし先頭は \(1 \sim 9\)） を選べます。

tight から digit \(d\) を選んで - \(d = \text{limit}\) なら次も tight - \(d < \text{limit}\) なら loose に移行 という通常の桁 DP の遷移をします。

最後に tight と loose の両方で \(|\Delta| \le D\) のものを足せば、「桁数が同じで \(N\) 以下」の答えになります。

3. 差 \(\Delta\) の配列添字化（offset）

\(\Delta\) は負になり得るので、配列にするために [ \text{index} = \Delta + \text{offset} ] とずらします（コードでは offset=200、size=401）。
最大でも桁数は \(16\) 程度で、差の絶対値は高々 \(9 \times 16 = 144\) なので、この範囲で十分安全です。

計算量

差 \(\Delta\) の取り得る範囲を \(R\)（ここでは \(401\)）とすると、各桁で 10 通りの遷移を行うため

• 時間計算量: \(O(\mathrm{len}(N) \cdot R \cdot 10)\)
  （さらに \(L<\mathrm{len}(N)\) の分もあるが、\(\mathrm{len}(N)\le 16\) なので同程度）
• 空間計算量: \(O(R)\)

実装のポイント

• 先頭桁だけ 0 を禁止：start_d = 1 if pos == 1 else 0 で管理します。

• 奇数桁は +、偶数桁は -：左から数えるので pos % 2 で sign を決めます。

• \(N\) 以下の管理は tight / loose：同じ長さで「上限を超えない」ことを正確に数える定番テクです。

• 負の差を配列にするため offset を使う：dp[offset] = 1 を初期状態（差 0）として開始します。

  ソースコード

import sys

def count_all_length(L: int, D: int, offset: int, size: int) -> int:
    dp = [0] * size
    dp[offset] = 1
    for pos in range(1, L + 1):
        ndp = [0] * size
        sign = 1 if (pos % 2 == 1) else -1
        start_d = 1 if pos == 1 else 0
        for idx, val in enumerate(dp):
            if val == 0:
                continue
            for d in range(start_d, 10):
                nidx = idx + sign * d
                if 0 <= nidx < size:
                    ndp[nidx] += val
        dp = ndp
    lo = max(0, offset - D)
    hi = min(size - 1, offset + D)
    return sum(dp[lo:hi + 1])

def count_upto_same_length(digs, D: int, offset: int, size: int) -> int:
    L = len(digs)
    tight = [0] * size
    loose = [0] * size
    tight[offset] = 1

    for pos in range(1, L + 1):
        limit = digs[pos - 1]
        sign = 1 if (pos % 2 == 1) else -1
        start_d = 1 if pos == 1 else 0

        ntight = [0] * size
        nloose = [0] * size

        # From tight state
        for idx, val in enumerate(tight):
            if val == 0:
                continue
            for d in range(start_d, limit + 1):
                nidx = idx + sign * d
                if 0 <= nidx < size:
                    if d == limit:
                        ntight[nidx] += val
                    else:
                        nloose[nidx] += val

        # From loose state
        for idx, val in enumerate(loose):
            if val == 0:
                continue
            for d in range(start_d, 10):
                nidx = idx + sign * d
                if 0 <= nidx < size:
                    nloose[nidx] += val

        tight, loose = ntight, nloose

    lo = max(0, offset - D)
    hi = min(size - 1, offset + D)
    return sum(tight[lo:hi + 1]) + sum(loose[lo:hi + 1])

def main():
    N_str = sys.stdin.readline().strip()
    D = int(sys.stdin.readline().strip())

    digs = list(map(int, N_str))
    LN = len(digs)

    offset = 200
    size = 401

    ans = 0
    for L in range(1, LN):
        ans += count_all_length(L, D, offset, size)
    ans += count_upto_same_length(digs, D, offset, size)

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。