概要

\(1\) 以上 \(N\) 以下の整数のうち、十進法表記したときに隣り合う桁の差の絶対値の総和（「揺れ値」）がちょうど \(K\) であるものの個数を求める問題です。 \(N\) が最大で \(10^{18}\) と非常に大きいため、1つずつ確認するのではなく、桁DP（動的計画法）を用いて高速に数え上げる必要があります。

考察

素朴なアプローチ

\(1\) から \(N\) までのすべての整数について揺れ値を愚直に計算すると、時間計算量は \(O(N \log N)\) となり、最大 \(N = 10^{18}\) では到底実行時間制限に間に合いません（TLEとなります）。

桁数と揺れ値の性質

\(N \le 10^{18}\) ということは、考える整数の桁数 \(L\) は最大でも \(18\) 桁（\(10^{18}\) の場合は \(19\) 桁）です。 また、隣り合う桁の差の最大値は \(|9 - 0| = 9\) です。したがって、\(18\) 桁の数の揺れ値の最大値は \(9 \times 17 = 153\) となり、制約の \(K \le 153\) に合致します（\(19\) 桁の \(10^{18}\) でも最大 \(162\) 程度です）。 このように、桁数や揺れ値の取り得る範囲が非常に小さいことに注目します。

桁DPの導入

「\(N\) 以下の整数」を数え上げる典型的な手法として桁DPがあります。 桁DPでは、上の桁から順番に数字を決めていきます。その際、 - すでに \(N\) 未満であることが確定しているか（未満フラグ） という情報を持ちながら遷移するのが一般的です。

しかし、本問題では、「長さ \(l\)、先頭の数字が \(d\)、揺れ値が \(s\) であるような数列の個数」をあらかじめ求めておく（DPテーブルを事前計算する）ことで、桁DPの処理をシンプルかつ高速に実装することができます。

アルゴリズム

この問題は、以下の3つのステップで解くことができます。

ステップ1: DPテーブルの事前計算

まず、以下の動的計画法（DP）を定義します。 - dp[l][d][s] : 桁数が \(l\)、最上位桁（先頭の数字）が \(d\)、揺れ値が \(s\) であるような数字の並び（ただし、先頭に \(0\) が来てもよいものとする）の個数

初期状態: \(1\) 桁の数（\(l = 1\)）の場合、揺れ値は \(0\) です。 - dp[1][d][0] = 1 （\(0 \le d \le 9\)）

遷移: 長さ \(l-1\) の数の先頭に新しい数字 \(d\) を追加して長さ \(l\) の数を作ることを考えます。 新しく先頭になる数字を \(d\)、その次の数字を \(nd\) とすると、揺れ値は \(|d - nd|\) だけ増加します。 したがって、遷移式は以下のようになります。 $\( dp[l][d][s + |d - nd|] \leftarrow dp[l][d][s + |d - nd|] + dp[l-1][nd][s] \)\( この事前計算は \)N\( に依存しないため、最大桁数 \)L \approx 20\(、最大揺れ値 \)K \approx 180$ 程度まであらかじめ計算しておきます。

ステップ2: \(N\) 以下の整数の数え上げ

\(N\) を文字列として扱い、その桁数を \(L\) とします。 \(1\) 以上 \(N\) 以下の整数を、以下の3つのグループに分けて数え上げます。

1. 桁数が \(L\) 未満の数

   • 桁数 \(l\) が \(1\) から \(L-1\) までの数です。
   • 先頭の数字 \(d\) は \(1\) 以上 \(9\) 以下（先頭に \(0\) は使えない）である必要があります。
   • 求める個数は、\(\sum_{l=1}^{L-1} \sum_{d=1}^{9} dp[l][d][K]\) となります。

