E - スムーズな山道 / Smooth Mountain Path 解説 by admin
gemini-3.5-flash-thinking概要
この問題は、与えられた区間 \([L, R]\) に含まれる整数のうち、隣り合う桁の差（段差）が右に進むにつれて単調非減少（等しいか大きくなる）であるものの個数を求める問題です。 桁数が最大 \(5000\) と非常に大きいため、愚直に1つずつ判定することは不可能です。巨大な数に対する数え上げ問題の定番である桁DP（Digit DP）を用いることで、高速に解くことができます。
考察
1. 範囲の言い換え
区間 \([L, R]\) における条件を満たす整数の個数を直接求めるのは難しいため、以下の性質を利用します。
$\((\text{区間 } [L, R] \text{ の個数}) = (\text{1以上 } R \text{ 以下の個数}) - (\text{1以上 } L \text{ 以下の個数}) + (\text{L自身が条件を満たすか (0 or 1)})\)\(
これにより、ある整数 \)X\( に対し、「\)1\( 以上 \)X$ 以下のスムーズな山道の個数」を求める関数 solve(X) を設計することに集中できます。
2. 桁DPの設計
上の桁（左端）から順に数字を決めていく桁DPを考えます。 「スムーズな山道」であるかを判定するためには、以下の情報が必要です。 - 直前の桁にどの数字を置いたか（現在の桁との差を計算するため） - 直前の段差はいくつだったか（現在の段差が「直前の段差以上」であるかを判定するため）
また、桁DPの一般的な状態として以下が必要です。
- 現在決めている値が、上限 \(X\) 未満であることが確定しているか（less）
- すでに \(1\) 以上の数字が始まっているか（is_start）。これは、先頭の余分な 0（リーディングゼロ）を無視するために不可欠です。
これらをまとめると、DPの状態（State）は次のように定義できます。
dp[less][is_start][prev_digit][prev_diff]
- less: 上限未満が確定しているか（\(0\): 未確定、 \(1\): 確定）
- is_start: 数値が始まっているか（\(0\): まだ（すべて 0）、 \(1\): 開始している）
- prev_digit: 直前の桁の数字（\(0 \le \text{prev\_digit} \le 9\)）
- prev_diff: 直前の段差（\(0 \le \text{prev\_diff} \le 9\)。まだ段差が存在しない場合は番兵として \(10\) とする）
アルゴリズム
DPの遷移
現在の桁に配置する数字を \(d\) （\(0 \le d \le 9\)）とします。
まだ数値が始まっていない場合 (
is_start == 0)- \(d = 0\) のとき：
数値は始まらないままです。状態は更新されず、直前の段差も存在しない状態（
10）のままです。 - \(d > 0\) のとき：
ここから数値が始まります。
next_is_start = 1となり、直前の数字は \(d\)、直前の段差はまだ存在しないため10となります。
- \(d = 0\) のとき：
数値は始まらないままです。状態は更新されず、直前の段差も存在しない状態（
すでに数値が始まっている場合 (
is_start == 1)- 直前の数字
prev_digitと現在の数字 \(d\) の差（現在の段差）を \(e = |d - \text{prev\_digit}|\) とします。 - もし
prev_diff == 10（これが最初の段差）であれば、無条件で遷移可能です。次の直前段差は \(e\) になります。 - もし
prev_diff != 10であれば、単調非減少の条件 \(e \ge \text{prev\_diff}\) を満たす場合のみ遷移可能です。次の直前段差は \(e\) になります。
- 直前の数字
初期状態
dp[0][0][0][10] = 1- 他の状態はすべて
0
答えの集計
すべての桁について遷移を行った後、is_start == 1（実際に存在する正の整数）である状態の総和が、求める個数となります。
計算量
時間計算量
- 桁DPの遷移: 桁数を \(N\)（最大 \(5000\)）とします。 DPの状態数は \(2 \times 2 \times 10 \times 11 = 440\) です。 各状態から次の桁の数字 \(d\)（\(10\) 通り）への遷移を試みます。 したがって、1桁進めるためのループ回数は最大でも \(440 \times 10 = 4400\) 回です。 全体での遷移回数は \(O(N \times 2 \times 2 \times 10 \times 11 \times 10)\) となり、定数倍を考慮しても約 \(2.2 \times 10^7\) 回の演算で済み、実行時間制限に余裕で間に合います。
- \(L\) の判定: \(L\) がスムーズな山道であるかの判定は \(O(N)\) で行えます。
よって、全体時間計算量は \(O(N)\) です。
空間計算量
DPの遷移は直前の桁の状態のみに依存するため、インプレース（または2つの配列を交互に使い回す方法）で実装できます。 必要な配列サイズは \(2 \times 2 \times 10 \times 11\) の定数サイズです。
よって、空間計算量は \(O(1)\)（または入力を保持するメモリを考慮して \(O(N)\)）です。
実装のポイント
引き算における負の数の余り:
solve(R) - solve(L)を行う際、引き算の結果が負になることがあります。プログラミング言語の仕様（特に C++ や Java など）に合わせて、(ans_R - ans_L + is_L_smooth + MOD) % MODのようにMODを足してから余りを取るようにします。リーディングゼロの区別: 例えば
000123のような数を考える際、先頭の0同士の差を段差として計算してしまうと誤判定の原因になります。必ずis_startフラグを用いて、実際の数が始まってからの段差のみを計算するように制御します。ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int MOD = 1000000007;
int dp[2][2][10][11];
int next_dp[2][2][10][11];
int solve(const string& S) {
int N = S.length();
memset(dp, 0, sizeof(dp));
dp[0][0][0][10] = 1;
for (int i = 0; i < N; ++i) {
memset(next_dp, 0, sizeof(next_dp));
int limit = S[i] - '0';
for (int less = 0; less < 2; ++less) {
for (int is_start = 0; is_start < 2; ++is_start) {
for (int prev_digit = 0; prev_digit < 10; ++prev_digit) {
for (int prev_diff = 0; prev_diff <= 10; ++prev_diff) {
int val = dp[less][is_start][prev_digit][prev_diff];
if (val == 0) continue;
int max_d = less ? 9 : limit;
for (int d = 0; d <= max_d; ++d) {
int next_less = less || (d < limit);
int next_is_start = is_start;
int next_prev_digit = prev_digit;
int next_prev_diff = prev_diff;
if (is_start == 0) {
if (d == 0) {
next_is_start = 0;
next_prev_digit = 0;
next_prev_diff = 10;
} else {
next_is_start = 1;
next_prev_digit = d;
next_prev_diff = 10;
}
} else {
next_is_start = 1;
next_prev_digit = d;
int diff = abs(prev_digit - d);
if (prev_diff == 10) {
next_prev_diff = diff;
} else {
if (diff >= prev_diff) {
next_prev_diff = diff;
} else {
continue;
}
}
}
next_dp[next_less][next_is_start][next_prev_digit][next_prev_diff] += val;
if (next_dp[next_less][next_is_start][next_prev_digit][next_prev_diff] >= MOD) {
next_dp[next_less][next_is_start][next_prev_digit][next_prev_diff] -= MOD;
}
}
}
}
}
}
memcpy(dp, next_dp, sizeof(dp));
}
int ans = 0;
for (int less = 0; less < 2; ++less) {
for (int prev_digit = 0; prev_digit < 10; ++prev_digit) {
for (int prev_diff = 0; prev_diff <= 10; ++prev_diff) {
ans += dp[less][1][prev_digit][prev_diff];
if (ans >= MOD) ans -= MOD;
}
}
}
return ans;
}
bool is_smooth(const string& S) {
if (S.length() <= 2) return true;
int prev_diff = -1;
for (size_t i = 0; i < S.length() - 1; ++i) {
int diff = abs((S[i] - '0') - (S[i+1] - '0'));
if (prev_diff != -1 && diff < prev_diff) {
return false;
}
prev_diff = diff;
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string L, R;
if (!(cin >> L >> R)) return 0;
int ans_R = solve(R);
int ans_L = solve(L);
int is_L_smooth = is_smooth(L) ? 1 : 0;
int ans = (ans_R - ans_L + is_L_smooth + MOD) % MOD;
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
投稿日時:
最終更新: