AtCoder Beginner Contest 076: D - AtCoder Express

,

https://abc076.contest.atcoder.jp/tasks/abc076_d

全部perlで提出したかったのですが、perlでは間に合いませんでした (https://abc076.contest.atcoder.jp/submissions/1721602)

solution

DP。$O(\sum t_i \cdot \max v_i)$。

時刻$t$に速度$v$で走っているときのそれまでの走行距離の最大値を$\mathrm{dp}(t, v)$とすればよい。 ただし$t \in \mathbb{N}$だと粗すぎてだめで、$0.5$刻みで計算しなければならない。

implementation

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int main() {
    int n; scanf("%d", &n);
    vector<int> t(n); repeat (i, n) scanf("%d", &t[i]);
    vector<int> v(n); repeat (i, n) scanf("%d", &v[i]);
    const int max_v = *max_element(whole(v));
    constexpr int zoom = 2;
    vector<double> cur(zoom * max_v + 3, - INFINITY);
    vector<double> prv(zoom * max_v + 3, - INFINITY);
    cur[0] = 0;
    repeat (i, n) {
        fill(cur.begin() + (zoom * v[i] + 1), cur.end(), - INFINITY);
        fill(prv.begin() + (zoom * v[i] + 1), prv.end(), - INFINITY);
        repeat (tick, zoom * t[i]) {
            cur.swap(prv);
            cur[0] = max(prv[0], prv[1] + 0.5 / zoom);
            repeat_from (a, 1, zoom * v[i] + 1) {
                cur[a] = max({ prv[a - 1] - 0.5 / zoom, prv[a], prv[a + 1] + 0.5 / zoom }) + a /(double) (zoom * zoom);
            }
        }
    }
    printf("%.12lf\n", cur[0]);
    return 0;
}