もう今年も半分超えてしまいましたね…。
https://codeforces.com/contest/1156/problem/F
問題
N枚のカードがあり、それぞれ数値が書かれている。
N枚から1枚ずつカードを取っていくことを考える。
残されたカードのうち、各カードを取る確率は等しいとする。
その際、2枚目以降は毎回以下の判定が入る。
- 直前にとったカードより値が小さいと負け
- 直前にとったカードと値が一致すると勝ち
- 直前にとったカードより値が大きいなら継続
このゲームで勝つ確率を求めよ。
解法
取ったカードの値が昇順である場合、ゲームは続く。
f(n,k) := 値がn以下のカードをちょうどk枚取ったとき、まだゲームが続いている確率
とする。f(0,0)=1から初めて、遷移を考えていこう。
今f(n,k)からの遷移を考える。(n+1)の値のカードがC枚あるとする。
- n+1の値のカードを取らない場合: f(n+1,k) += f(n,k)
- n+1の値のカードを1枚だけ取る場合、ゲームは続行する。これは残された(N-k)枚中、(n+1)の値を持つC枚のいずれかを取る確率なので: f(n+1,k+1) += f(n,k)*C/(N-k)
- n+1の値のカードを2枚だけ取る場合、ゲームは勝利する。これは残された(N-k)枚中、(n+1)の値を持つC枚のうち2枚を確率なので: f(n,k)*Comb(C,2)/Comb(N-k,2)だけ解に加算する。
int N; ll mo=998244353; int C[5050]; ll from[5050]; ll to[5050]; ll ret; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll comb(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll modpow(ll a, ll n=mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; cin>>N; FOR(i,N) { cin>>x; C[x]++; } from[0]=1; FOR(i,5001) if(C[i]) { //take0 memmove(to,from,sizeof(to)); //take1 for(j=0;j<=5000;j++) if(from[j]) { (to[j+1]+=from[j]*C[i]%mo*inv[N-j])%=mo; if(C[i]>=2) (ret+=from[j]*comb(C[i],2)%mo*modpow(comb(N-j,2)))%=mo; } swap(from,to); } cout<<ret<<endl; }
まとめ
これはECRのFにしては難しくない問題だと思ったけど、D,Eが割と厄介なせいか解いた人が少なかったね。