状態・配置の正規化
対称操作で同値な状態を一意な標準形へ写し、重複した探索・数え上げを除く。
この典型を扱う単元: 同値な状態を正規化する
検索別名: state canonicalization、標準形による状態圧縮
未知問からこの典型を見つける手掛かり
- 扱う対象
- 列
- 状態
- 配置
- 使う手掛かり
- 代表
- 同値
- 対称
- 保つ不変量
- 同値類
- 標準形
- 求めるもの
- 状態圧縮
- 重複除去
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
学習成果と学習単位
鏡映対称な文字列を自由な前半で一意に表し、辞書順上限以下の個数を前半prefixの基数値と、等号境界の完成文字列一候補との比較で求められる。
同値な状態を正規化するで学ぶ対称操作で同値な状態の標準形と不変量を選べる。
同値な状態を正規化するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC242 E「(∀x∀)」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC296 F「Simultaneous Swap」 公式問題主題: 同値な状態を正規化する / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 H「Red and Blue Lamps」 公式問題主題: path matchingのheap縮約greedy / 補助タグ
技能・出典
主題: path matchingのheap縮約greedy
主タグ: path matchingのheap縮約greedy / 補助タグ: 索引付き連結リスト、priority queue・best-first列挙、状態・配置の正規化
- ABC219 F「Cleaning Robot」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC232 H「King's Tour」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC242 E「(∀x∀)」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC250 E「Prefix Equality」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC278 G「Generalized Subtraction Game」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 補助タグ
- ABC284 G「Only Once」 公式問題主題: 関数グラフのcycle・tree分解 / 補助タグ
- ABC296 F「Simultaneous Swap」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC301 F「Anti-DDoS」 公式問題主題: 有限状態automatonの構成 / 補助タグ
- ABC302 G「Sort from 1 to 4」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC307 E「Distinct Adjacent」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC313 G「Redistribution of Piles」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC323 F「Push and Carry」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC360 E「Random Swaps of Balls」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC382 G「Tile Distance 3」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC404 F「Lost and Pound」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC411 G「Count Cycles」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC421 E「Yacht」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC425 F「Inserting Process」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC427 G「Takahashi's Expectation 2」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC446 G「221 Subsequence」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC450 G「Random Subtraction」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC462 E「Alternating Costs」 公式問題主題: 同値な状態を正規化する / 主タグ
- ABC463 F「Senshuraku」 公式問題主題: 同値な状態を正規化する / 主タグ