ABC 237 F — |LIS| = 3
分類・前提・執筆情報
掲載状態: 収録済み
最終確認:
学習上の位置付け
主題の単元: 最小十分状態からDPを設計する
- 主題
- 最小十分状態からDPを設計する: 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。
- 追加で学ぶ技能
- 既習技能
- LIS・末尾の支配関係: 同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
主タグ: DPの最小十分状態
補助タグ: LIS・末尾の支配関係
執筆: abc-explanation-author1.1.1 / revision 2
学習の位置
体系上の位置: 最小十分状態からDPを設計する
- 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。
先に読む単元:
- LIS・末尾の支配関係 — 列・subsequence DPで得た考え方と実装を再利用し、LIS・末尾の支配関係の発動条件・正当化・境界を重複なく学ぶ。
この解説で扱わないこと:
- 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る
同じ単元の問題
- ABC244-E — King Bombee
- ABC251-E — Takahashi and Animals
- ABC307-E — Distinct Adjacent
- ABC310-E — NAND repeatedly
- ABC232-E — Rook Path
- ABC215-E — Chain Contestant
- ABC375-E — 3 Team Division
- ABC265-E — Warp
- ABC247-F — Cards
- ABC403-F — Shortest One Formula
- ABC283-E — Don't Isolate Elements
- ABC264-F — Monochromatic Path
- ABC229-F — Make Bipartite
- ABC344-F — Earn to Advance
- ABC462-F — More ABC
- ABC450-F — Strongly Connected 2
- ABC311-F — Yet Another Grid Task
- ABC422-F — Eat and Ride
- ABC217-G — Groups
- ABC376-F — Hands on Ring (Hard)
- ABC391-G — Many LCS
- ABC281-G — Farthest City
- ABC345-E — Colorful Subsequence
- ABC227-E — Swap
- ABC279-G — At Most 2 Colors
- ABC273-G — Row Column Sums 2
- ABC416-G — Concat (1st)
- ABC389-G — Odd Even Graph
- ABC440-G — Haunted House
- ABC313-EX — Group Photo