AtCoder ABC #226 : H - Random Kth Max

本番中に解けてよかった。
https://atcoder.jp/contests/abc226/tasks/abc226_h

問題

N個の変数X[i]があり、各変数X[i]は[L[i],R[i]]の範囲のいずれかの実数値を均一な確率で取る。
これらの変数のうちK番目に大きな値の期待値を求めよ。

解法

解が[x,x+1]の範囲となるケースを総当たりしよう。
N個の変数のうち、x+1以上の値を取るものがs個、[x,x+1]の範囲を取るものがt個である確率を考える。
この処理は、O(N^3)で計算できる。

K番目に大きな値が[x,x+1]の範囲に来るには、s＜Kかつs+t≧Kであればよい。
[x,x+1]の範囲を取る変数がt個あるなら、それらを降順に並べた値の期待値は(x+t/(n+1)),(x+(t-1)/(n+1)),(x+(t-2)/(n+1))...となるので、(K-s)番目のものを選ぼう。

xを総当たりしても、O(N^3*max(R))で解ける。

int N,K;
int L[55],R[55];
const ll mo=998244353;

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;
}

ll dp[55][55];
ll re[155];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>L[i]>>R[i];
	for(i=1;i<=150;i++) re[i]=modpow(i);
	
	ll ret=0;
	for(x=0;x<100;x++) {
		ZERO(dp);
		dp[0][0]=1;
		FOR(y,N) {
			ll same=0,mor=0;
			if(L[y]<=x&&x<R[y]) {
				same=re[R[y]-L[y]];
				mor=(R[y]-x-1)*re[R[y]-L[y]]%mo;
			}
			else if(x<R[y]) {
				mor=1;
			}
			ll les=(1-same-mor+2*mo)%mo;
			for(j=y+2;j>=0;j--) for(k=y+2;k>=0;k--) if(dp[j][k]) {
				(dp[j][k+1]+=dp[j][k]*same)%=mo;
				(dp[j+1][k]+=dp[j][k]*mor)%=mo;
				(dp[j][k]=dp[j][k]*les)%=mo;
			}
		}
		FOR(j,N+1) FOR(k,N+1) if(j<K&&j+k>=K&&dp[j][k]) {
			int s=K-j;
			(ret+=dp[j][k]*(x+(k+1-s)*re[k+1]%mo)%mo)%=mo;
		}
	}
	cout<<ret<<endl;
}

まとめ

ここらへん、ARC/AGCでも似た考えを使う問題出たことあったしね。