AtCoder Grand Contest 009: C - Division into Two

,

http://agc009.contest.atcoder.jp/tasks/agc009_c

蟻本などの教科書に載ってそうな感じ。

solution

DP。 愚直だと$O(N^3)$。 $A \le B$と仮定すると$X$側の使った位置をほとんど覚えなくてよくて$O(N^2)$。 しゃくとり法と累積和で$O(N)$。

左から順に所属を決めていく。 愚直には$s_i = \max X, \; s_j = \max Y$であるようなときの$(X, Y)$の場合の数を$\mathrm{dp}(i, j)$とする。 $A \le B$であると仮定する。 $i \lt j - 1$であるとき$s_i + A \le s_{j-1} + B \le s_j + B$であるので、$s_{j+1}$以降の所属を決めるのに$i$の細かい値は必要ない。 $j$番目まで見たとき次に$Y$に所属させる要素$s_k$を決めて開区間$(j, k)$の中は全て$X$に所属させるようにすると、これで$\mathrm{dp} : 2 \times (N+1) \to 10^9+7$とできて$O(N^2)$。 その更新はとりあえず書いてみて眺めれば容易に高速化でき、$O(N)$。

implementation

l_l > l_rな場合で無限にWAを出した。

#include <array>
#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))
using ll = long long;
using namespace std;

constexpr int mod = 1e9+7;
int main() {
    // input
    int n; ll a, b; scanf("%d%lld%lld", &n, &a, &b);
    vector<ll> s(n); repeat (i, n) scanf("%lld", &s[i]);
    if (a > b) swap(a, b);
    // solve
    s.insert(s.begin(), s.front() - a - b);
    s.insert(s.end(),   s.back()  + a + b);
    s.insert(s.end(),   s.back()  + a + b);
    vector<array<int, 2> > dp(n + 2);
    vector<int> acc(dp.size() + 1);
    dp[0][0] = 1;
    acc[1] = 1;
    int l_l = 0, l_r = 0;
    repeat_from (r, 1, dp.size()) {
        while (l_r < r - 1 and s[l_r] + b <= s[r]) ++ l_r;
        if (l_l <= l_r) {
            dp[r][0] = (acc[l_r] - acc[l_l] +(ll) mod) % mod;
        }
        if (not (s[r - 1] + a <= s[r])) l_l = r - 1;
        dp[r][1] = (s[r - 1] + b <= s[r]) ? (dp[r - 1][0] + dp[r - 1][1]) % mod : 0;
        acc[r + 1] = (0ll + acc[r]
                + (s[r - 1] + a <= s[r + 1] ? dp[r][0] : 0)
                + dp[r][1] ) % mod;
    }
    // output
    int result = (dp[n + 1][0] + dp[n + 1][1]) % mod;
    printf("%d\n", result);
    return 0;
}