ABC 457 G — Catch All Apples
分類・前提・執筆情報
掲載状態: 収録済み
Catch All Apples の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: 半順序・Dilworth・最大反鎖
- 主題
- 半順序・Dilworth・最大反鎖: 対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。
- 追加で学ぶ技能
- 既習技能
- LIS・末尾の支配関係: 同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
- 幾何の基本判定と座標変換: 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。
主タグ: 半順序・Dilworth・最大反鎖
補助タグ: 幾何の基本判定・配置・座標変換 LIS・末尾の支配関係
執筆: abc-explanation-author1.1.1 / revision 1
学習の位置
体系上の位置: 半順序・Dilworth・最大反鎖
- 対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。
先に読む単元:
- 二部matching・Hall・Kőnig — 二部グラフの彩色と成分構造で得た考え方と実装を再利用し、二部matching・Hall・Kőnigの発動条件・正当化・境界を重複なく学ぶ。
- LIS・末尾の支配関係 — 列・subsequence DPで得た考え方と実装を再利用し、LIS・末尾の支配関係の発動条件・正当化・境界を重複なく学ぶ。
- 列・subsequence DP — DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence DPの発動条件・正当化・境界を重複なく学ぶ。
- 幾何の基本判定と座標変換 — 座標と外積・距離式で向きや交差を代数判定し、凸幾何へ進む前提を作る。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る