ABC 242 Ex — Random Painting

考察

抽選済みの異なる区間集合 S がまだ全盤面を覆わない間、次に S 外の区間が初めて出るまでの待ち時間は成功確率 (M-|S|)/M の幾何分布で、期待値は M/(M-|S|) である。

異なる区間が i 種類集まった時点の集合は全 C(M,i) subset に対称であり、そのうち union が [1,N] でない割合だけ、その stage の待ち時間が完了前に発生する。

採用する候補: 被覆する i-subset 数 f(i) を interval-union DP で数え、各 i<M の非被覆割合 (C(M,i)-f(i))/C(M,i) に stage 待ち時間 M/(M-i) を掛けて足す。

無限回の確率過程を distinct-set size ごとの有限な期待値和へ変え、残る組合せ数を区間構造で計算できる。

棄却する候補: 抽選された ball の列または2^M個の既出集合を状態に期待値 DP を行う。

同じ ball の反復で列は無限、distinct subset も M=400 に対して指数個ある。

区間を (L,R) 昇順に処理すると、選択区間の union が gap なしの prefix [1,j] である状態だけを持てる。新 interval は j<L-1 なら選べず、重なるなら右端を R へ伸ばし、既に含まれるなら j を保つ。

f(i)=dp[N][i] が i 個で全被覆する subset 数となり、期待値は i=0..M-1 の stage 寄与の和である。

interval を L,R 順に sort し、dp[j][k] を選択 union が [1,j]、選択数 k の subset 数とする。空集合は dp[0][0]=1、他は0。区間 (L,R) ごとに next=dp として非選択を移し、旧 dp の j≥L−1 から next[max(j,R)][k+1]+=dp[j][k] と選択を加える。全てを加えてから dp=next にする。同じ座標の区間も抽選される種類は別なので、一つずつ処理する。f(k)=dp[N][k] を得た後、Σ_{k=0}^{M-1}(1-f(k)/C(M,k))·M/(M-k) を法998244353で計算する。

典型の発動条件

coupon stage による期待値分解

発動条件: 復元抽選で異なる種類が増え、ある集合性質を初めて満たすまでの回数を求めるとき。

distinct 集合サイズごとの滞在確率と、次の新種類までの幾何分布期待値を掛けて足す。

区間 union の prefix DP

発動条件: 区間を選んだ union が gap なしで始点からどこまで覆うかを数えたいとき。

左端順に処理し、covered right endpoint と選択数を状態にする。

問題固有の要素

抽選順を直接追わず、「異なる区間が i 個そろった stage でまだ被覆していないか」へ期待値を分解すると、順序確率と subset 数え上げが分離する。

別の問題へ持ち帰る視点: with-replacement 過程では、distinct set が増える瞬間だけを埋め込んだ過程として観察する。

正当性

初出区間がk種類に達した時点の集合は全k-subsetに一様であり、次の未出区間までの待ち時間の期待値はM/(M−k)。まだ被覆しない確率を掛け各stageを足せば完了時間の期待値になる。区間を左端順に処理すると、既にprefixを覆う選択集合にgapを作る区間は後の区間ではそのgapを埋められないため棄却してよい。空集合から各区間の非選択と選択を旧配列だけから次配列へ送るので、同じ区間を二度使わず各subsetを一度数える。端jと選択数kのDPで全被覆subset数f(k)を得て、Σ(1−f(k)/C(M,k))M/(M−k)を計算すれば正しい。

実装上の注意

  • 期待値和は M−k が0になる k=M を含めない。M<998244353なので、この範囲の M−k と C(M,k) は非零である。
  • 二配列なら旧 dp だけを読む。in-place にする場合は選択数 k を降順の外側ループにし、各 k の全 j から k+1 へ加算する。今回書いた層 k+1 は既に走査済みなので再使用しない。j の降順だけでは、j≥R で端が変わらない遷移を防げない。
  • N=1、M=4、全区間 [1,1] なら f(k)=C(4,k)(k≥1)で期待値は1。j 降順・k 昇順だと [f(0),…,f(4)]=[0,4,6,10,15] へ過大計数する。

復習の核

  • i 個の distinct ball が集まった時の subset が一様であることと、次の新 ball まで M/(M-i) 回かかることを別々に導く。

計算量と制約

時間

O(M²N+M log M)。各区間について被覆端Nと選択数Mを遷移する。

空間

O(NM)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N,M \leq 400; 1 \leq L_i \leq R_i \leq N; For every square i, there is an integer j such that L_j \leq i \leq R_j.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 確率過程・期待値DP

主題
  • 確率過程・期待値DP: 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 確率・期待値DP

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

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

    学習の位置

    体系上の位置: 確率過程・期待値DP

    • 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。

    先に読む単元:

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

    • 二人零和ゲームの勝敗・Grundy数。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題