CF 626 D - Jerry's Protest
問題
問題概要
Harryを記録係として、AndrewとJerryは2人でゲームをする。ゲームは3ラウンドで構成され、ラウンドごとに以下のことを行う:
正の整数が書かれたボールが個入った袋からAndrewとJerryはボールを1個ずつ取り出し、その数字を見ずにHarryに渡す。そして、大きい数字を引いていた方に1ポイントが入り、ボールは袋に戻す。
最後に2ポイント以上持っていたものが勝ちである。また、袋の中に入っているボールに書かれている正の整数はどれも異なるので引き分けにはならない。いま、ラウンド1,2ではAndrewが勝ち、ラウンド3ではJerryが勝ってゲームが終了した。Jerryはこのゲームのルールに不満で、3回の数字を合わせた合計は自分が勝っているはずなのに、ゲームには負けてしまうと言っている。
このような(ラウンド1,2ではAndrewが勝ち、ラウンド3ではJerryが勝った)状況において、3回の数字の合計がAndrewよりもJerryの方が大きくなる確率を求めよ。
アイデア
まず、問題文の原文でも強調されているように、各ラウンドごとにボールを戻すので3回のラウンドはそれぞれ独立に考えることが出来る。そこで、勝つ場合において、数字にどれくらいの差があるのかというものを全ての勝ちパターンにおいて列挙しておく。具体的には、ボールの値をソートしておいて、を全て計算して数え上げておく。このとき、ボールの値の上限が5000なので、差の上限は4999になる。
これを利用すると、2勝する時の数字の和はどのようになっているのかという場合の数を簡単に列挙することが出来る。独立なので、単純に1回目と2回目の結果を掛け合わせるだけである。それをコード内では配列dpに保存してある。
そして最後に、Jerryが1勝してこの数字を上回ることの出来る場合の数は、始めに数えた1回分の勝利に対するものよりも配列dpのindexが小さい部分の場合の数に相当するので、それを掛けて足し合わせることでそのような場合の数を列挙できる。最後に確率を求めるために全体からその値を割ることで答えが求められる。
ボールの値の制約を利用して解くべき問題だった。勝ちパターンを列挙するところまではなんとなく考えたけど、そこから計算量をどうしても落とせなかった。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(i=0;i<n;++i) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define mp make_pair #define pb push_back #define fi first #define sc second int main(int argc, char const *argv[]) { long i,j; long n; cin >>n; std::vector<long> a(n); rep(i,n) cin >>a[i]; sort(a.begin(),a.end()); //勝つときの差を列挙して場合の数をカウント ll ct[5000]={0}; rep(i,n){ rep(j,i){ ++ct[a[i]-a[j]]; } } //2勝するときの数の場合の数 ll dp[10000]={0}; rep(i,5000){ rep(j,5000){ dp[i+j]+=ct[i]*ct[j]; } } double ans=0; //最後1回で前の2回分を取り返せる場合の数 rep(i,5000){ rep(j,i){ ans+=(double)ct[i]*dp[j]; } } ll N=n*(n-1)/2; printf("%.20lf\n",ans/N/N/N); return 0; }