ややこしめの数え上げをシンプルに書く練習に良い問題.

問題

http://codeforces.com/contest/513/problem/C

オークションを行う. n (2 <= n <= 5) 人の参加者がいる. i 人目の入札額は [l[i], r[i]] の範囲で一様ランダムに決まる. (1 <= l[i] <= r[i] <= 10000) 落札額はセカンドプライス・オークション形式で決まる. つまり, 落札者の次点の入札額が落札額となる. 落札額の期待値を求めよ.

解法

次点者, 次点入札額, 落札者 を固定して確率を計算する.

次点入札額と等しい入札額の参加者が複数いる場合を重複カウントしないよう, 工夫する必要がある.

次点者 snd, 入札額 v, 落札者 fst について考える. このとき, 参加者 i (< snd) の入札額が次点入札額と一致するパターンは既にカウント済みである.

よって, 次の条件を満たす確率を求めれば良い.

• fst の入札額 >= v
• snd の入札額 = v
• その他の入札額 <= v
• ただし, 参加者 i (< snd) については, 入札額が v と等しくない

解答

別解

本番でやった, 長くて汚いけど理解が容易な方法.

落札額 v (1 <= v <= 10000) を固定してループを回す.

n 人の参加者について,

1. 入札額が v 未満
2. 入札額が v
3. 入札額が v より大

の 3 つのステータスを全パターン回す.

各ステータスの人数を cnt1, cnt2, cnt3 とすると, 落札額が v となるのは,

• cnt2 >= 1
• cnt2 + cnt3 >= 2
• cnt3 < 2

を全て満たす場合である. これを満たすパターン全てについて, 確率計算する.

解答: http://codeforces.com/contest/513/submission/9762252