ABC 389 G — Odd Even Graph
分類・前提・執筆情報
掲載状態: 収録済み
Odd Even Graph の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: 最小十分状態からDPを設計する
- 主題
- 最小十分状態からDPを設計する: 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。
- 追加で学ぶ技能
- 既習技能
- 組合せを生成関数へ符号化する: 組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。
- 組合せ係数と対称性で数える: 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。
主タグ: DPの最小十分状態
補助タグ: 組合せ係数・数え上げ 生成関数による組合せ構造の符号化
執筆: abc-explanation-author1.1.1 / revision 3
学習の位置
体系上の位置: 最小十分状態からDPを設計する
- 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。
先に読む単元:
- 組合せ係数と対称性で数える — 選び方を通常・Gaussian二項係数で整理し、必要ならStirling変換でrank別計数を基底変換する。
- 組合せを生成関数へ符号化する — 高速畳み込みを前提にせず、係数の意味を定義して和・積・sequence・set・cycleが表す組合せ構造を欲しい係数へ翻訳する。
この解説で扱わないこと:
- 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る
同じ単元の問題
- 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
- ABC237-F — |LIS| = 3
- 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)
- ABC440-G — Haunted House
- ABC313-EX — Group Photo