E - バランスチェック / Balance Check Editorial by admin
gemini-3.5-flash-thinking概要
この問題は、\(1\) 以上 \(N\) 以下の整数のうち、最上位桁から数えて「奇数番目の桁の合計」と「偶数番目の桁の合計」の差の絶対値が \(D\) 以下であるものの個数を求める問題です。
\(N\) が最大で \(10^{15}\) と非常に大きいため、1つずつ条件を満たすか調べる方法（全探索）では間に合いません。このような「\(N\) 以下の整数で、特定の条件を満たすものの個数を数える」問題には、桁DP（桁動的計画法）という手法が非常に有効です。
考察
1. 桁DPの基本的な考え方
上（最上位）の桁から順番に数字を決定していくことを考えます。 例えば \(N = 314\) のとき、百の位、十の位、一の位の順に数字を決めていきます。このとき、以下の情報を状態として保持しながら遷移（次の桁の決定）を行います。
is_less（\(N\) 未満フラグ）: 現在までに決めた部分が、すでに \(N\) より小さいことが確定しているかどうかを表すフラグです。- 例えば \(N = 314\) で、百の位に
2を選んだ場合、十の位と一の位に何を選んでも \(N\) 未満になることが確定します（is_less = 1）。 - 百の位に
3を選んだ場合、まだ \(N\) 未満になるかは確定していないため、十の位には1以下の数字しか選べません（is_less = 0）。
- 例えば \(N = 314\) で、百の位に
2. この問題特有の課題と解決策
① Leading Zero（先頭の連続する0）の扱い
\(N\) が最大15桁のとき、3桁の数（例えば 123）を処理する際、上から「0, 0, 0, …, 1, 2, 3」と決めることになります。
しかし、問題文の「奇数番目」「偶数番目」は先頭のゼロを除いた、実際の最上位桁から数える必要があります。
- 00123 の場合、最初の非ゼロ桁である 1 が「1番目（奇数番目）」となります。
- これを正しく判定するため、「これまでに決めた桁がすべて \(0\) であるか」を表すフラグ is_leading_zero を状態に持たせます。
② 奇数番目と偶数番目の判定
最初の非ゼロ桁が現れた瞬間（is_leading_zero が \(1\) から \(0\) に変わる瞬間）が「1番目（奇数番目）」です。それ以降は、桁を進めるたびに奇数番目と偶数番目が交互に切り替わります。
これを管理するため、次に決める桁が奇数番目か偶数番目かを表すフラグ parity を状態に持たせます。
③ 奇数番目の和と偶数番目の和の差
奇数番目の和を \(S_{\mathrm{odd}}\)、偶数番目の和を \(S_{\mathrm{even}}\) としたとき、必要なのはその差 \(S_{\mathrm{odd}} - S_{\mathrm{even}}\) です。 DPの状態でこの差を保持します。 - 奇数番目の桁に数字 \(d\) を置くとき：差に \(+d\) する - 偶数番目の桁に数字 \(d\) を置くとき：差に \(-d\) する
差は負の値になることもあるため、配列のインデックスが負にならないよう、十分な大きさの基準値（offset = 150）を足して管理します。
アルゴリズム
DPテーブルの定義
以下のようにDPテーブルを定義します。
dp[i][is_less][is_leading_zero][parity][diff]
- i: 現在決定した桁数（\(0\) から \(L\) まで、\(L\) は \(N\) の桁数）
- is_less: すでに \(N\) 未満であることが確定しているか（\(0\): 未確定, \(1\): 確定）
- is_leading_zero: これまで決めた桁がすべて \(0\) か（\(0\): すでに非ゼロが出現, \(1\): すべて \(0\)）
- parity: 次に決める桁が、最初の非ゼロ桁から数えて奇数番目か偶数番目か（\(0\): 奇数番目, \(1\): 偶数番目）
- diff: \((S_{\mathrm{odd}} - S_{\mathrm{even}}) + \text{offset}\)
遷移のルール
現在の桁から次の桁の数字 \(d\)（\(0 \leq d \leq 9\)）を決めるとき、以下のように遷移します。
まだ非ゼロの桁が現れていない場合（
is_leading_zero == 1）- \(d = 0\) のとき：
依然として
is_leading_zeroは \(1\) のまま。パリティや差は変化しません。 - \(d \geq 1\) のとき：
この \(d\) が最初の非ゼロ桁（奇数番目）になります。
next_is_leading_zeroは \(0\) になり、差に \(d\) を加え、次のパリティは偶数番目（1）になります。
- \(d = 0\) のとき：
依然として
すでに非ゼロの桁が現れている場合（
is_leading_zero == 0）- 現在のパリティが奇数番目（
0）なら：差に \(+d\) し、次のパリティを1にする。 - 現在のパリティが偶数番目（
1）なら：差に \(-d\) し、次のパリティを0にする。
- 現在のパリティが奇数番目（
答えの集計
すべての桁を決定した後（i = L）、is_leading_zero == 0（正の整数である）かつ、実際の差の絶対値が \(D\) 以下（\(|S_{\mathrm{odd}} - S_{\mathrm{even}}| \leq D\)）であるものの総和が答えとなります。
計算量
時間計算量
- \(O(\log_{10} N \times \text{offset})\)
- \(N\) の桁数 \(L\) は最大で \(15\)。
- DPの状態数は \(15 \times 2 \times 2 \times 2 \times 300 = 36,000\)。
- 各状態からの遷移は \(0\) から \(9\) までの \(10\) 通り。
- 全体のループ回数は約 \(360,000\) 回となり、実行時間制限に対して一瞬（数ミリ秒）で処理が完了します。
空間計算量
- \(O(\log_{10} N \times \text{offset})\)
- DPテーブルのサイズは \(18 \times 2 \times 2 \times 2 \times 300\) の
long long型配列であり、約 \(345 \text{ KB}\) と非常に省メモリです。
- DPテーブルのサイズは \(18 \times 2 \times 2 \times 2 \times 300\) の
実装のポイント
負のインデックス対策（オフセット）: 差 \(S_{\mathrm{odd}} - S_{\mathrm{even}}\) は負になり得ます。最大桁数が \(15\) のため、差の範囲は最大でも \(-135\) から \(135\) の間です。そのため、
offset = 150を足して常に正の範囲（\(0\) から \(300\)）に収まるようにしています。正の整数のみをカウントする: 問題文では「\(1\) 以上 \(N\) 以下」の正の整数を求められています。 すべてが \(0\) である状態（
is_leading_zero == 1の状態）は \(0\) を表すため、最終的な集計時にis_leading_zero == 0の状態のみを足し合わせることで、正の整数のみを正しくカウントできます。ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
// dp[i][is_less][is_leading_zero][parity][diff]
// i: 決定した桁数 (0 to L)
// is_less: 1 if already less than N, 0 otherwise
// is_leading_zero: 1 if all digits so far are 0, 0 otherwise
// parity: 0 if next digit is odd-positioned, 1 if even-positioned (only valid if is_leading_zero is 0)
// diff: S_odd - S_even + offset
long long dp[18][2][2][2][300];
int main() {
// 高速入出力
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string S;
if (!(cin >> S)) return 0;
long long D;
if (!(cin >> D)) return 0;
int L = S.length();
int offset = 150;
dp[0][0][1][0][offset] = 1;
for (int i = 0; i < L; ++i) {
int limit_digit = S[i] - '0';
for (int is_less = 0; is_less < 2; ++is_less) {
for (int is_leading_zero = 0; is_leading_zero < 2; ++is_leading_zero) {
for (int parity = 0; parity < 2; ++parity) {
for (int diff = 0; diff < 300; ++diff) {
long long val = dp[i][is_less][is_leading_zero][parity][diff];
if (val == 0) continue;
int max_d = is_less ? 9 : limit_digit;
for (int d = 0; d <= max_d; ++d) {
int next_is_less = is_less || (d < limit_digit);
int next_is_leading_zero = is_leading_zero && (d == 0);
if (next_is_leading_zero) {
dp[i + 1][next_is_less][1][0][offset] += val;
} else {
int next_parity;
int next_diff;
if (is_leading_zero) {
// 最初の非ゼロ桁 (奇数番目の第1桁)
next_diff = diff + d;
next_parity = 1; // 次は偶数番目
} else {
if (parity == 0) {
next_diff = diff + d;
next_parity = 1;
} else {
next_diff = diff - d;
next_parity = 0;
}
}
if (next_diff >= 0 && next_diff < 300) {
dp[i + 1][next_is_less][0][next_parity][next_diff] += val;
}
}
}
}
}
}
}
}
long long ans = 0;
for (int is_less = 0; is_less < 2; ++is_less) {
for (int parity = 0; parity < 2; ++parity) {
for (int diff = 0; diff < 300; ++diff) {
long long val = dp[L][is_less][0][parity][diff];
if (val > 0) {
long long actual_diff = abs(diff - offset);
if (actual_diff <= D) {
ans += val;
}
}
}
}
}
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: