ABC 231 G — Balls in Boxes

考察

箱 i が選ばれた回数を X_i とすると得点は ∏(A_i+X_i) であり、積を展開すれば各項の期待値へ線形性を適用できる。

相異なる m 箱の X_i の積の期待値は箱の選び方に依存せず、操作時刻を各箱へ一つ割り当てる組合せだけで決まる。

棄却する候補: K 回後の各箱の球数分布を多次元 DP で求め、配置ごとの積を確率付きで足す。

K が 10 億で箱数も 1000 あり、球の配分状態を列挙できない。

採用する候補: 積を A と X の選択部分集合で展開し、A の基本対称式と、相異なる箱の選択回数積の共通期待値を次数別に掛け合わせる。

A 側は二次時間の対称式 DP、確率側は falling factorial の一次再帰となり、巨大な K を状態に含めない。

m 個の相異なる箱について ∏X_i を展開すると、同じ時刻に二箱は選べないため有効なのは相異なる m 時刻だけで、期待値は (K)_m/N^m になる。

A の積の部分集合和は ∏(1+A_i z) の係数、すなわち全次数の基本対称式として一度に計算できる。

ランダムな選択回数を含む積を多重線形展開し、定数 A の基本対称式と multinomial 分布の相異なる座標に対する階乗モーメントを次数ごとに合成する。

e_t=[z^t]∏(1+A_i z) を e_0=1 から、A_i ごとに t を降順に e_t+=A_i e_{t−1} と更新する。答えは

Σ_{m=0}^{min(N,K)} e_{N−m}·(K)_m/N^m

である。m個の X を選ぶため、残る A の次数は N−m。w_0=1、w_{m+1}=w_m(K−m)/N とすれば各重みを順に求められる。K=0なら m=0 だけが残り元の積 ∏A_i と一致する。

典型の発動条件

積の展開と期待値の線形性

発動条件: 相関する確率変数の積でも、各変数が一次式として一度ずつ現れるとき。

各因子から A_i または X_i を選ぶ部分集合へ展開し、単項式ごとの期待値を足す。

基本対称式 DP

発動条件: 全ての部分集合について要素積を選択個数別に合計したいとき。

多項式 ∏(1+A_i z) の係数を一次元 DP の降順更新で求める。

問題固有の要素

X_i 自体は互いに独立でないが、各操作で選ばれる箱の対称性と時刻の独立性により、相異なる箱集合の積期待値は集合サイズだけに依存する。

別の問題へ持ち帰る視点: 交換可能な確率変数では独立性を求める前に、必要なモーメントが添字集合の大きさだけで決まる対称性を探す。

正当性

積の展開は、各箱で定数項か選択回数を取る全場合を一度ずつ含む。相異なる箱に対応する操作時刻も相異なる必要があるため、各項の重みは階乗モーメントと一致する。箱数だけで重みをまとめても元の期待値の和は変わらない。

実装上の注意

  • (K)_m は m>K で 0 になり、m を一つ増やすごとに K−m+1 と N の逆元を掛けて更新する。
  • 次数 m の X を選ぶ項には次数 N−m の A 基本対称式を対応させ、添字を逆に取り違えない。

復習の核

  • 確率変数の積が難しいときも、各因子が定数+変数ならまず全単項式へ展開し、線形性が使える形を探す。
  • 選択回数の積では、時刻添字が一致した項が 0 になるかを調べ、相異なる時刻の falling factorial を導く。

計算量と制約

時間

O(N²)、基本対称式DPと次数momentの合成。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 1000; 1 \leq K \leq 10^9; 0 \leq A_i \leq 10^9

出典

分類・前提・執筆情報

掲載状態: 収録済み

Balls in Boxes の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

    補助タグ: 生成関数による組合せ構造の符号化 法上の四則演算・高速累乗・逆元

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題