ABC 336 E — Digit Sum Divisible

考察

条件n mod digitSum(n)=0ではmodulus自体が桁選択で変わるため、そのまま一つの桁DP状態に入れにくい。先に最終桁和sを固定すれば、桁和sかつn mod s=0という通常の有限状態DPになる。

採用する候補: 可能な桁和sを全探索し、各sについて桁和・剰余付きdigit DPを行う

最大桁和は高々9×桁数で小さく、変動する除数を外側loopへ分離できる。

棄却する候補: 1からNまで各整数の桁和と剰余を直接調べる

Nは10^14まであり線形列挙できない。

固定したsごとに、上位d桁までのdigit sum i、値mod s=j、Nのprefixと一致中か未満かを持てば、次digit tで(i+t,(10j+t) mod s)へ遷移できる。最終状態(i,j)=(s,0)だけがそのsのgood整数を数える。

Nをdecimal digit列にし、s=1から9×桁数まで繰り返す。dp[pos][sum][rem][tight]を0初期化しdp[0][0][0][1]=1、許される次digitを配る。全桁後のdp[L][s][0][0/1]を加算する。

典型の発動条件

parameter固定によるdigit DP

発動条件: 桁から決まる値が同時にmodulusとして使われ、状態遷移の法が未確定である。

最終digit sum sを外側で固定し、各DP内では剰余状態0,…,s-1を使う。

上限制約付き桁DP

発動条件: 0≤n≤Nのうち桁和と剰余条件を満たす個数を数える。

tight flagでN prefixとの大小を持ち、leading zeroを許して固定長列として処理する。

問題固有の要素

各正整数は桁和sをただ一つ持つので、sごとの数え上げは重複せず、その和が答えになる。

別の問題へ持ち帰る視点: 状態遷移のmodulusや目標値が対象自身から決まる場合、取り得る小範囲を外側列挙すると通常DPへ戻せる。

正当性

正整数xは桁和sを一意に持つので、sを固定した対象集合は互いに重複しない。digit DPは処理済み桁の桁和・x mod s・Nのprefixとの比較を持ち、次digit dで和へd、剰余へ10r+dを加える。これらは条件判定に必要十分で、全digit列を一度だけ表す。最後に桁和sかつ剰余0を取ると、ちょうどxがその桁和で割り切れる条件になる。leading zeroは一意のpaddingであり、s≥1なので整数0は受理されない。全sの和が求める個数である。

実装上の注意

  • leading zeroで表した0はs≥1の最終桁和条件を満たさず自動除外される。sum>sの遷移を切り、N=10^14でも安全な最大sを桁数から取る。

復習の核

  • 小さいNで1…Nを直接列挙し、9の繰上がり境界、N自身を含むtight状態、桁和1・最大付近のsを比較する。

計算量と制約

時間

O(D(9D)³)、DはNの十進桁数、固定sのsum×remainder状態を全sで走査。

空間

O((9D)²)、pos方向rolling。

制約との対応

公式制約の確認範囲: Time limit: 10 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^{14}; N is an integer.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Digit Sum Divisible の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 上限制約付き桁DP

主題
  • 上限制約付き桁DP: 数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 上限制約付き桁DP

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: 上限制約付き桁DP

      • 数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題