CF #956 E. I Love Balls

↓問題リンク

codeforces.com

問題概要

個のボールがある．それぞれには点数 が与えられている．また，番号 1 から のボールはSpecialである．

Alice と Bob が次の行動を繰り返す．

• ボールを等確率でランダムに 1 つ選び，それを取り除く．取り除いたボールに書かれた点数を得る．ボールがSpecialなら次も自分の手番で，そうでないならもう一人に手番を回す．

それぞれの点数の期待値を求めよ．

解き方

ゼロサムゲームなので，Aliceのが求まれば合計から引くことでBobのがわかる．よってAliceを求める．

ランダムに1つ選ぶのではなく，事前にシャッフルしてから前から順番に取るとしてもよい．よって，ボールの並べ方 通りに対する総和を求めてから で割ればよいことになる．

主客転倒をする．ボールの並べ方を固定した時，ボール i の点数はどちらが得ることになるか？

Specialでないボールが当たるたび交代するので，ボール i を Alice が得る必要十分条件は，ボール i より前にあるボールのうち，Special でないものの個数が偶数個という条件になる．

よって，それぞれのボールについて，すべての並べ方のうち，Specialでないものが前に偶数個並ぶものの個数を求められれば良いことになる．ここで，この個数は対象となるボール 自体が Special であるかのみに依存するので，それぞれの場合を考えればよい．そして，これらは前に並ぶ Special でないボールの個数を固定すると簡単な二項係数の数え上げになるので，それぞれ で計算できる．

あとは，各ボールが Special かどうか考えて，それぞれの係数をかければよい．計算量は全体で ．