ABC 215 G — Colorful Candies 2

考察

選んだ K 個の飴に含まれる色数は、各色について「その色が一個以上現れた」という指示変数の総和である。

全 N 個中に n_i 個ある色 i が一度も選ばれない確率は C(N−n_i,K)/C(N,K) であり、出現確率はその余事象である。

棄却する候補: 各 K と各色の組について、その色が含まれる選び方を個別に計算して期待値へ加える。

色数も K の種類数も N に達し得るため、全組を処理すると二乗規模になる。

採用する候補: 同じ出現個数 x を持つ色を a_x 個にまとめ、各 K に対して正の a_x だけから出現確率を加算する。

期待値への寄与は色名でなく頻度だけで決まり、異なる正頻度の種類数は N の平方根程度に抑えられる。

色どうしの出現は独立でなくても、期待値の線形性により各色の出現確率を単純に足せる。

正の頻度 x が互いに異なるなら、その最小総和は 1+2+… と増えるため、存在する頻度値の種類数は少ない。

色数を指示変数の和へ分解し、余事象の二項係数比を頻度別に集約して、正頻度の疎性を利用しながら全ての K の期待値を求める。

典型の発動条件

指示変数と期待値の線形性

発動条件: 異なる種類の出現数の期待値を求め、種類間の依存関係が複雑なとき。

各色が一度以上選ばれる指示変数を置き、その出現確率を色ごとに加える。

頻度による同型項の集約

発動条件: 各種類の寄与が名前ではなく、その種類の出現回数だけで決まるとき。

頻度 x の色数 a_x を数え、同じ二項係数比を a_x 倍して一括加算する。

問題固有の要素

頻度ごとの配列は長さ N でも、正の異なる頻度は合計が N 以内という制約から平方根程度しか存在しない。

別の問題へ持ち帰る視点: 値別グループの走査が一見二乗でも、正の異なる値の総和制約から非零グループ数を評価できることがある。

正当性

色数の指示変数分解は各選択集合に対して成り立つため、色間の依存によらず期待値を加算できる。同じ頻度の色は同じ確率を持つので、頻度別の重み付けもこの和を変えない。

実装上の注意

  • K>N−x のとき C(N−x,K) は 0 と扱い、配列外の階乗を参照しない。
  • 色の値そのものは大きくてもよいため、連想配列またはソートで各色の個数を求め、さらに頻度別の色数へ圧縮する。

復習の核

  • 異なる種類数の期待値では、分布全体を追う前に各種類が現れたかという指示変数へ分解する。
  • 同じ頻度の種類が同一式へ寄与するなら、頻度の種類数を総和制約から評価して反復回数を見積もる。

計算量と制約

時間

O(N√N)、存在する正の頻度種類数O(√N)、各Kで頻度別和。

空間

O(N)、階乗と頻度群。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5 \times 10^4; 1 \leq c_i \leq 10^9; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Colorful Candies 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

    補助タグ: 組合せ係数・数え上げ 法上の四則演算・高速累乗・逆元

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題