ABC 417 F — Random Gathering

考察

一操作後、区間[L,R]の各plateの期待stone数は、操作前区間総和をlenで割った同じ値になる。選択位置とstone数は相関しても、期待値の線形性により総和の期待値だけでよい。

区間外の期待値は変わらないため、必要操作は現在期待値配列へのrange sum queryと、その区間全体へのconstant assignmentである。

採用する候補: range sumとrange assignment lazy propagationを持つsegment treeで期待値配列をオンライン更新する

棄却する候補: 各操作で[L,R]の全要素を走査して合計し同じ期待値を書き込む

区間長がNの操作がM回あり得てO(NM)となる。

leafをA_iでbuildする。各(L,R)でrange sum sを取得し、v=s·inv(R-L+1) mod 998244353を計算してrange assignする。全操作後に各point value、またはtreeを展開したleafを順に出力する。

典型の発動条件

期待値の線形性

発動条件: ランダムに全量を一地点へ集める操作の各位置期待値を追うとき。

選択indicatorと区間総量の積を条件付けし、期待総和を均等配分する。

lazy segment tree

発動条件: range aggregate取得とrange全代入が混在するとき。

node sumとoptional assignment tagを持ち、区間長倍でapplyする。

問題固有の要素

ランダム過程の分布や共分散を保持せず、操作が線形なので期待値vector自体へ同じ確定range平均操作を適用できる。

別の問題へ持ち帰る視点: 確率操作が状態の線形変換なら、期待値にも同じ線形変換を施し、deterministic data structureで処理する。

正当性

実際の配置は一皿に全stoneが集まるが、各jが選ばれる確率1/lenなのでE[X'_j]=E[ΣX_k]/len=ΣE[X_k]/lenとなる。 lazy tagは加算ではなく上書きで、node区間長lenNodeに値vをassignしたときsum=v·lenNodeへ置換し、後のtagが前のtagを上書きする。 各操作でsum=prod(L,R)、v=sum/(R-L+1)を求めrange assign vとし、全体O((N+M)log N)で処理できる。

実装上の注意

  • assignment値0とtagなしを別flagで区別する。区間長の逆元をmodで計算し、half-open indexとnode長を揃える。

復習の核

  • 長さ1、全区間、重なる区間、期待値0のassignmentを小Nの全乱数列挙と比較する。

計算量と制約

時間

長さ逆元前計算O(N)、操作O(M log N)、葉展開O(N)。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1\le N\le2\times10 ^ 5; 1\le M\le2\times10 ^ 5; 0\le A _ i\lt998244353\ (1\le i\le N); 1\le L _ i\le R _ i\le N\ (1\le i\le M); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 区間更新を要約へ作用させる

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

    主タグ: 遅延評価する区間作用

    補助タグ: 寄与の数え上げと順序交換 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 区間更新を要約へ作用させる

    • 更新作用の合成順と要約への適用を定義し、遅延評価で保てる。

    先に読む単元:

    • 局所寄与へ分解して集計順を交換する — 数える対象を一意に固定し、その対象を含む選択や組の個数へ集計順を交換する。要素・組・区間・値のどれを固定すると重複が消えるかを比較する。
    • 法上の四則演算・高速累乗・逆元 — 剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算や確率を計算する。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 過去の版の保存・rollback・構造共有。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題