ABC 380 G — Another Shuffle Window

考察

長さ K の窓を shuffle して変わるのは窓内二要素の相対順だけで、窓外との転倒関係は位置ブロックが保たれる。一様 permutation の窓内期待転倒数は K(K-1)/4 である。

採用する候補: 元全体の転倒数から各窓の元転倒数を引き、K(K-1)/4 を足す。窓転倒数は Fenwick tree で削除・追加寄与を更新する。

期待値の線形性で shuffle の分布を窓内 pair の1/2へ集約でき、全窓の転倒数を O(N log N) で走査できる。

棄却する候補: 各窓について K! 通りの並べ替えを列挙し、転倒数を平均する。

K は2×10^5まであり permutation 列挙は不可能で、窓ごとの O(K log K) 再計算も O(NK) になる。

窓内の任意の異なる二要素は shuffle 後の前後が半々なので、値に関係なく各 pair の期待寄与は1/2になる。

左端要素を除くとその要素が左側として作った「より小さい右要素」数を引き、右端要素追加では「より大きい既存要素」数を足す。

Fenwick tree で元 permutation の全転倒数と最初の窓の転倒数を求める。窓を一つずつずらして削除・追加の順位数を反映し、各窓の期待値を足して窓数で割る。

典型の発動条件

期待値の線形性による pair 分解

発動条件: random shuffle 後の転倒数など pair 指示変数の和を扱うとき。

各窓内 pair の確率1/2を独立性なしで加算する。

sliding window inversion

発動条件: 固定長窓の転倒数を全位置で求めたいとき。

Fenwick tree で出入り要素の転倒寄与だけを更新する。

問題固有の要素

shuffle が窓外との相対位置を変えないことをブロック X,Y,Z で分離すると、差分は窓内だけになる。

別の問題へ持ち帰る視点: 期待転倒数は各 pair の確率だけでよく、pair 間の依存を考えなくてよい。

正当性

窓外の要素は窓全体の前か後にあるため、窓の並べ替えでは窓との転倒数総和が変わらない。窓内の各対だけが確率1/2で転倒する。元の窓内寄与を置き換えた値が各窓の期待値であり、それらの平均が求める期待値になる。

実装上の注意

  • 窓内期待転倒数はC(K,2)/2=K(K−1)/4。法上ではK(K−1)·inv4、またはK(K−1)·inv2·inv2で計算する。inv2を一回だけ掛けると二倍になる。
  • 窓数W=N−K+1とし、最終値はI_total−(Σ I_window)·inv(W)+K(K−1)·inv4。窓数による平均は元の窓転倒数の総和へ掛ける。
  • 左要素を除くときは残る値のうち厳密に小さい個数を引き、右へ追加するときは既存の厳密に大きい個数を足す。K=1なら元の転倒数、K=NならN(N−1)/4になる。

復習の核

  • 窓内・窓外の六種類の pair を分類し、どの関係だけが random 化されるかを先に確認する。

計算量と制約

時間

O(N log N)、全転倒数とK窓の追加削除BIT。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 1 \le K \le N \le 2 \times 10^5; P is a permutation of (1,2,\dots,N).

出典

分類・前提・執筆情報

掲載状態: 収録済み

Another Shuffle Window の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

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

    主タグ: 寄与の数え上げと順序交換

    補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計 法上の四則演算・高速累乗・逆元 尺取り法・sliding window

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

    学習の位置

    体系上の位置: 局所寄与へ分解して集計順を交換する

    • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

    先に読む単元:

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

    • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題