ABC 440 F — Egoism

考察

各馬の満足度に掛かる係数は、先頭なら 1、それ以外なら直前の馬の B_i であり、1 または 2 に限られる。したがって全馬を係数 2 とした 2ΣA_i を基準に置き、係数 1 になる馬の A_i の総和を最小化すればよい。

B_i=1 の馬の頭数を z とする。末尾が B_i=1 でない並びは巡回移動して満足度を下げずに末尾を B_i=1 にできるため、0<z<N では係数 1 の馬をちょうど z 頭とする場合だけ調べれば足りる。

0<z<Nのとき、係数1にするz頭の集合の必要十分条件は「B=2の馬を少なくとも一頭含む」ことである。

この集合条件の両方向を確認する。必要性は並びの最初のB=2の馬に注目すればよい。先頭なら係数1、それ以外なら直前はB=1なのでやはり係数1になる。

十分性には並びを具体的に作る。選んだz頭を希望係数1、残りを希望係数2とし、H_{i,j}={Bがi、希望係数がjの馬}と定義する。B=1の頭数と希望係数1の頭数がともにzだから、|H11|+|H12|=|H11|+|H21|、すなわち|H21|=|H12|。集合はB=2を含むのでこの共通数をk≥1とする。

「H21から一頭 → H22全頭 → H12から一頭 → 残りのH21とH12を交互にk−1組 → H11全頭」の順に並べる。先頭のH21は係数1。そのB=2を受けるH22と最初のH12は係数2になる。以後はH12のB=1の直後にH21、H21のB=2の直後にH12を置くため各希望係数が合う。最後のH12以後に置くH11は全て係数1で、末尾は必ずB=1になる。H22またはH11が空、k=1でもこの説明は成立する。全馬を一度ずつ使うので、任意の適合集合を実現できた。

採用する候補: 並び順の最適化を、A_i の小さい z 頭を選ぶ問題へ言い換える。値 A ごとの B=1 の個数、B=2 の個数、A の総和をセグメント木に持ち、点更新後に z 番目の値と B=2 の最小値を順序統計として求める。

集合の必要十分条件まで示せば並び順を状態に持たずに済み、各更新を値域上の O(log M) 個の節点だけで処理できる。

棄却する候補: 各クエリ後に全馬を A_i の昇順へ並べ直し、先頭から z 頭と B_i=2 の候補を走査する。

一回の更新ごとに N 頭を整列または走査すると、N,Q がともに 2×10^5 の制約では間に合わない。

棄却する候補: 馬を一頭ずつ置く貪欲法として、直前の B_i と次の A_i の積がその場で最大になる馬を選ぶ。

現在の選択が次の係数と B_i=2 を含むという全体条件を同時に変えるため、局所的な積の大小から最適な並びは決められない。

z=0 なら先頭だけが係数 1 なので答えは 2ΣA_i−min A_i、z=N なら全員が係数 1 なので答えは ΣA_i となり、中間の場合と分離できる。

0<z<N では A_i が小さい z 頭の集合 T に B_i=2 が含まれれば T が最適である。含まれなければ、T 内の最大 A_i を全体で最小の B_i=2 の馬へ置き換えるのが最小の修正になる。

以上の構成により、集合の最小損失は実際の並びで達成できる。

値 A を添字とするセグメント木に B=1 の個数 c_1、B=2 の個数 c_2、A の総和 s を保持する。更新前の馬を削除して更新後の馬を追加し、0<z<N なら累積個数が z 以上となる最小値 r を木上で探索する。A≤r の集計から余分な同値要素を引いた z 個分の和を求め、そこに B=2 がなければ値 r の一頭を最小の B=2 へ交換し、最後に 2ΣA_i からその和を引く。

区間要約は(c_1,c_2,s)、合成は三成分それぞれの加算、単位元は(0,0,0)。境界rまでにB=2があれば、z個の選択にその一頭を含められる。特にB=2が境界rにしかない場合は、同額rの選択枠へ優先的に一頭入れれば和は変わらない。B=2がr以下に一頭もない場合だけ交換補正を行う。

典型の発動条件

基準値からの差分による目的関数変形

発動条件: 各要素の係数が少数の値しか取らず、最大の係数を全要素へ与えた仮想的な総和から損失だけを最小化できる場合。

係数をすべて 2 とした 2ΣA_i を基準にし、係数 1 を割り当てる実現可能な集合の A_i 総和を最小化する問題へ変換する。

セグメント木上の順序統計

発動条件: 値の多重集合が点更新され続け、k 番目の値、先頭 k 個の総和、条件付き最小値を毎回高速に求めたい場合。

A の値域に個数と総和を載せ、累積個数が z に達する境界 r、z 個の総和、B=2 の最小 A を木上の降下で取得する。

問題固有の要素

各馬が受ける係数の集合を先に特徴付けると、順列の自由度は「B_i=2 の馬を一頭以上含む z 要素部分集合」という静的な条件へ潰れる。

別の問題へ持ち帰る視点: 前後関係を直接最適化しにくいときは、各位置が受ける係数の多重集合と、その割り当てを実現できる条件を先に求める。

正当性

0<z<Nでは最後のB=1の直後から巡回移動すると、旧先頭の係数は1から2へ変わり、他の係数は変わらないので満足度を下げずに末尾B=1へ正規化できる。この並びの係数1はちょうどz頭で、最初のB=2は必ずその集合に入る。逆に適合集合では|H21|=|H12|≥1であり、H21一頭、H22全頭、H12一頭、残りのH21/H12の交互列、H11全頭という構成が希望係数と末尾B=1を同時に実現する。従って係数1の集合の損失最小化と元の順列最適化は同値。小さいAのz頭にB=2を含められればその和が下界を達成し、含められなければ選択内の最大値を最小B=2へ交換するのが最小損失である。同値境界ではB=2を優先して選べる。z=0なら先頭だけ係数1で2ΣA−min A、z=Nなら全て係数1でΣAとなる。個数と和の要約は加算で結合でき、順位境界と条件付き最小値からこの最適損失を復元できる。

実装上の注意

  • A_i の重複を許すため、境界値 r の個数を丸ごと足さず、累積個数の超過分だけ r を総和から引いて正確に z 頭を選ぶ。
  • 点更新では旧い (A_i,B_i) を木から削除してから新しい組を追加し、全体和と z も同じ順序で同期させる。
  • z=0 と z=N を中間式へ流さず、総和や 2 倍した値は 64 bit 整数で保持する。

復習の核

  • データ構造を見る前に、係数 1 の集合について必要性だけでなく任意の適合集合を実現する並べ方まで説明できているかを確認する。
  • A_i が同値の馬を多数含む例と、更新で z が 0、1、N−1、N をまたぐ例を用意し、境界 r の補正と場合分けを重点的に検査する。

計算量と制約

時間

構築O(N+M)、Q更新O(Q log M)、MはAの管理値域。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 1 \leq Q \leq 2 \times 10^5; 1 \leq A_i \leq 10^6 (1 \leq i \leq N); B_i is 1 or 2. (1 \leq i \leq N); 1 \leq W_k \leq N (1 \leq k \leq Q); 1 \leq X_k \leq 10^6 (1 \leq k \leq Q); Y_k is 1 or 2. (1 \leq k \leq Q); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 区間monoid要約

    補助タグ: 貪欲法と交換論

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

    学習の位置

    体系上の位置: 区間monoid要約

    • 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題