8VC Venture Cup 2016 - Elimination Round D. Jerry’s Protest

難しくない問題なのに実装に時間を取られてしまった。深夜に開催されたのが悪いのだと思いたい。

D. Jerry’s Protest

解法

knapsack問題を重さの制約を利用して多項式時間でdpするあれに似たことをする。$O(n + a^2)$。単なる数え上げなので期待値のdpではない。

ボールに書かれた数の差の頻度表を作り、それを重ね合わせたものを作り、これらふたつをまとめて舐める。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    vector<ll> wins(*max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end()) + 1);
    repeat (i,n) repeat (j,n) if (i != j and a[i] > a[j]) ++ wins[a[i] - a[j]];
    vector<ll> wins2(wins.size() * 2 + 1);
    repeat (i,wins.size()) repeat (j,wins.size()) wins2[i + j] += wins[i] * wins[j];
    ll cnt = 0;
    ll acc = 0;
    int j = 0;
    repeat (i, wins.size()) {
        cnt += wins[i] * acc;
        acc += wins2[j];
        ++ j;
    }
    printf("%.12f\n", cnt / pow(accumulate(wins.begin(), wins.end(), 0ll), 3));
    return 0;
}