概要

\(1\) 以上 \(N\) 以下の正の整数のうち、奇数番目の桁の和と偶数番目の桁の和の差の絶対値が \(D\) 以下であるものの個数を求める問題です。桁DPで解きます。

考察

素朴なアプローチの問題点

\(N\) が最大 \(10^{15}\) なので、\(1\) から \(N\) まで全ての整数を一つずつ調べると \(O(N)\) かかり、到底間に合いません。

重要な気づき

「\(N\) 以下の正の整数で、桁に関する条件を満たすものを数える」という問題は、桁DP（Digit DP） の典型パターンです。上の桁から一桁ずつ決めていき、以下の情報を状態として管理します：

• 現在見ている桁の位置
• \(S_{\mathrm{odd}} - S_{\mathrm{even}}\) の現在の値（差を追跡）
• \(N\) の対応する桁と同じ値まで使っているか（tight制約）
• 数が始まっているか（先頭のゼロを無視するため）
• 次に置く桁が奇数番目か偶数番目か（パリティ）

差の追跡

\(S_{\mathrm{odd}}\) と \(S_{\mathrm{even}}\) を別々に管理する代わりに、差 \(\mathrm{diff} = S_{\mathrm{odd}} - S_{\mathrm{even}}\) だけを追跡すれば十分です。最終的に \(|\mathrm{diff}| \leq D\) を判定すればよいからです。

\(N\) は最大16桁なので、奇数番目は最大8桁、偶数番目も最大8桁です。よって \(\mathrm{diff}\) の範囲は \([-72, 72]\) に収まります。

アルゴリズム

桁DP を再帰（メモ化）で実装します。

1. \(N\) を十進数の桁のリストに変換する。
2. 再帰関数 dp(pos, diff, tight, started, parity) を定義する：
   • pos：現在決めようとしている桁の位置（\(N\) の桁列でのインデックス）
   • diff：これまでに確定した \(S_{\mathrm{odd}} - S_{\mathrm{even}}\) の値
   • tight：\(N\) の上界に張り付いているか（True なら次の桁は \(N\) の該当桁以下に制限）
   • started：まだ有効な桁が始まっていないか（先頭ゼロの処理）
   • parity：次に置く桁が奇数番目（0）か偶数番目（1）か
3. 各桁位置で \(0\) から上限まで全ての数字を試し、条件に応じて diff を更新する：
   • 奇数番目の桁なら diff += d
   • 偶数番目の桁なら diff -= d
4. 枝刈り：残りの桁数を \(r\) としたとき、\(|\mathrm{diff}| - 9r > D\) なら、どう頑張っても条件を満たせないのでスキップ。
5. 全桁を決め終わったら（pos == n）、started かつ \(|\mathrm{diff}| \leq D\) なら 1 を返す。

計算量

• 時間計算量: \(O(n \times W \times 2 \times 2 \times 2 \times 10)\)
  • \(n\)：桁数（最大16）
  • \(W\)：diffの取りうる値の数（約145）
  • \(2 \times 2 \times 2\)：tight, started, parity の組み合わせ
  • \(10\)：各位置で試す数字の個数
  • 合計で約 \(16 \times 145 \times 8 \times 10 \approx 185{,}600\) 程度の状態×遷移
• 空間計算量: \(O(n \times W \times 2 \times 2 \times 2)\)（メモ化テーブル）

実装のポイント

• 先頭ゼロの処理：started フラグで管理。先頭ゼロの間はまだ桁が始まっていないとみなし、diff や parity を更新しない。非ゼロの数字が初めて現れたとき、それは必ず奇数番目（1番目）の桁になる。

• パリティの管理：数の「何番目の桁か」は、数自体の長さによって決まるため、先頭ゼロを含む全体の桁位置ではなく、実際に数が始まってからのカウントで管理する必要がある。

• 枝刈り：残り桁で挽回不可能な状態を早期に除外することで高速化。

• lru_cacheの利用：Python では functools.lru_cache を使うことで、メモ化再帰を簡潔に実装できる。

  ソースコード

import sys
from functools import lru_cache

def solve():
    N = int(input())
    D = int(input())
    
    digits = list(map(int, str(N)))
    n = len(digits)
    
    # Digit DP
    # State: position, diff (S_odd - S_even), tight, started
    # diff can range from -9*8 = -72 to 9*8 = 72 for up to 16 digits
    # Actually for 16 digits: max 8 odd positions * 9 = 72, similarly even
    # diff range: -9*8 to 9*8 = -72 to 72
    # But we need to handle up to 16 digits (10^15 has 16 digits)
    # Max odd positions: 8, max even positions: 8 -> diff in [-72, 72]
    
    # We'll use memoization with offset for diff
    # diff = S_odd - S_even
    # At position i (0-indexed), if i is even (0,2,4,...) it's odd-numbered (1st,3rd,...) -> add to S_odd
    # if i is odd (1,3,5,...) it's even-numbered (2nd,4th,...) -> add to S_even
    # But position indexing depends on the actual number's length when started
    # 
    # Actually, we need to track the actual digit position within the number being formed.
    # When the number hasn't started yet (leading zeros), we don't count those positions.
    # So we need to track how many actual digits have been placed.
    
    # State: pos in the template, number of actual digits placed so far, diff, tight
    # number of actual digits: 0 to 16
    # diff: -72 to 72 -> offset by 72, range 0 to 144
    
    # Actually, let's think differently. We track pos, tight, started, and diff.
    # When we place a non-zero digit and haven't started, we start. The first actual digit is at odd position (1st).
    # After that, each subsequent digit alternates.
    # Instead of tracking num_digits, we can track the parity of the next digit position.
    # parity=0 means next digit goes to odd position (adds to diff), parity=1 means even position (subtracts from diff)
    
    OFFSET = 130  # enough offset
    MAX_DIFF = 260
    
    @lru_cache(maxsize=None)
    def dp(pos, diff, tight, started, parity):
        # parity: 0 = next actual digit is odd-positioned, 1 = even-positioned
        if pos == n:
            if not started:
                return 0
            return 1 if abs(diff) <= D else 0
        
        limit = digits[pos] if tight else 9
        result = 0
        
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            
            if not started and d == 0:
                # Still not started
                result += dp(pos + 1, 0, new_tight, False, 0)
            else:
                # Place digit d
                new_started = True
                if not started:
                    # First digit, it's at odd position (parity=0)
                    new_parity = 1  # next will be even position
                    new_diff = diff + d  # odd position: add
                else:
                    if parity == 0:
                        # odd position: add
                        new_diff = diff + d
                    else:
                        # even position: subtract
                        new_diff = diff - d
                    new_parity = 1 - parity
                
                # Pruning: remaining positions
                remaining = n - pos - 1
                # max change possible is 9 * remaining
                # if diff is already too far from 0, prune
                if abs(new_diff) - 9 * remaining > D:
                    continue
                
                result += dp(pos + 1, new_diff, new_tight, new_started, new_parity)
        
        return result
    
    print(dp(0, 0, True, False, 0))

solve()

---

この解説は claude4.6opus-thinking によって生成されました。