E - スムーズな山道 / Smooth Mountain Path Editorial by admin
gemini-3.5-flash-thinking(計算量の説明が誤り)概要
この問題は、隣り合う桁の差（段差）が右に進むにつれて単調非減少（等しいか大きくなる）であるような、指定された範囲 \([L, R]\) 内の整数の個数を求める問題です。
制約として \(L, R\) の桁数が最大で \(5000\) 桁と非常に大きいため、通常の整数型で扱うことはできません。数え上げの典型手法である桁DP（Digit DP）を用いることで、高速かつ正確に解くことができます。
考察
1. 範囲 \([L, R]\) の言い換え
まずは、範囲 \([L, R]\) 内の条件を満たす整数の個数を直接求めるのではなく、定番の累積和の考え方を適用します。 \(f(X)\) を「\(1\) 以上 \(X\) 以下のスムーズな山道の個数」と定義すると、求める答えは以下のように表せます。
\[\text{Ans} = f(R) - f(L) + (L \text{ がスムーズな山道なら } 1, \text{ そうでなければ } 0)\]
これにより、任意の正の整数 \(N\) に対して \(f(N)\) を高速に求める問題へと帰着されます。
2. スムーズな山道の判定に必要な情報
ある数がスムーズな山道であるかを左から順に（上の桁から順に）決めていくことを考えます。 第 \(i\) 桁目の数字を \(d_i\) としたとき、次の第 \(i+1\) 桁目の数字 \(d_{i+1}\) を決める際に必要な情報は以下の2点のみです。
- 直前の桁の数字: \(d_i\) （次の段差 \(|d_i - d_{i+1}|\) を計算するため）
- 直前の段差: \(diff = |d_{i-1} - d_i|\) （次の段差がこれ以上である必要があるため）
※ただし、まだ段差が1つも存在しない状態（1桁目までしか決まっていない状態）では、次の段差に対する制限はありません。この「制限なし」の状態を \(diff = 10\) という特別な値で表すことにします。
このように、状態を「（現在の数字, 直前の段差）」のペアで管理すれば、それ以前の具体的な数字の並び方は気にする必要がありません。
アルゴリズム
1. 後ろからの動的計画法（Suffix DP）の事前計算
\(f(N)\) を求める際、「ある桁まで \(N\) と一致し、次の桁で \(N\) より小さい数字を選び、それ以降の桁は自由に決める」という遷移を行います。 この「残り \(rem\) 桁を自由に決める方法の数」は、上限 \(N\) の値に依存せず、「残り桁数」「現在の数字」「直前の段差」のみで決まります。これを事前に DP で計算しておきます。
DPテーブルの定義
suf_all[rem][d * 11 + diff]: 残り \(rem\) 桁で、現在の数字が \(d\)、課されている最小の段差が \(diff\) であるとき、それ以降の桁を適切に埋めてスムーズな山道を作る方法の数。- 状態数： \(5000 \times 10 \times 11 \approx 5.5 \times 10^5\)
遷移
残り \(rem\) 桁から残り \(rem+1\) 桁への遷移を考えます。次に置く数字を \(nx \in \{0, \ldots, 9\}\) とすると、新たな段差は \(nd = |d - nx|\) となります。 スムーズな山道の条件を満たすためには \(nd \geq diff\) である必要があります。
\[\text{suf\_all}[rem][d \times 11 + diff] = \sum_{\substack{0 \leq nx \leq 9 \\ |d - nx| \geq diff}} \text{suf\_all}[rem-1][nx \times 11 + |d - nx|] \pmod{10^9+7}\]
初期値は \(rem = 0\) のとき、これ以上桁を埋める必要がないため、すべての状態に対して 1 とします。
2. \(f(N)\) の数え上げ
事前計算した suf_all を用いて、 \(N\) 以下のスムーズな山道の個数を以下の3つのグループに分けて数え上げます。
① 桁数が \(N\) の桁数 \(M\) 未満の数
例えば \(N = 352\) （3桁）のとき、1桁および2桁の数をすべて数え上げます。 先頭の桁 \(d \in \{1, \ldots, 9\}\) を決めると、残りの桁数は自由に決められます（最初の段差の制約はないので \(diff = 10\)）。
\[\sum_{len=1}^{M-1} \sum_{d=1}^{9} \text{suf\_all}[len-1][d \times 11 + 10]\]
② 桁数が \(M\) で、 \(N\) 未満の数
左から順に \(N\) と一致する桁を伸ばしていき、途中の第 \(i\) 桁目（0-indexed）で \(N[i]\) 未満の数字 \(d\) を選ぶ場合を考えます。 - \(i = 0\)（先頭桁）のとき： \(d \in \{1, \ldots, N[0]-1\}\) を選びます。残りの桁数は \(M-1\) で、制約は \(diff = 10\)。 - \(i = 1\) のとき： \(d \in \{0, \ldots, N[1]-1\}\) を選びます。直前の段差は \(diff = |N[0] - d|\) となり、残りの桁数は \(M-2\)。 - \(i \geq 2\) のとき： これまでの接頭辞 \(N[0 \ldots i-1]\) がすでにスムーズな山道の条件を満たしている場合のみ遷移可能です。 \(d \in \{0, \ldots, N[i]-1\}\) のうち、新しい段差 \(diff = |N[i-1] - d|\) が直前の段差 \(|N[i-1] - N[i-2]|\) 以上になるものを選びます。残りの桁数は \(M - i - 1\)。
条件を満たす各ケースについて、対応する suf_all の値を足し合わせます。
③ \(N\) 自体
\(N\) 自体がスムーズな山道の条件を満たしている場合、答えに \(1\) を加算します。
計算量
- 時間計算量: \(O(M \cdot D^2)\)
- ここで \(M\) は最大桁数（\(5000\)）、\(D\) は基数（\(10\)）です。
- 事前計算の DP の遷移は、各状態（\(M \times 10 \times 11\) 通り）に対して次の数字 \(nx\) の \(10\) 通りを試すため、全体で \(5000 \times 110 \times 10 \approx 5.5 \times 10^6\) 回のループとなり、制限時間内に余裕で間に合います。
- \(f(N)\) の計算は、各桁 \(i\) について高々 \(10\) 回の遷移を見るため \(O(M \cdot D)\) であり、非常に高速です。
- 空間計算量: \(O(M \cdot D^2)\)
- DPテーブル
suf_allのサイズは \(5000 \times 110\) 個の整数であり、メモリ制限に対しても極めて軽量です。
- DPテーブル
実装のポイント
状態のエンコード: 2次元の情報を1次元に圧縮するため、
d * 11 + diffというインデックスを用いています。これにより、多次元配列へのアクセスを高速化し、Pythonにおけるオーバーヘッドを削減しています。遷移の事前計算:
valid_nx[d][diff]に「数字 \(d\) の次に置くことができ、かつ差が \(diff\) 以上になるような次の数字 \(nx\) とその段差のリスト」をあらかじめ用意しておくことで、DPの二重ループ内での無駄な条件分岐を省き、定数倍の高速化を図っています。ソースコード
import sys
def main():
input = sys.stdin.read
data = input().split()
if not data:
return
L_str = data[0]
R_str = data[1]
MOD = 10**9 + 7
M = len(R_str)
# valid_nx[d][diff] = list of (nx, nd) where nd = abs(d - nx) and nd >= diff
# diff = 10 represents -1 (no constraint)
valid_nx = [[[] for _ in range(11)] for _ in range(10)]
for d in range(10):
for diff in range(11):
if diff == 10:
valid_nx[d][diff] = [(nx, abs(d - nx)) for nx in range(10)]
else:
valid_nx[d][diff] = [(nx, abs(d - nx)) for nx in range(10) if abs(d - nx) >= diff]
# DP suffix
# suf_all[rem][d * 11 + diff]
suf_all = []
dp = [1] * 110
suf_all.append(dp)
for rem in range(1, M + 1):
new_dp = [0] * 110
for d in range(10):
for diff in range(11):
val = 0
for nx, nd in valid_nx[d][diff]:
val += dp[nx * 11 + nd]
new_dp[d * 11 + diff] = val % MOD
dp = new_dp
suf_all.append(dp)
def solve_f(N_str):
if not N_str or N_str == "0":
return 0
M_local = len(N_str)
N = [int(c) for c in N_str]
ans = 0
# 1. Less than M_local digits
for len_val in range(1, M_local):
for d in range(1, 10):
ans += suf_all[len_val - 1][d * 11 + 10]
ans %= MOD
# 2. Exactly M_local digits, strictly less than N
is_smooth = [True] * M_local
D = [0] * M_local
for i in range(1, M_local):
D[i] = abs(N[i] - N[i-1])
if i >= 2:
is_smooth[i] = is_smooth[i-1] and (D[i] >= D[i-1])
else:
is_smooth[i] = is_smooth[i-1]
for i in range(M_local):
if i > 0 and not is_smooth[i-1]:
break
limit = N[i]
start = 1 if i == 0 else 0
for d in range(start, limit):
if i == 0:
ans += suf_all[M_local - 1][d * 11 + 10]
elif i == 1:
diff = abs(N[0] - d)
ans += suf_all[M_local - 2][d * 11 + diff]
else:
diff = abs(N[i-1] - d)
if diff >= D[i-1]:
ans += suf_all[M_local - i - 1][d * 11 + diff]
ans %= MOD
# 3. N itself
if is_smooth[M_local-1]:
ans += 1
ans %= MOD
return ans
def is_smooth_num(S):
n = len(S)
if n <= 2:
return True
D = [abs(int(S[i]) - int(S[i-1])) for i in range(1, n)]
for i in range(1, len(D)):
if D[i] < D[i-1]:
return False
return True
ans = (solve_f(R_str) - solve_f(L_str) + (1 if is_smooth_num(L_str) else 0)) % MOD
print(ans)
if __name__ == '__main__':
main()
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: