ABC 290 G — Edge Elimination

考察

辺や頂点を展開するには完全木が大きすぎる。そこで、最後に残す連結成分の「最も浅い頂点」vを固定する。深さhのvを残すなら、その親辺を切る費用は[h>0]。vの下にある深さH=D−hの完全K分木から、X頂点を残す問題になる。同じ深さのvは対称なので、h=0,…,Dだけを列挙すればよい。

深さiの完全木のサイズをV_0=1、V_{i+1}=1+KV_iとする。V_H<Xならこのhは不可能。そうでなければ削除数はR=V_H−Xである。v以外の部分木を一つ丸ごと落とす切断は、あるV_i(0≤i<H)頂点を削除する。最終成分の外側の最上位部分木だけを切れば十分であり、その部分木同士は重ならない。従って任意の解は、RをV_0,…,V_{H−1}の和で表す硬貨表現を与える。

まず木上の配置を忘れ、硬貨の最小枚数を求める。大きいV_iからq_i=floor(R/V_i)枚取り、R←R−q_iV_iとすればよさそうだが、一般の硬貨ではこの貪欲は成立しない。必要なのはこの額面列特有の交換式である。V_{−1}=0と約束すると、0≤l≤jに対して

K V_j + V_l = V_{j+1} + K V_{l−1}

となる。左辺のK+1枚を右辺へ交換しても枚数は増えず、より大きい額面V_{j+1}の枚数が増える。l=0ならK+1枚を一枚へ減らせる。この交換から貪欲の最適性を、次の正当性で示す。

次に、硬貨の表現が実際の木へ置けるか確認する。深さHの木でR≤V_H−1=KV_{H−1}だから、最初に削る子部分木数q=floor(R/V_{H−1})は高々K。q=Kなら余りは0で根だけが残る。q<Kなら、q個の子を丸ごと落とし、余りr<V_{H−1}の削除を残った一つの子の中だけで行う。他の子には触れない。この操作を深さについて繰り返せば、貪欲の硬貨を互いに重ならない部分木へ配置できる。

例えばK=2,H=2では額面は1,3、全体サイズは7。X=3なら削除数4を3+1とし、一つの深さ1の子を丸ごと削り、もう一つの子の葉を一枚削る。硬貨表現の最適性と、二つの削除が重ならない実現可能性は別の議論である。

各hについてこの貪欲枚数に[h>0]を加え、最小値を答える。H=0ではX=1だけが可能で、硬貨を一枚も使わない。

典型の発動条件

構造付き硬貨の交換

発動条件: 一回の削除量が少数の階層サイズに限られる。

大きい額面から取る前に、枚数を増やさず大きい額面の個数を増やせる交換式を探す。本問ではK V_j+V_l=V_{j+1}+K V_{l−1}が使える。等比和という見た目だけを根拠にしない。

緩和の下界と配置の構成

発動条件: 数値上の表現を、重ならない部分構造として実現する必要がある。

配置を忘れた硬貨問題で下界を出し、その表現を深さの帰納法で木へ配置して達成を示す。最高点の対称性は深さD+1候補へ圧縮する。

問題固有の要素

完全K分木のサイズ列には交換式とV_H−1=KV_{H−1}が同時にある。前者が数値上の貪欲を正当化し、後者が子部分木への配置を保証する。

別の問題へ持ち帰る視点: 緩和した最適化が正しくても元の構造に配置できるとは限らない。下界の証明と、下界を達成する構成を分ける。

正当性

固定した最高点vの下で、任意の最終連結成分から外れる頂点は、互いに重ならない完全部分木に一意に分かれる。各部分木の親辺を切る必要があり、内部の余分な切断を省いてもよい。従って切断数は削除数Rの硬貨最小枚数以上である。

その最小枚数の表現のうち、大きい額面から見た枚数列が辞書順最大のものを選ぶ。最大額面より小さいV_jがK+1枚以上あれば、交換式のl=jで辞書順を増やせる。またV_jがK枚あり、下位のV_lが一枚でもあれば、同じ式で枚数を増やさず上位枚数を増やせる。枚数が減れば最小性、同じなら辞書順最大性に反する。従って各下位桁は0,…,K枚で、K枚の桁より下は全て0である。

この形のV_0,…,V_{j−1}の合計はV_j未満である。j=1では高々K=V_1−1。帰納的に、V_{j−1}がK枚なら下位は0で合計KV_{j−1}=V_j−1、K−1枚以下なら下位合計≤V_{j−1}−1なので合計≤KV_{j−1}−1<V_j。よって最上位額面の枚数は必ずfloor(R/額面)、余りも同じ形となり、この最小表現は貪欲そのものである。額面が1だけの場合も自明に成立する。

深さHの木ではR≤KV_{H−1}。q=floor(R/V_{H−1})個の子を落とし、q=Kなら余り0。q<Kなら余りr<V_{H−1}を残った一つの子へ配置し、その子の根を残す。深さ0のR=0を基底に帰納すると、貪欲で選んだ部分木は全て互いに素に配置でき、残った木はvを含む連結成分でサイズXとなる。従って硬貨下界を達成できる。任意の解の最高点深さは列挙範囲にあるため、親辺費用を含む全hの最小が答え。

実装上の注意

  • V_iは再帰式でDまで正確に求める。公式制約でV_D≤10^18なので、積KV_iも次のV_{i+1}−1以下である。不要な次の段を計算しない。
  • H=0の硬貨ループは空。X=V_Hなら削除費用0。h=0だけは親辺費用を加えない。
  • 本文の木への配置は証明用であり、実装で頂点やq個の部分木を展開しない。除算一回で枚数qを数える。

復習の核

  • 階層サイズの見た目から貪欲を断定せず、枚数を増やさない交換式を探す。
  • 硬貨としての下界と、部分木として置ける証明を分ける。
  • q=Kでは余りが必ず0、q<Kでは一つの子だけへ余りを押し込める。

計算量と制約

時間

O(D²)、D+1の開始subtree候補とD種類のgreedy差分。

空間

O(D)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All values in the input are integers.; 1 \le T \le 100; 1 \le D; 2 \le K; \displaystyle 1 \le X \le \sum_{i=0}^{D} K^i \le 10^{18}

出典

分類・前提・執筆情報

掲載状態: 収録済み

Edge Elimination の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 貪欲法と交換論

    補助タグ: 有界全列挙・有限case分解

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 交換論から選択順を導く

    • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

    先に読む単元:

    この解説で扱わないこと:

    • 対称操作による状態の正規化。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題