kmjp's blog

競技プログラミング参加記です

Codeforces ECR #064 : F. Card Bag

もう今年も半分超えてしまいましたね…。
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が割と厄介なせいか解いた人が少なかったね。