2. 桁数が \(L\) で、\(N\) 未満であることが確定した数

   • \(N\) と上から数桁が一致し、ある桁 \(p\)（\(0\)-indexed）で初めて \(N\) のその桁の数字よりも小さい数字を選んだ場合です。
   • \(p\) 桁目で選ぶ数字を \(d\) とします。
     • \(p = 0\)（最上位桁）のとき：\(1 \le d < N[0]\)
     • \(p > 0\) のとき：\(0 \le d < N[p]\)
   • このとき、上から \(p\) 桁目までに確定した揺れ値の累積を pref_sum、直前の桁の数字を prev_digit とします。
   • \(p\) 桁目の数字を \(d\) に決定したことで、新たに加わる揺れ値は \(|prev\_digit - d|\) です。
   • 残りの \(L - p\) 桁（\(p\) 桁目を含む）で必要な残りの揺れ値 rem は、 $\(rem = K - (pref\_sum + |prev\_digit - d|)\)$ となります。
   • この条件を満たす個数は、dp[L - p][d][rem] として足し合わせることができます。
   • この遷移を \(p = 0\) から \(L-1\) まで順に行い、各ステップの後に pref_sum を更新していきます。

3. \(N\) 自体

   • \(N\) 自体の揺れ値がちょうど \(K\) である場合、答えに \(1\) を加えます。

計算量

\(L\) を \(N\) の桁数（\(L \le 19\)）、\(D = 10\)（数字の種類数）、\(K\) を目標とする揺れ値（\(K \le 153\)）とします。

• 時間計算量: \(O(L \cdot D^2 \cdot K)\)

  • DPの事前計算において、桁数 \(L\)、現在の数字 \(D\)、次の数字 \(D\)、揺れ値 \(K\) の4重ループを回します。
  • 最大でも \(20 \times 10 \times 10 \times 180 \approx 3.6 \times 10^5\) 回のループであり、実行時間制限に対して一瞬（数ミリ秒）で終わります。
  • \(N\) 以下の数え上げパートは \(O(L \cdot D)\) であり、さらに高速です。

• 空間計算量: \(O(L \cdot D \cdot K)\)

  • DPテーブルのサイズは \(20 \times 10 \times 180 \approx 3.6 \times 10^4\) 個の整数を保持する程度であり、メモリ使用量は極めて小さく抑えられます。

実装のポイント

• 先頭の \(0\) の扱い:

  • DPテーブル dp[l][d][s] では、先頭の数字 \(d\) が \(0\) である場合も含めて遷移を計算しています。これにより、桁数が一致した後の「途中からの遷移（\(p > 0\)）」において、途中の桁に \(0\) が来るケースを正しく処理できます。
  • 一方で、数全体の先頭（最上位桁）に \(0\) が来ることは許されないため、数え上げの際には \(d\) の開始インデックスを \(1\) に制限する（start = 1 if p == 0 else 0）ことで、余分な \(0\) を排除しています。

• インデックスの範囲外参照:

  • rem（残りの必要な揺れ値）が負になったり、あらかじめ計算した MAX_K を超えたりした場合は、条件を満たす数が存在しないため、足し合わせる対象から除外する必要があります。

  • コード内では if 0 <= rem <= MAX_K: という条件式でこれを安全に防いでいます。

    ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N_str = data[0]
    K = int(data[1])

    L = len(N_str)
    MAX_L = max(20, L)
    MAX_K = max(180, K)

    # dp[l][d][s]: 長さ l、最初の桁 d、揺れ値 s である数列の個数
    dp = [[[0] * (MAX_K + 1) for _ in range(10)] for _ in range(MAX_L + 1)]

    for d in range(10):
        dp[1][d][0] = 1

    for l in range(2, MAX_L + 1):
        for d in range(10):
            for nd in range(10):
                diff = abs(d - nd)
                dp_l_d = dp[l][d]
                dp_prev_nd = dp[l - 1][nd]
                for s in range(MAX_K - diff + 1):
                    dp_l_d[s + diff] += dp_prev_nd[s]

    ans = 0

    # 1. 桁数が l < L の数
    for l in range(1, L):
        for d in range(1, 10):
            ans += dp[l][d][K]

    # 2. 桁数が L で、N 未満の数
    pref_sum = 0
    prev_digit = -1
    for p in range(L):
        limit = int(N_str[p])
        start = 1 if p == 0 else 0
        for d in range(start, limit):
            if p == 0:
                ans += dp[L][d][K]
            else:
                diff = abs(prev_digit - d)
                rem = K - (pref_sum + diff)
                if 0 <= rem <= MAX_K:
                    ans += dp[L - p][d][rem]

        if p > 0:
            pref_sum += abs(prev_digit - limit)
        prev_digit = limit

    # 3. N 自体
    if pref_sum == K:
        ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。