Code Festival 2018 予選B D - Sushi Restaurant

企業コンテスト

なんか本番中ずっと不適合度って言葉が気になってた
社会不適合度

本戦はtokumini君と寿司食ってきます✨

問題

略

解法

まずn人の空腹度が a[1],a[2],...,a[n] (昇順) で各皿に乗った寿司の個数が b[1],b[2],...,b[n] (昇順) である場合の不適合度は
Σ |a[i]-b[i]|
となる
このことからは「空腹度がi番目に少ない人」は「i番目に寿司が少ない皿」としか関係しないことがわかる

「空腹度がi番目に低い人」の空腹度がx[j]である確率をs(i,j)とする
またi人目が取る皿の寿司の個数をcとすると、この人の不満度の期待値は
Σ s(i,j) * |x[j]-c| (1 <= j <= m)
となる
これはよくあるやつで、cがx[K] (K: Σs(i,j)が0.5に最も近くなるi) のときに最小になる(中央値のやつ、証明略)
これを各iについて計算して足し合わせればO(nm)で答えがわかる
あとはs(i,j)を事前計算として求められればok

s(i,j)は単純に考えると、L <= i かつ i < r として
ΣΣ [(空腹度がx[j]未満の人がL-1人いる確率) * (空腹度がx[j]の人がr-L人いる確率)
* (空腹度がx[j]より大きい人がn-r+1人いる確率)] * n! / (L-1)! / (r-L)! / (n-r+1)! (並べ方の個数)
となる
Lとrを全通り試すとs(i,j)1個につきO(n^2)かかり、iがn通りでjがm通りあるからトータルでO(n^3 m)
ただ L <= i < r を満たす全てのiでs(i,j)は同じ値になるから、Lとrを全通り試しながら配列のs[L][j]からs[r-1][j]までいもす法(累積和)で足していくようにすると、iを全通り試す必要がなくなり、トータルO(n^2 m)になる
けどこれでもまだ間に合わない

空腹度がi番目に低い人の空腹度がx[j]以上である確率をt(i,j)とする
するとt(i,j)は、L <= iとして
Σ [(空腹度がx[j]未満の人がL-1人いる確率) * (空腹度がx[j]以上の人がn-L+1人いる確率)]
* n! / (L-1)! / (n-L+1)!
となる
これはさっきと同様にLを全通り試しつつL <= iの範囲に足していけばO(nm)で求められる
また定義より
s(i,j) = t(i,j) - t(i,j+1)
だからこれで解けた🤠

実装

コード中のsが↑で言うt

2000の階乗とかをdoubleでまともにやるとオーバーフローするから、途中はlogで計算して最後にexpする
logだから掛け算が足し算に、割り算が引き算に、べき乗が掛け算になってることに注意
あと0除算同様log(0)に気をつける必要がある
↓の書き方だとj=1のとき面倒なことになるから特別扱いしてやった
これ初めてやったけど便利だな

int n, m, q, x[2020], p[2020], ps[2020];
double f[2020], s[2020][2020], ans;

signed main() {
	reps(i,2,2020) f[i] = f[i-1] + log(i);
	cin >> n >> m >> q;
	reps(i,1,m+1) {
		cin >> x[i] >> p[i];
		ps[i] = p[i] + ps[i-1];
	}

	reps(i,1,n+1) {
		s[i][1] = (i==1 ? 1 : 0);
		reps(j,2,m+1) {
			s[i][j] += log(1.*ps[j-1]/q) * (i-1);
			s[i][j] += log(1.*(ps[m]-ps[j-1])/q) * (n-i+1);
			s[i][j] += f[n] - f[i-1] - f[n-i+1];
			s[i][j] = exp(s[i][j]);
		}
	}
	reps(i,1,n+1) reps(j,1,m+1) s[i][j] += s[i-1][j];

	reps(i,1,n+1) {
		double sum = 0;
		int id = -1;
		reps(j,1,m+1) {
			s[i][j] -= s[i][j+1];
			if (sum<0.5) id = j;
			sum += s[i][j];
		}
		reps(j,1,m+1) ans += s[i][j] * abs(x[j]-x[id]);
	}
	printf("%.14lf\n",ans);
}

模範解答だとloglistを事前に作ることで高速化とlog0避けを同時にしててスマート
条件を復元できる範囲でゆるくして変数を1個消すってテクニックは覚えておきたい

https://beta.atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_d