上限制約付き桁DP

概要

数値上限以下の桁列を接頭辞から構成し、tight・started・剰余・digit maskなど将来に必要な有限統計を保つ。

考え方

上限の各桁とまだ一致するかをtightフラグで持つ。一度小さくなれば残りの桁は自由に選べる。桁和や剰余など未来に必要な情報だけを追加する。

初期値はdp[0][tight=1][started=0][初期統計]=1。次の桁dはtightなら上限桁以下、それ以外は0,…,b−1から選ぶ。newTight=tight AND(d=上限桁)、newStarted=started OR(d≠0)。数値の剰余rは (br+d) mod m、桁和はs+dへ更新する。digit maskは先頭0を実桁とみなさないならstartedが立ってから更新する。条件を満たす最終状態の個数を両tightについて足す。数0だけは全桁が先頭0となるので、0の数字表現を条件へどう含めるかを別に判定する。

値の総和も持つなら各状態に(count,sum)を保存する。次の桁dへの寄与は count'=count、sum'=b·sum+d·count。同じ遷移先へ加算すれば、候補数を列挙せず総和を求められる。

成立条件と計算量

L桁・基数b・追加状態SならO(LbS)。先頭0を実際の桁として数えるかは問題による。区間はF(R)−F(L−1)で求め、L=0の境界を扱う。巨大上限は文字列で読み整数overflowを避ける。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。tight・先頭の0・残す統計を分け、上限以下の整数を重複なく数える。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 接頭辞から更新する有限状態DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-digit-dp

上限制約付き桁DP

習得する技能

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

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 最小十分状態からDPを設計する。

このUnitを直接前提とする単元: なし。

接頭辞状態DPの共通像を得た後、数値上限とのtight・started・剰余・digit maskだけを状態にして、上限以下の整数を数える。

このUnitでは扱わないもの

  • 上限制約付き桁DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