AtCoder Grand Contest 007: D - Shik and Game

,

http://agc007.contest.atcoder.jp/tasks/agc007_d

自明DPの$O(N^2)$をsegment木とかで$O(N \log N)$で落とすやつでしょ知ってるけど$N \le 10^5$なので定数倍高速化で押し切るよ、って言いながらガチャガチャしてたらいつの間にか$O(N)$に落ちてしまっていた。レギュレーション違反。定数倍高速化でなんとかする方法は分からず。後$2$倍。本気でやればできるのかもだが、コンパイラに察してもらう範囲ではだめだった。

solution

DP。$O(N)$。

まず同じ点を$3$回を越えて通る必要はないことを見る。図を書けばすぐ。これには$0 \le x_i \le E$が成り立つことが効いている。

そこでDPをする。 $i$番目以降のみを考え$x_i$に到着した直後から必要な最短時間を$\mathrm{dp}_i$とする。 どこまでキャンディを配ってから$x_i$に戻ってくるかを考えれば漸化式 $\mathrm{dp}_l = \min \{ \max \{ T, 2(x_{r-1} - r_l) + (x_r - x_l) + \mathrm{dp}_r \mid r \gt l \}$。 そのままでは$O(N^2)$だが、内側の$\max$を消去し$\mathrm{dp}$は単調減少であることを使えば$O(N)$にできる。

implementation

#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

constexpr ll inf = ll(1e18)+9;
int main() {
    // input
    int n, e, t; scanf("%d%d%d", &n, &e, &t);
    vector<int> x(n); repeat (i, n) scanf("%d", &x[i]);
    // solve
    vector<ll> dp(n + 1, inf);
    dp[n] = e;
    int m = n;
    ll acc = inf;
    repeat_reverse (l, n) {
        for (; m - 1 >= l + 1 and t <= 2ll * (x[m - 1] - x[l]); -- m) {
            setmin(acc, 2ll * x[m - 1] + dp[m]);
        }
        dp[l] = min(acc - 2ll * x[l], t + dp[m]);
    }
    // output
    printf("%lld\n", dp[0]);
    return 0;
}

愚直 $O(N^2)$

#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 repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

constexpr ll inf = ll(1e18)+9;
int main() {
    // input
    int n, e, t; scanf("%d%d%d", &n, &e, &t);
    vector<int> x(n); repeat (i, n) scanf("%d", &x[i]);
    // solve
    x.push_back(e);
    vector<ll> dp(n + 1, inf);
    dp[n] = 0;
    repeat_reverse (l, n) {
        repeat_from (r, l + 1, n + 1) {
            setmin(dp[l], max<ll>(t, 2ll * (x[r - 1] - x[l])) + (x[r] - x[l]) + dp[r]);
        }
    }
    // output
    printf("%lld\n", x[0] + dp[0]);
    return 0;
}