典型タグ

上限制約付き桁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状態と遷移

関連する典型

学習成果と学習単位

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

    上限制約付き桁DPで学ぶ

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。