ABC 252 F — Bread

考察

切るたび、その時点のパン全体の長さを払う。入力順に切る方法では同じ長い部分を何度も費用へ加えてしまう。操作を逆にすると、最終片を二つずつ併合し、和の長さを費用として払う問題になる。最終的な片の左右順は指定されないので、任意の併合二分木を逆向きの切断として実現できる。

併合木の葉に最終片の長さwを置き、内部節点に子の重みの和を置く。費用は内部節点重みの和であり、各葉の重みが祖先の数だけ加わるためΣw×深さにも等しい。したがって、小さい片ほど深い位置に置く方がよい。この式から「最小二片を最深の兄弟にできるか」を考えると、次の交換証明と縮約によりHuffman法が導ける。

先に余りR=L−ΣAの扱いを決める。R>0なら未使用片も葉に必要だが、複数の余り葉に分ける必要はない。ある切断木で余り葉の最浅深さをdとし、その葉に余り総量Rを集める。元の余り寄与ΣB_j d_jはRd以上なので費用を増やさない。重み0になった他の余り葉を削除し、子が一つになった節点を縮約すれば、残る全葉の深さも増えない。よって余りを一片にした合法二分木で元の費用以下を達成できる。R=0なら余り葉は一枚も加えない。

全葉を最小ヒープへ入れる。最小二重みa,bを取り出し、a+bを費用へ加えてヒープへ戻す。一片まで繰り返せばよい。単に「今回の併合が安い」だけでは大域最適性は言えず、最深の兄弟への交換と、二葉を和の一葉へ縮約した残りが同じ問題になることが核心である。

典型の発動条件

Huffman法の交換と縮約

発動条件: 任意の二つを併合でき、併合費用が二重みの和で、全体を一つにまとめたい。

費用を葉重み×深さに写す。最小二重みを最深の兄弟へ交換し、和の一葉へ縮約して最適部分構造を示す。隣接片だけを併合する制約が付くと葉の交換が自由でなく、この証明は使えない。

未指定部分の正規化

発動条件: 総量は固定されるが、その一部の最終分割は自由である。

自由な葉の重みを最浅葉へ集め、不要葉を削除することで費用が増えないことを示す。単に操作回数が減るだけでは、重み付き費用の比較にならない。

問題固有の要素

未指定部分も最終的には一つの片として切り分けられるため、その長さを補助片として加えないと元のパン長Lへの併合にならない。

別の問題へ持ち帰る視点: 分割費用が生成する二片の合計なら、逆向きの最適併合としてHuffman構造を疑う。

正当性

まず任意の切断木の費用はΣw_i d_i。複数の余り葉があれば、最浅の余り葉の深さdへ全余りRを集めると、余り寄与はΣB_j d_jからRdへ減る。零になった余り葉を取り除き単子節点を縮約すると他の葉の深さも減るので費用は増えない。逆にR一片を含む併合木は合法な切断に戻せるため、余り一片への正規化で最適値は変わらない。

固定した葉重みの最適な全二分木を取る。最大深さDの葉の兄弟は必ず同じ深さの葉である。兄弟が内部節点ならさらに深い葉が存在して矛盾するからである。最小二重みa≤bをこの兄弟位置へ順に交換してよい。例えば重みaが深さd≤D、交換相手w≥aが深さDなら費用差はaD+wd−(ad+wD)=(w−a)(d−D)≤0。二回目も同様で、既に置いたaを動かさず残り最小のbを置ける。従って最小二重みが兄弟となる最適木が存在する。

この二葉を重みa+bの一葉へ縮約すると、その祖先への寄与は変わらず、費用はちょうどa+bだけ減る。縮約木が残る重み集合の最適木でなければ、より安い木へ置き換えて元の最適性に矛盾する。逆に残りの最適木の葉a+bを二葉へ展開すると、費用にa+bを足して元の合法木を得る。従ってOPT(S)=a+b+OPT((S−{a,b})∪{a+b})。一葉の費用0を基底に葉数の帰納法で、Huffman法が全体最適となる。

実装上の注意

  • 長さと総費用は64ビット整数で保持し、ΣA=Lなら長さ0の補助片は追加しない。ヒープが一要素になるまでの併合回数を確認する。

復習の核

  • 併合費用をΣ葉重み×深さへ数え直すと、安全な交換が見える。
  • 最小二葉を最深の兄弟へ置けることと、縮約後にも同じ最適化になることを組にして証明する。
  • 余り一片への正規化は貪欲とは別に証明する。葉順固定・隣接併合には自由交換を適用しない。

計算量と制約

時間

O(N log N)、余りを含む片数≤N+1。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; 1\leq A_i\leq 10^9; A_1+A_2+\cdots+A_N\leq L\leq 10^{15}; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

主題
追加で学ぶ技能
    なし
    既習技能
    • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 貪欲法と交換論

    補助タグ: priority queue・best-first列挙

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

    学習の位置

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

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

    先に読む単元:

    • priority queue・best-first列挙 — 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題