D - Sushi Restaurant

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

てんぷらさんのツイートとコードを参考にしました

https://twitter.com/tempura_cpp/status/1051475771221401600

https://atcoder.jp/contests/code-festival-2018-qualb/submissions/3409618

解法

空腹度と寿司の個数はソート出来る。

その時、各々が目の前の寿司を食べるのが最適となるため、独立して寿司の個数を考える事が出来る。

ここで「dp[i][j] := i番の空腹度がx[j]になる確率」を求められれば

i番にsum(x[0] ~ x[j]) >= 0.5 なる最小のjで、j個の寿司を出すのが最適となる。

なぜなら、p(>=0.5) = sum(x[0] ~ x[j]) として

jを1増やすと答えがp-(1-p)増え

jを1減らすとq(<0.5) = p-dp[i][j]で答えが(1-q) - q増え

どちらも答えが大きくなっており、jに対する不満度の大きさは凹関数となっている事からjが最適となるからである。

また、dp[i][j] は「sub[i][j] := i番目の空腹度がx[j]以上になる確率」として

dp[i][j] := sub[i][j] - sub[i][j+1]と求められる

sub[i][j]は k = 0 ~  iで以下を足し合わせた物になる。

x[j]未満がk人で、x[j]以上がn-k人となる確率

そのまま計算すると間に合わないが

sub[i][j] = sub[i-1][j] + x[j]未満がi人で、x[j]以上がn-i人となる確率

と漸化的にまとめられる

https://atcoder.jp/contests/code-festival-2018-qualb/submissions/4813350

//define double long double
void solve() {
    double q;
    cin >> n >> m >> q;
    vd x(m+1), p(m+1);
    rep(i, m)cin >> x[i + 1] >> p[i + 1];
    vd rp(m + 1);//空腹度がp[i]以下になる確率(1index)
    rep(i, 1, m + 1) {
        p[i] /= q;
        rp[i] = p[i];
        rp[i] += rp[i - 1];
    }
    vvd(dp, 2020, 2020);//i番目がj(1index)以上となる確率
    //全てj以上
    rep(j, 1, m + 1)dp[0][j] = pow(1 - rp[j - 1], n);
    rep(j, 1, m + 1) {
        rep(i, 1, n) {
            //x[j]未満がk個(i以下)
            //x[j]以上がn-k個
            //         0 ~ i-1
            dp[i][j] += dp[i - 1][j];
            //          i
            dp[i][j] += comd(n, i) * pow(rp[j - 1], i) * pow(1 - rp[j - 1], n - i);
        }
    }
    rep(i, 2020) {
        rep(j, 1, 2020 - 1) {
            dp[i][j] -= dp[i][j + 1];
        }
    }
    dou res = 0;
    rep(i, n) {
        int ind = 1;//j 1index
        dou per = 0;
        while (per < 0.5) {
            per += dp[i][ind];
            ind++;
        }
        dou v = x[ind - 1];
        rep(j, 1, m + 1) {
            res += dp[i][j] * abs(v - x[j]);
        }
    }
    cout << res << endl;
}