一意な後続・サイクル・ダブリング
概要
状態グラフを理解した後、後続が一意という制約からcycleと流入木への分解やダブリングを導く。
考え方
各頂点の行き先が一つなら、各成分は一つのcycleとそこへ流れ込む木になる。何回移動したかを扱う方法と、cycleへ着くまでの距離や周期を使う方法を比較する。
成立条件と計算量
明示的なN頂点なら構造分解はO(N)。巨大回数にはcycle長による剰余かbinary liftingを使う。出次数が一つであることが本質で、任意の有向graphへ同じ分解を適用しない。
下位単元
- 関数グラフのcycle・tree分解 — 水色
- doubling・binary lifting — 水色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC258 E「Packing Potatoes」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 尺取り法・sliding window / 補助タグ: 関数グラフのcycle・tree分解
- ABC370 F「Cake Division」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: doubling・binary lifting(一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: 尺取り法・sliding window / 補助タグ: doubling・binary lifting、単調境界探索
- ABC371 G「Lexicographically Smallest Permutation」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。追加で学ぶ技能: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 貪欲法と交換論、一次合同・CRT / 補助タグ: 関数グラフのcycle・tree分解
- ABC417 G「Binary Cat」 公式問題
技能・出典
主題: 圧縮・反復・再帰文字列へ問い合わせる(圧縮・反復・再帰または入れ子で定義された文字列を展開せず、block長・対応区切り・作用から照会・変換・評価できる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / doubling・binary lifting(一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。)。主タグ: 再帰・圧縮・入れ子文字列の走査 / 補助タグ: 単調進行による償却解析、doubling・binary lifting
- ABC444 G「Kyoen」 公式問題主題: Gaussian整数・二平方和
技能・出典
主題: Gaussian整数・二平方和(Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: Gaussian整数・二平方和 / 補助タグ: 関数グラフのcycle・tree分解
前提・学習成果・出典
導入対象の目安: 水色(1200–1599)。後続が一意な遷移をcycleと流入木に分け、反復を圧縮する入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-functional-graph
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 各頂点から複数の後続を選べる一般のグラフ探索・強連結成分への縮約。