上限制約付き桁DP
数値上限以下の桁列を接頭辞から構成し、tight・started・剰余・digit maskなど将来に必要な有限統計を保つ。
この典型を扱う単元: 上限制約付き桁DP
検索別名: digit DP、tight DP、上限制約付き桁DP、桁DP
未知問からこの典型を見つける手掛かり
- 扱う対象
- 上限
- 二進表記
- 十進表記
- 数字列
- 桁
- 使う手掛かり
- leading zero
- prefix
- 剰余
- 未満フラグ
- 桁ごと
- 保つ不変量
- started flag
- tight flag
- 上限と一致
- 先頭ゼロ
- 求めるもの
- 以下の個数
- 値の総和
- 条件を満たす数
- 適用しない条件
- automaton state
- carryだけ
- parser
- syntax
- 文法
- 構文木
- 混合基数
- 禁止pattern
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
- automaton上のDP・行列遷移: 数値上限のtight状態を扱うDPと、受理条件を表す有限automatonとの直積DPを区別する。
- 繰り上がり・混合基数DP: 上限との接頭辞一致を保つ桁DPと、下位桁から繰り上がりだけを渡す混合基数DPを区別する。
学習成果と学習単位
数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。
上限制約付き桁DPで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC235 F「Variety of Digits」 公式問題主題: 上限制約付き桁DP / 主タグ
- ABC336 E「Digit Sum Divisible」 公式問題主題: 上限制約付き桁DP / 主タグ
- ABC406 E「Popcount Sum 3」 公式問題主題: 上限制約付き桁DP / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC235 F「Variety of Digits」 公式問題主題: 上限制約付き桁DP / 主タグ
- ABC288 Ex「A Nameless Counting Problem」 公式問題主題: 上限制約付き桁DP / 主タグ
- ABC317 F「Nim」 公式問題主題: 上限制約付き桁DP / 主タグ
- ABC336 E「Digit Sum Divisible」 公式問題主題: 上限制約付き桁DP / 主タグ
- ABC406 E「Popcount Sum 3」 公式問題主題: 上限制約付き桁DP / 主タグ
- ABC465 E「Digit Circus」 公式問題主題: 上限制約付き桁DP / 主タグ