Yukicoder No.472 平均順位

DPやるだけなので楽。

solution

DP。$i$コンテスト目まで参加して$j$問解いたときの順位の総和を$\mathrm{dp}(i,j)$としてこれを最小化。$O(NP)$。

implementation

#include <cstdio>
#include <vector>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
typedef long long ll;
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
const int inf = 1e9+7;
int main() {
    int n, p; scanf("%d%d", &n, &p);
    vector<array<int, 4> > th(n);
    repeat (i,n) {
        repeat (j,3) scanf("%d", &th[i][j]);
        th[i][3] = 1;
    }
    vector<int> cur(p+1, inf);
    vector<int> prv;
    cur[0] = 0;
    repeat (i,n) {
        cur.swap(prv);
        cur.clear();
        cur.resize(p+1, inf);
        repeat (k,p+1) {
            repeat (j,4) if (k+j < p+1) {
                setmin(cur[k+j], prv[k] + th[i][j]);
            }
        }
    }
    printf("%.8lf\n", cur[p] /(double) n);
    return 0;
}