Array Game

Created by LXC on Sun Jul 16 00:12:18 2023

https://codeforces.com/problemset/problem/1600/E

ranting: 1900

tag: games, greedy, two pointers

problem

给出一排数，alice和bob轮流操作，alice先行。

每次操作只能选最左侧或最右侧的数，然后当前选手选择的数必须严格比对手上次所选的数大。

在alice和bob发挥最佳水平时，求谁胜。

solution

我们比较左右两端的值的大小，当我们选择较大值时，较小值的一端无法再选取，所以较大值一端连续严格增大的个数的奇偶性决定了胜负。当较大端为奇数时，当前选手必胜，否则我们只能选择较小端。当前选则较小端后，对手会面临相同的问题，所以可以递归处理。

另一种比较直接的结论就是两端只要一端存在奇数个数的严格增大的个数，就必胜。

若一端为奇数个数，另一端为偶数个数，我们选择奇数个数的一端，对手面临两端都为偶数，必败。

若两端都为奇数，我们选择较大端，从而较小端大家都无法选取，对手可选端依旧为偶数，必败。

若两端都为偶数，对手面临两端都为偶数，必败，当对手是自己时显然自身必败。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    vector<int> l(n, 1), r(n, 1);
    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i])
            l[i] += l[i - 1];
    }
    for (int i = n - 2; i >= 0; i--) {
        if (a[i + 1] > a[i])
            r[i] += r[i + 1];
    }
    auto dfs = [&](auto self, int x, int y, int p) -> bool {
        // cout << x << " " << y << "\n";
        if (x == y)
            return a[x] > p;
        if (a[x] <= p && a[y] <= p)
            return false;
        if (a[x] <= p)
            return !self(self, x, y - 1, a[y]);
        if (a[y] <= p)
            return !self(self, x + 1, y, a[x]);
        if (a[x] > a[y]) {
            if (r[x] % 2)
                return true;
            return !self(self, x, y - 1, a[y]);
        } else if (a[x] < a[y]) {
            if (l[y] % 2)
                return true;
            return !self(self, x + 1, y, a[x]);
        } else
            return l[y] % 2 || r[x] % 2;
    };
    cout << (dfs(dfs, 0, n - 1, -1) ? "Alice\n" : "Bob\n");
}

void sol2() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    int l = 0, r = n - 1;
    while (l + 1 < n && a[l + 1] > a[l])
        l++;
    while (r - 1 >= 0 && a[r - 1] > a[r])
        r--;
    l = l + 1;
    r = n - r;
    cout << ((l % 2 || r % 2) ? "Alice\n" : "Bob\n");
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
    // sol2();
#endif
    return 0;
}