E - バランスチェック / Balance Check 解説 by admin
gemini-3.5-flash-thinking概要
この問題は、\(1\) 以上 \(N\) 以下の整数のうち、奇数番目の桁の数字の合計 \(S_{\mathrm{odd}}\) と、偶数番目の桁の数字の合計 \(S_{\mathrm{even}}\) の差の絶対値が \(D\) 以下であるものの個数を求める問題です。
\(N\) が最大で \(10^{15}\) と非常に大きいため、1つずつ条件を満たすか判定する素朴な方法では間に合いません。桁の上限 \(N\) を意識しながら、上の桁から順に数字を決めていく桁DP（動的計画法）を用いることで、高速に解くことができます。
考察
1. なぜ素朴な探索ではダメなのか？
\(1\) から \(N\) までのすべての整数をループで走査し、各整数の桁を調べて判定する場合、最悪で \(10^{15}\) 回のループが必要になります。一般的なコンピュータが1秒間に実行できる計算回数は \(10^8\) 回程度であるため、この方法（全探索）では実行時間制限（TLE）になってしまいます。
2. 桁DPによる解決
「\(N\) 以下の整数」という条件で数を数え上げる問題では、「上の桁から順番に数字を決定していく」というアプローチが非常に有効です。これが桁DPです。
しかし、この問題では以下の2点に注意する必要があります。
① リーディングゼロ（先頭の 0）の扱い
例えば、全体の桁数が \(5\) 桁のとき、数値 123 を 00123 として表現したとします。
もし先頭の 0 をそのままカウントしてしまうと、0（1番目・奇数）、0（2番目・偶数）、1（3番目・奇数）、2（4番目・偶数）、3（5番目・奇数）となり、1 が奇数番目の桁になってしまいます。
本来、123 の奇数番目の桁は 1 と 3、偶数番目は 2 です。
このように、「実際に数字が始まってから何番目の桁か」を正しく判定するために、「まだ数字が始まっていない（すべて 0）」状態と「すでに数字が始まっている」状態を区別する必要があります。
② 奇数番目か偶数番目かの状態
数字が始まっている場合、現在決めている桁が「奇数番目」か「偶数番目」かによって、その桁の数字を差に足す（\(S_{\mathrm{odd}}\) に加える）か、引く（\(S_{\mathrm{even}}\) に加える、すなわち差を引く）かが変わります。したがって、現在の桁の奇偶（パリティ）を状態として持つ必要があります。
③ 差の管理とオフセット
奇数番目の桁の和と偶数番目の桁の和の差 \(S_{\mathrm{odd}} - S_{\mathrm{even}}\) を DP の状態として持ちます。 \(N \le 10^{15}\) より、最大桁数は \(15\) 桁です。各桁の数字は最大で \(9\) なので、差の最大値は \(15 \times 9 = 135\)、最小値は \(-135\) となります。 配列のインデックスに負の数は使えないため、基準値（オフセット）として \(150\) 程度を足すことで、差を \([0, 300]\) の範囲の正の整数として安全に管理できます。
アルゴリズム
DP の状態定義
各桁を上から決めていく際、以下の状態を保持します。
is_less: 現在決めている値が、\(N\) 未満であることが確定しているか（0: 未確定,1: 確定）is_started: すでに \(1\) 以上の数字が現れて、数の表記が始まっているか（0: 始まっていない,1: 始まっている）parity: 次に決める桁が、開始から数えて何番目か（0: 奇数番目,1: 偶数番目）diff: 現在の「奇数番目の和 - 偶数番目の和」にオフセット（\(150\)）を加えた値
これらをまとめた状態 dp[is_less][is_started][parity][diff] を更新していきます。
状態遷移
上の桁から順に、次の桁の数字 \(d\)（\(0 \le d \le 9\)）を決定していきます。
まだ数字が始まっていない場合 (
is_started == 0)- \(d = 0\) のとき：
まだ数字は始まりません。状態は変化せず、
diffもそのままです。 - \(d > 0\) のとき：
ここから数字が始まります。これが「1番目（奇数番目）」の桁になるので、
diffに \(d\) を加算し、次の桁は「偶数番目 (parity = 1)」になります。またis_started = 1に変化します。
- \(d = 0\) のとき：
まだ数字は始まりません。状態は変化せず、
すでに数字が始まっている場合 (
is_started == 1)parity == 0（次の桁が奇数番目）のとき：diffに \(d\) を加算し、次の桁は「偶数番目 (parity = 1)」になります。parity == 1（次の桁が偶数番目）のとき：diffから \(d\) を減算し、次の桁は「奇数番目 (parity = 0)」になります。
最終的な集計
すべての桁を決定し終えたあと、以下の条件を満たす状態の総和が答えになります。
- is_started == 1（正の整数である）
- diff（オフセット適用後）が、許容される差 \(D\) の範囲内にある（すなわち、\(\mathrm{OFFSET} - D \le \mathrm{diff} \le \mathrm{OFFSET} + D\)）
計算量
時間計算量
- \(N\) の桁数を \(L\) とします（\(1 \le L \le 15\)）。
- DP の状態数は \(L \times 2 \times 2 \times 2 \times \mathrm{MAX\_DIFF}\) です。 ここで、\(\mathrm{MAX\_DIFF} = 301\) とします。
- 各状態からの遷移（次の桁の数字 \(d\) の選択肢）は最大 \(10\) 通りです。
- したがって、全体の計算量は \(O(L \times \mathrm{MAX\_DIFF} \times 10)\) となります。 \(L = 15\) のとき、計算回数は \(15 \times 8 \times 301 \times 10 \approx 3.6 \times 10^5\) 回となり、実行時間制限（通常2.0秒）に対して十分に高速（数ミリ秒）で動作します。
空間計算量
- DP テーブルは次の桁の計算をする際に「1つ前の桁の状態」だけが必要となるため、テーブルを使い回すことができます。
- したがって、必要な空間計算量は \(O(\mathrm{MAX\_DIFF})\) となり、メモリをほとんど消費しません。
実装のポイント
- 1次元配列へのエンコードによる高速化
Pythonなどの言語では、多次元リスト（多重の
list）へのアクセスはオーバーヘッドが大きくなります。正解コードでは、多次元の状態(is_less, is_started, parity, diff)を1つの整数にエンコードし、サイズがSTATE_SIZEの1次元配列として管理することで、劇的な高速化を図っています。
# 状態を1つのインデックスにマッピングする
state = ((is_less * 2 + is_started) * 2 + parity) * MAX_DIFF + diff
オフセットの適切な設定 差の最小値は \(-135\)、最大値は \(135\) です。余裕を持って
OFFSET = 150と設定し、MAX_DIFF = 301とすることで、すべての差の値を \(0\) 以上のインデックス（\([15, 285]\)）に収めています。ソースコード
import sys
def solve():
# Read all inputs from standard input
input_data = sys.stdin.read().split()
if not input_data:
return
N_str = input_data[0]
D = int(input_data[1])
L = len(N_str)
OFFSET = 150
MAX_DIFF = 301
STATE_SIZE = 2 * 2 * 2 * MAX_DIFF # 2408 states
# dp[state] where state is encoded as:
# ((is_less * 2 + is_started) * 2 + parity) * MAX_DIFF + diff
dp = [0] * STATE_SIZE
# Initial state: is_less=0, is_started=0, parity=0, diff=OFFSET
initial_state = ((0 * 2 + 0) * 2 + 0) * MAX_DIFF + OFFSET
dp[initial_state] = 1
for char in N_str:
limit = int(char)
next_dp = [0] * STATE_SIZE
for is_less in range(2):
for is_started in range(2):
for parity in range(2):
base_idx = ((is_less * 2 + is_started) * 2 + parity) * MAX_DIFF
for diff in range(MAX_DIFF):
count = dp[base_idx + diff]
if count == 0:
continue
max_d = 9 if is_less else limit
for d in range(max_d + 1):
next_is_less = is_less or (d < limit)
if is_started == 0:
if d == 0:
next_is_started = 0
next_parity = 0
next_diff = diff
else:
next_is_started = 1
next_parity = 1 # Next digit is the 2nd digit (even index)
next_diff = diff + d
else:
next_is_started = 1
if parity == 0: # Odd-positioned digit
next_diff = diff + d
next_parity = 1
else: # Even-positioned digit
next_diff = diff - d
next_parity = 0
next_state = ((next_is_less * 2 + next_is_started) * 2 + next_parity) * MAX_DIFF + next_diff
next_dp[next_state] += count
dp = next_dp
ans = 0
# Sum up valid states where is_started = 1 and |diff - OFFSET| <= D
for is_less in range(2):
for parity in range(2):
base_idx = ((is_less * 2 + 1) * 2 + parity) * MAX_DIFF
for diff in range(OFFSET - D, OFFSET + D + 1):
if 0 <= diff < MAX_DIFF:
ans += dp[base_idx + diff]
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-thinking によって生成されました。
投稿日時:
最終更新: