Codeforces ECR #095 : E. Expected Damage

割と難しめな回っぽい。
https://codeforces.com/contest/1418/problem/E

問題

N匹の敵を倒すことを考える。
各敵eはパラメータとして攻撃力D[e]を持つ。
その際、耐久力A、防御力Bを持つ盾を使い敵を倒していく。

敵eと戦うとき、

• A=0ならダメージD[e]を受ける
• A＞0の場合
  • D[e]＜Bなら何も起きない
  • D[e]≧BならAが1減る

盾のパラメータA,Bが複数与えられる。
もしN匹の登場順がN!通り等確率で生じるとき、全敵を倒すまでの受けるダメージの期待値を求めよ。

解法

まず敵をD[e]がB未満かB以上かで分ける。
B以上の敵とA回戦った以降、無条件でダメージを受けると考えよう。
また、その際受けるダメージは、登場順が等確率であることから

• D[e]がB未満の敵と戦うとき、そのダメージはそれらの敵のD[e]の平均値
• D[e]がB以上の敵と戦うとき、そのダメージはそれらの敵のD[e]の平均値

となる。あとはそれらの敵と何回戦うかの期待値を求めて、上記平均値と掛け合わせていこう。

int N,M;
int D[202020];
ll S[202020];
const ll mo=998244353;
int A,B;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	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;
	
	cin>>N>>M;
	FOR(i,N) cin>>D[i];
	sort(D,D+N);
	FOR(i,N) S[i+1]=S[i]+D[i];
	FOR(i,M) {
		cin>>A>>B;
		x=lower_bound(D,D+N,B)-D;
		int over=N-x;
		
		if(over<A) {
			cout<<0<<endl;
			continue;
		}
		ll ret=0;
		ll X=(S[N]-S[x])%mo;
		ret+=X*(over-A)%mo*modpow(over);
		if(x) {
			ll X=S[x]%mo;
			ret+=X*(over+1-A)%mo*modpow(over+1);
		}
		cout<<ret%mo<<endl;
	}
}

まとめ

本番意外にすんなり解いてるな。