有界全列挙・有限case分解
制約や生成パラメータから候補総数を界すか、鳩ノ巣原理で成功前の失敗回数を界して探索する。
この典型を扱う単元: 候補数を界して全列挙・有限case分解する
検索別名: bounded exhaustive search、finite case enumeration、制約を利用した全探索、小さい候補集合の全列挙
未知問からこの典型を見つける手掛かり
- 扱う対象
- case
- 候補
- 生成パラメータ
- 組合せ
- 配置
- 使う手掛かり
- 候補数
- 全て試す
- 固定個
- 場合分け
- 高々
- 保つ不変量
- 候補総数の上界
- 漏れなく
- 重複なく
- 求めるもの
- 全caseの評価
- 存在判定
- 最適値
- 構成
- 適用しない条件
- divide.?and.?conquer
- meet.?in.?the.?middle
- 分割統治
- 半分.*列挙
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- meet-in-the-middle・半分全列挙: 候補全体を制約から直接界す全列挙と、探索空間を二分して部分結果を照合する半分全列挙を区別する。
学習成果と学習単位
制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。
候補数を界して全列挙・有限case分解するで学ぶ集合のbitmask表現から全部分集合と共通要素を列挙し、集合間のDP遷移を必要としない計数に利用できる。
候補数を界して全列挙・有限case分解するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC219 E「Moat」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC220 G「Isosceles Trapezium」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC223 E「Placing Rectangles」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC226 F「Score of Permutations」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC227 F「Treasure Hunting」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC227 H「Eat Them All」 公式問題主題: 最大流・最小カット / 補助タグ
- ABC234 E「Arithmetic Number」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC234 Ex「Enumerate Pairs」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP / 補助タグ
技能・出典
主題: 値域集約による部分列DP
主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC246 F「typewriter」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC248 E「K-colinear Line」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC254 E「Small d and k」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC257 F「Teleporter Setting」 公式問題主題: 最短路モデル / 補助タグ
- ABC258 F「Main Street」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC260 F「Find 4-cycle」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC270 F「Transportation」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
- ABC271 Ex「General General」 公式問題主題: gcdと整数解の成立条件 / 補助タグ
- ABC272 E「Add and Mex」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC284 E「Count Simple Paths」 公式問題主題: backtracking・可逆な探索状態 / 補助タグ
- ABC290 G「Edge Elimination」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC298 G「Strawberry War」 公式問題主題: 区間合成・領域分割DP / 補助タグ
- ABC301 G「Worst Picture」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC302 G「Sort from 1 to 4」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC312 E「Tangency of Cuboids」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC313 F「Flip Machines」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC323 F「Push and Carry」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC328 E「Modulo MST」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC331 E「Set Meal」 公式問題主題: priority queue・best-first列挙 / 補助タグ
- ABC343 E「7x7x7」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC347 F「Non-overlapping Squares」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC353 F「Tile Distance」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC369 E「Sightseeing Tour」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC386 E「Maximize XOR」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC387 E「Digit Sum Divisible 2」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC409 F「Connecting Points」 公式問題主題: priority queue・best-first列挙 / 補助タグ
技能・出典
主題: priority queue・best-first列挙
主タグ: priority queue・best-first列挙 / 補助タグ: 有界全列挙・有限case分解、DSUによる連結成分管理・縮約
- ABC410 F「Balanced Rectangles」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 補助タグ
- ABC419 G「Count Simple Paths 2」 公式問題主題: near-tree graphのkernel化 / 補助タグ
- ABC423 G「Small Multiple 2」 公式問題主題: 一次合同・CRTで解の類を統合する / 補助タグ
- ABC442 G「Lightweight Knapsack」 公式問題主題: 候補数を界して全列挙・有限case分解する / 主タグ
- ABC459 G「Golf 2」 公式問題主題: 二変数の凸区分線形整数最適化 / 補助タグ