ABC 320 G — Slot Strategy 2 (Hard)
分類・前提・執筆情報
掲載状態: 収録済み
Slot Strategy 2 (Hard) の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: 二部matching・Hall・Kőnig
- 主題
- 二部matching・Hall・Kőnig: 左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
- 追加で学ぶ技能
- 既習技能
- 疎なkeyの順序を保ってdense indexへ圧縮する: 初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。
- 剰余周期と指数法則を利用する: 剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。
- 単調境界を証明して探索する: 判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。
- 交換論から選択順を導く: 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。
補助タグ: 座標・値の順序保存圧縮 貪欲法と交換論 剰余周期・指数法則 単調境界探索
執筆: abc-explanation-author1.1.1 / revision 2
学習の位置
体系上の位置: 二部matching・Hall・Kőnig
- 左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
先に読む単元:
- 二部彩色と成分構造を扱う — 無向グラフを探索できることを前提に二部性と部の交換対称性を扱い、連結二部グラフの彩色重複も補正する。
- 疎なkeyの順序を保ってdense indexへ圧縮する — 保持すべき疎な座標をsort-uniqueして順序・等値性を添字へ写す。距離・時間差・区間長も使う場合は元座標と間隔を併せて保存する。
- 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。
- 剰余周期と指数法則を利用する — 剰余列や冪が有限状態で周期化することを示し、周期前計算や指数法則で巨大な反復を短縮する。
- 単調境界を証明して探索する — 判定結果が一方向に変わることを証明し、巨大な値域から成功・失敗の境界を二分探索で求める。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る