Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。

問題概要

長さ $N$ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値が $X$ 以下でなければらなない。最後の 1 ピースをとってしまった方の負けである。

双方最善を尽くしたとき、どちらが勝つか？

制約

$1 \le N \le 5000$

考えたこと

いかにも、こんな感じの DP をしたくなる。

dp[ l ][ r ]:= 区間 [l, r) が残った状態から勝てるかどうか？

このままだと、先手・後手が手番において「どこまで取るか」をきちんと考えた DP 遷移をしようと思うと $O(N^{3})$ になってしまう。ここでよくある DP 高速化をする。 $O(N)$ 通りの遷移を高速化するのは非常によく見られる典型ではある。

多分累積和とかで良さそうだけど、ここでは BIT でやってみた。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <class Abel> struct BIT {
    const Abel UNITY_SUM = 0;                       // to be set
    vector<Abel> dat;
    
    /* [1, n] */
    BIT(int n) : dat(n + 1, UNITY_SUM) { }
    void init(int n) { dat.assign(n + 1, UNITY_SUM); }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int N;
long long X;
vector<long long> a, s;
vector<int> l2r, r2l;

bool solve() {
    l2r.assign(N+1, -1), r2l.assign(N+1, -1);
    int r = 0;
    for (int l = 0; l < N; ++l) {
        while (r < N && s[r + 1] - s[l] <= X) {
            ++r;
            r2l[r] = l;
        }
        l2r[l] = r;
    }

    vector<BIT<int> > left(N+5, BIT<int>(N+5));
    vector<BIT<int> > right(N+5, BIT<int>(N+5));
    for (int l = 0; l <= N; ++l) left[l].add(l+1, 1);
    for (int r = 0; r <= N; ++r) right[r].add(r+1, 1);
    for (int bet = 1; bet <= N; ++bet) {
        for (int l = 0; l+bet <= N; ++l) {
            int r = l+bet;
            
            // l+1, ..., min(l2r[l], r) に「負け」があれば OK
            int mi = min(l2r[l], r);
            int tmp1 = (mi-l) - right[r].sum(l+2, mi+2);

            // max(l, r2l[r]), ..., r-1 に「負け」があれば OK
            int ma = max(l, r2l[r]);
            int tmp2 = (r-ma) - left[l].sum(ma+1, r+1);

            // judge
            if (tmp1 + tmp2) left[l].add(r+1, 1), right[r].add(l+1, 1);
        }
    }
    return left[0].sum(N+1, N+2);
}

int main() {
    while (cin >> N >> X) {
        a.resize(N); s.assign(N+1, 0);
        for (int i = 0; i < N; ++i) cin >> a[i], s[i+1] = s[i] + a[i];
        if (solve()) cout << "A" << endl;
        else cout << "B" << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

yukicoder No.973 余興

問題概要

制約

考えたこと