考察
上限が巨大でも、上の桁から数字を決めれば「まだ上限と一致しているか」と「どの数字が出たか」で残りの選択肢をまとめられる。さらに、まとめた整数の個数と総和を一緒に持つと、末尾に数字を付けた後の総和も一度に更新できる。
残りの選択肢を決める情報
上限 は最大1万桁なので、1から順に整数を調べることはできない。そこで を文字列で読み、その桁数を とする。短い整数は左を0で埋めて 桁に揃え、上位桁から順に作る。
途中まで決めた桁列を接頭辞と呼ぶ。同じ桁数まで作った接頭辞について、以後の選択に必要なのは次の情報である。
tight:接頭辞が上限の同じ長さの接頭辞と一致していれば1、すでに小さければ0。一致している間だけ、次の数字を上限の対応桁以下に制限する。
started:0でない数字を一度でも選んでいれば1。0のままなら、これまで選んだ0はすべて桁埋めである。
mask:実際の表記に現れた数字の集合を表す10ビットの整数。数字 が現れたらビット を立てる。出現回数や順序は、各必須数字を一度以上含むかの判定に影響しない。
桁位置は外側のループで管理し、各 (tight, started, mask) に、その状態に属する接頭辞の個数 count と、接頭辞を数値とみなした総和 sum を保存する。
総和の更新には個数も必要
ある状態に属する接頭辞の値を とする。各接頭辞の末尾に同じ数字 を付けると、値はそれぞれ になる。したがって、その遷移が次の状態へ加える総和は
である。数字 は各接頭辞に一回ずつ付くため、総和だけでは更新できず、個数も必要になる。同じ数字を付けてできる接頭辞の個数は変わらないので、次の個数への寄与は count である。
空の接頭辞から一桁ずつ配る
まだ一桁も選んでいないときは、tight=1, started=0, mask=0 に (count, sum)=(1, 0) を置き、他の状態を (0, 0) にする。空の接頭辞は「何も選ばない方法」一つなので個数は1、その値は0なので総和は0である。
次の手順を上の桁から 回繰り返す。DPの個数・総和に関する加算と乗算はすべて で剰余を取る。
- 次の桁まで作った状態を保存する別の配列を用意し、全状態の個数・総和を0にする。
- 現在の各状態について、上限の対応桁の数字を とすると、
tight=1 なら 、tight=0 なら の各数字 を選ぶ。
- 遷移先を次のように決める。
newTight = tight && (d == a)。一度上限より小さくなった接頭辞は、その後も小さいままである。
newStarted = started || (d != 0)。
newStarted=0 なら newMask=mask のままにする。このときの0は桁埋めである。それ以外なら newMask = mask | (1 << d) とし、数字 のビットを立てる。開始後に選ぶ0もこの場合に含まれる。
- 遷移先
(newTight, newStarted, newMask) の次層の個数へ count、総和へ 10 * sum + d * count を加える。複数の遷移が同じ状態へ来るので、代入ではなく加算する。
- 全状態・全候補数字を処理したら、現在の配列を次層の配列に置き換える。同じ桁の処理中に、書き込んだ値を再び遷移元として使わない。
最後に、必須数字のビットを立てた集合を req として、started=1 かつ (mask & req) == req を満たす状態の sum を足す。tight=0 は上限未満、tight=1 は上限自身に対応するので、両方を集計する。全桁が0の状態は started=0 のため除外される。
典型の発動条件
出現集合付き digit DP
上限以下の整数を数え、条件が各数字の出現の有無だけで決まるときは、出現集合をビット集合に圧縮できる。上限との一致を tight、桁埋めの0と実際の0の区別を started で管理する。
桁 DP での値の総和
桁の追加で各値が同じ一次式に従って変わるなら、状態ごとの個数と総和だけで、次の総和を更新できる。整数値の列挙を避けたいときは、更新式を総和にして、個数の項が必要にならないかを調べる。
問題固有の要素
必須数字に0が含まれると、左に埋めた0を出現として数える誤りが起きやすい。次は説明用の小例である。、必須数字が0だけの場合を考える。説明のため上限も 020 と書いて3桁に揃えると、条件を満たすのは 010 と 020、すなわち10と20で、総和は30になる。余分な先頭0を一桁付けても、整数との対応は変わらない。
010 では最初の0を選んでも started=0, mask=0 のままである。次の1で started=1 となりビット1を立て、最後の0で初めてビット0を立てる。020 も同様に、最後の0が実際の表記中の0になる。
一方、001 は整数1を表す。最初の二つの0はどちらも桁埋めで、最後の1を選ぶまで mask=0 のままである。完成後もビット0は立たず、必須数字0の条件を満たさない。0という値だけを見てビットを立てるのではなく、数が開始したかと組み合わせて判定する。
正当性
上から同じ桁数だけ処理したとき、各状態の count と sum は、その状態に属する接頭辞の個数と数値の総和を表すとする。初期状態には空の接頭辞が一つあり、その値は0なので、この意味を満たす。
同じ tight・started・mask を持つ接頭辞では、次に選べる数字も、今後満たすべき出現条件も等しい。よって一つの状態にまとめられる。各接頭辞に数字を一つ付ける操作は、上限を超えない全候補を尽くし、異なる接頭辞や数字から同じ桁列を重複して作らない。接頭辞の値を とすると、桁追加後は になることから、個数と総和の更新式も上の意味を保つ。桁埋めの0だけを出現集合から除くため、mask は常に実際の十進表記で現れた数字の集合である。
最後には、1以上上限以下の各整数が、左を0で埋めた桁列と一対一に対応する。started=1 で0を除き、(mask & req) == req で必須数字をすべて含む整数だけを残せる。両方の tight の sum を足すので、上限自身も含め、求める整数の値を一度ずつ加えた答えを得る。加算・乗算のたびに剰余を取っても、最終的な答えの剰余は変わらない。
実装上の注意
- は整数型へ変換せず文字列で持ち、各文字から対応する一桁だけを取り出す。
- 次層の配列は毎桁0に戻す。上限との比較・出現集合の更新は現在の状態から行い、個数・総和だけを次層へ加算する。
- 剰余を取った
count が0でも、sum が0とは限らない。count == 0 だけを理由に遷移を省かず、全状態を処理すればよい。
- 積を計算してから剰余を取るまでに、32ビット整数の範囲を超え得る。
10 * sum + d * count は十分な幅の整数型や剰余演算用の型で計算する。
復習の核
- 値を一つずつ求められないときは、桁追加の式をまとめて足し、次の総和を更新するための統計を探す。
- 空の接頭辞は個数1・総和0。初期値はそれぞれが何を表すかから決める。
- 必須数字0の小例で、桁埋めの0を無視し、開始後の0を出現として扱えているか確かめる。
計算量と制約
時間
桁数を とする。各桁で tight・started の各2通りと、出現集合 通りに対し最大10個の数字を試すため、時間計算量は 。各桁の次層の初期化と、最後の全状態の集計もこの範囲に含まれる。
空間
現在と次の桁の2層だけを保持するので、DPの作業領域は 。上限文字列の保存に 必要なため、入力を含む全体の空間計算量は である。
制約との対応
より 。桁数に比例する処理と、10種類の数字の出現集合で管理でき、上限の数値の大きさに比例する列挙は行わない。必須数字は 個で、 なので10ビットの req に収まる。実装では全桁分のDP配列を保存せず2層を使う。
出典