ABC 391 E — Hierarchical Majority Vote

考察

長さ3のmajority nodeを反転するには、現在の多数派を構成するchildのうち必要数を反転すればよい。葉変更の影響は完全な三分木上を上へ伝わる。childが3つ同値なら安い2つを、2対1なら多数派側の安い1つを反転すれば親のmajorityが変わる。leafの反転costは1。内部nodeでは現在多数派と同じ値のchildだけが親反転へ寄与する候補になる。同値3個なら一個だけ反転しても2対1で親値は変わらないため、二つの最小costを足す。

採用する候補: 各三分木nodeの現在値と、その値を反転する最小leaf変更数をbottom-up DPする

各nodeの最適変更は三childの値・costだけで局所的に決まり、全node数O(3^N)を一度処理すればroot答えが得られる。

棄却する候補: leaf subsetを変更数順に列挙して最終majorityを再計算する

leaf数3^Nに対するsubsetは二重指数的であり、階層構造を利用していない。

leafの反転costは1。

文字を(value,cost=1)のleafとし、3要素ずつまとめる。親valueをmajorityで求め、多数派childが2個ならcostのmin、3個ならcostの小さい2個の和を親costとする。N層後のcostを出す。

典型の発動条件

tree DPによる局所感度

発動条件: 階層的な集約関数の最終出力を反転する最小入力変更数を求めるとき。

各nodeに現在値と反転costを持たせる。

majority gateの最小cut

発動条件: 奇数個majorityの出力を変えるcostがchild別に異なるとき。

現多数派を過半数未満にする最安child集合を選ぶ。

問題固有の要素

最終bitだけを目標にしても、各subtreeでは「現在値を逆にするcost」一つだけで上位の全判断に十分である。

別の問題へ持ち帰る視点: Boolean回路の出力反転最小costでは、gateごとに出力0/1の最小costまたは現在値反転costをbottom-upする。

正当性

現在多数派が二子なら、その二子の一方を反転することが必要十分で最小費用を選ぶ。三子なら二子以上の反転が必要で最小二費用を足す。子部分木は互いに素だから費用加算が可能。葉費用1から帰納的に全頂点の最小反転費用が正しい。

実装上の注意

  • 三つ全同値と2対1を分け、多数派でないchildのcostを誤って選ばない。3^N長を整数で正しく構築する。

復習の核

  • N≤3で全leaf変更subsetを列挙し、3同値・2対1が各層で混ざるcaseのvalue/costをnodeごとに比較する。

計算量と制約

時間

葉数 L=3^N。三分木全体も O(L) 頂点なので O(3^N)。

空間

各段を縮める配列で O(3^N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: N is an integer with 1 \leq N \leq 13.; A is a string of length 3^N consisting of 0 and 1.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Hierarchical Majority Vote の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 根付き木DP・部分木集約

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

      主タグ: 根付き木DP・部分木集約

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

      学習の位置

      体系上の位置: 根付き木DP・部分木集約

      • 根付き木で子側の状態を合成し、部分木または木全体の値を求められる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題