CODE FESTIVAL 2018 Qual B : D - Sushi Restaurant

ここら辺自力で解けたのはよかったね。
https://beta.atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_d

問題

N人の人がいる。
各人がある空腹度Xiである確率Piがそれぞれ与えられる。

彼らにいくつかの寿司が乗った皿を計N個提供する。
空腹度xの人がy個のった皿を取ると不満度が|x-y|増加する。
また、彼らは互いの空腹度を把握しており、各人の不満度の合計が最小となるよう、それぞれ１つずつ皿を取る。

各皿に整数個の寿司をのせ提供する場合、不満度の期待値を求めよ。

解法

まずN人の人がどのように皿を取るかを考える。
これは単純で、空腹度の低い順に、寿司の数の少ない皿を取る。
そこで以下を求めよう。

f(a,b) := 少ない順からa番目の空腹度の人の人の空腹度が、X[b]である確率
すると、少ない順からa個目の皿には、sum(|y-X[b]|*f(a,b))が最小となるy個の寿司を載せればよくなる。

まずf(a,b)を求めよう。そのためには以下を考える。
g(a,b) :=少ない順からa番目の空腹度の人の人の空腹度が、X[b]以下である確率
h(a,b) :=X[b]以下の空腹度の人がちょうどa人である確率
Q(b) := 1人選んだ時空腹度がX[n]以下である確率

まず以下は単純な二項定理の延長で求められる。

g(a,b)はX[b]以下の空腹度の人がa人以上いればよいので

かつ、f(a,b)はa番目の人がX[b]未満であるケースを除けばよいので

これでf(a,b)が求まった。
あとは各aに対しsum(|y-X[b]|*f(a,b))を最小化するyを考える。
yはX[b]*f(a,b)の期待値…ではなく、bに対するf(a,b)の総和が最も0.5に近くなるX[b]を選ぶのが良い。
これはよく数直線上で1移動するコストが1ある場合、数直線上の点をどこに寄せるのが最適化を求める問題で出てくる考えだね。

int N,M,Q;
int X[2020];
long double P[2020];
long double PS[2020];

long double dp[2020][2020];

static const int N_=2020;
static long double C_[N_][N_];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,N_) C_[i][0]=C_[i][i]=1;
	for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	
	cin>>N>>M>>Q;
	FOR(i,M) {
		cin>>X[i]>>P[i];
		P[i]/=Q;
		PS[i+1]=PS[i]+P[i];
	}
	
	for(i=M-1;i>=0;i--) for(x=N;x>=0;x--) dp[i][x]=C_[N][x]*pow(PS[i+1],x)*pow(1-PS[i+1],N-x);
	FOR(i,M) for(x=N;x>=0;x--) dp[i][x]+=dp[i][x+1];
	for(i=M-1;i>=1;i--) for(x=N;x>=0;x--) dp[i][x]-=dp[i-1][x];
	
	
	long double ret=0;
	for(i=1;i<=N;i++) {
		long double S[2020]={};
		long double PS[2020]={};
		FOR(j,M) {
			S[j+1]=S[j]+X[j]*dp[j][i];
			PS[j+1]=PS[j]+dp[j][i];
			
		}
		long double be=1e10;
		FOR(j,M) {
			be=min(be,(S[M]-S[j+1])-X[j]*(1-PS[j+1])+X[j]*PS[j]-S[j]);
		}
		
		ret+=be;
	}
	_P("%.12lf\n",(double)ret);
	
}

まとめ

包除原理苦手なのでこういうのしんどい。