Ad Hoc Game Theory

Vị trí thắng và vị trí thua

Một trạng thái là thua (cho người sắp đi) nếu mọi nước đi đều dẫn tới trạng thái thắng; là thắng nếu có ít nhất một nước tới trạng thái thua. Trạng thái không còn nước đi là thua. Khi đồ thị trạng thái không có chu trình, tính theo thứ tự ngược của nước đi: trạng thái “gần kết thúc” trước.

Với tham số tới $10^{18}$, không thể tính hết, nhưng có thể tính bằng tay hoặc brute force cho $n$ nhỏ rồi nhìn ra chu kỳ, sau đó chứng minh chu kỳ đó bằng quy nạp: mỗi trạng thái thua chỉ dẫn tới trạng thái thắng, mỗi trạng thái thắng có nước tới trạng thái thua.

Ví dụBước Nhảy Trên Hoán Vị

Đề. Hoán vị $a$ dài $n \le 5000$. Từ ô $i$ được nhảy tới ô $j$ nếu $|i - j|$ là bội dương của $a_i$ và $a_j > a_i$. Với mỗi ô xuất phát, in A nếu người đi trước thắng, B nếu thua.

Lời giải. Mọi nước đi tăng giá trị, nên xét ô theo $a$ giảm dần: khi tới ô $i$, mọi ô đích đã có kết quả. Ô $i$ thắng nếu có một ô đích thua.

Bước 1: duyệt theo giá trị giảm dần. at[v] là vị trí của giá trị $v$.

Bước 2: các ô đích. Vòng j bắt đầu từ i % v, tăng theo bước $v$: đi qua mọi ô cách $i$ một bội của $v$, cả bên trái lẫn bên phải, trong một vòng. j >= 1 loại ô 0; a[j] > v giữ đúng điều kiện nước đi và tự loại chính ô $i$.

for (ll v = n; v >= 1; v--) {
    ll i = at[v];
    for (ll j = i % v; j <= n; j += v)
        if (j >= 1 && a[j] > v && !win[j]) win[i] = 1;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 5005;
ll n, a[N], at[N];
bool win[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        at[a[i]] = i;
    }
    for (ll v = n; v >= 1; v--) {
        ll i = at[v];
        for (ll j = i % v; j <= n; j += v)
            if (j >= 1 && a[j] > v && !win[j]) win[i] = 1;
    }
    for (ll i = 1; i <= n; i++) cout << (win[i] ? 'A' : 'B');
    cout << '\n';
}

Input1
1

OutputB

Tổng số ô xét là $\sum_v n / v = O(n \log n)$.

Ví dụBước Nhảy 1-2-K

Đề. Quân ở ô $n$ trên dải $0..n$, mỗi lượt lùi 1, 2 hoặc $k$ ô; không đi được thì thua. $n \le 10^{18}$, $3 \le k \le 10^{18}$, tối đa 100 test.

Lời giải. Không có bước $k$, thua đúng khi $n$ chia hết cho 3. Nếu $k$ không chia hết cho 3, bước $k$ từ bội của 3 vẫn rơi vào số không chia hết cho 3, nên quy luật giữ nguyên. Nếu $k$ chia hết cho 3, brute force cho thấy chu kỳ $k + 1$: lấy $r = n \bmod (k + 1)$, ô $r = k$ thắng (nhảy $k$ về 0), các $r$ khác thắng khi $r$ không chia hết cho 3.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll t, n, k;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n >> k;
        bool alice;
        if (k % 3) alice = n % 3 != 0;
        else {
            ll r = n % (k + 1);
            alice = r == k || r % 3 != 0;
        }
        cout << (alice ? "Alice" : "Bob") << '\n';
    }
}

Input1
0 3

OutputBob

Số lượt cố định: chỉ cần chẵn lẻ

Có những trò mà dù chơi thế nào, tổng số lượt vẫn như nhau. Khi đó không có chiến lược nào: người đi trước thắng khi và chỉ khi tổng số lượt lẻ. Dấu hiệu: mỗi lượt làm một đại lượng giảm đúng 1, và trò chỉ dừng khi đại lượng đó về một giá trị cố định.

Cần chứng minh tổng số lượt không phụ thuộc cách chơi, không chỉ đoán. Ví dụ, xóa cặp ký tự kề bằng nhau: kết quả cuối cùng (xâu không còn cặp nào) là duy nhất, giống như rút gọn ngoặc, nên số lần xóa luôn bằng nhau.

Ví dụNhững Khúc Gỗ

Đề. $n$ khúc gỗ dài $a_i \le 10^9$. Mỗi lượt chặt một khúc dài ít nhất 2 thành hai khúc nguyên dương. Ai không chặt được thì thua; errorgorn đi trước.

Lời giải. Mỗi lượt tăng số khúc đúng 1, trò dừng khi mọi khúc dài 1, tức có $\sum a_i$ khúc. Tổng số lượt là $\sum (a_i - 1)$; lẻ thì errorgorn thắng.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll t, n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n;
        ll s = 0;
        for (ll i = 1; i <= n; i++) {
            ll x;
            cin >> x;
            s += x - 1;
        }
        cout << (s % 2 ? "errorgorn" : "maomao90") << '\n';
    }
}

Input1
1
1

Outputmaomao90

Ví dụCặp Ký Tự Biến Mất

Đề. Xâu chữ thường dài tới $10^5$. Mỗi lượt xóa hai ký tự kề nhau bằng nhau; ai không xóa được thì thua. In Yes nếu người đi trước thắng.

Lời giải. Duyệt xâu với một ngăn xếp: ký tự trùng đỉnh ngăn xếp thì bỏ cả hai và đếm một lần xóa. Số lần xóa không phụ thuộc thứ tự, nên chỉ xem nó lẻ hay chẵn.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s, st;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    ll cnt = 0;
    for (char c : s) {
        if (!st.empty() && st.back() == c) st.pop_back(), cnt++;
        else st.push_back(c);
    }
    cout << (cnt % 2 ? "Yes" : "No") << '\n';
}

Inputa

OutputNo

Chiến lược đối xứng

Nếu trạng thái có một phép đối xứng, và người thứ hai luôn đi được nước gương của nước vừa rồi, thì người thứ hai không bao giờ hết nước trước: người thứ nhất đi được thì nước gương cũng hợp lệ. Muốn người đi trước hưởng chiến lược này, nước đầu tiên của họ phải đưa trạng thái về dạng đối xứng, ví dụ chiếm đúng tâm.

Dạng tổng quát hơn là ghép cặp: chia các nước đi thành cặp sao cho sau khi đối thủ dùng một nước, nước còn lại của cặp vẫn hợp lệ. Lập luận chỉ cần chỉ ra phép ghép, không cần duyệt cây trò chơi.

Ví dụĐặt Đĩa Tròn

Đề. Bàn $a \times b$, hai người luân phiên đặt đĩa bán kính $r$ nằm trọn trong bàn và không chồng lên nhau. Ai không đặt được thì thua. $a, b, r \le 10^9$.

Lời giải. Không đặt nổi một đĩa ($2r > a$ hoặc $2r > b$) thì người đầu thua. Ngược lại người đầu đặt đĩa đầu vào tâm, rồi đáp mỗi đĩa của đối thủ bằng đĩa đối xứng qua tâm: chỗ đó luôn trống, vì nếu nó chồng lên đĩa nào thì đĩa đối thủ vừa đặt cũng chồng lên ảnh gương của đĩa ấy.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll a, b, r;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> a >> b >> r;
    cout << (2 * r <= min(a, b) ? "First" : "Second") << '\n';
}

Input3 3 1

OutputFirst

Ví dụMột Nửa Số Đống

Đề. $n$ đống đá, $n$ chẵn, $n \le 5000$. Mỗi lượt chọn đúng $n/2$ đống khác rỗng và bớt mỗi đống một lượng dương. Khi còn ít hơn $n/2$ đống khác rỗng, người tới lượt thua. Alice đi trước.

Lời giải. Gọi $c$ là số đống bằng giá trị nhỏ nhất. Nếu $c > n/2$, mọi nước của Alice phải chạm ít nhất một đống nhỏ nhất, làm nó nhỏ hơn hẳn; Bob kéo $n/2$ đống khác về đúng giá trị mới đó, lại có hơn nửa số đống bằng nhỏ nhất, cho tới khi Alice hết nước. Nếu $c \le n/2$, Alice kéo $n/2$ đống lớn nhất về đúng giá trị nhỏ nhất, tạo ra trạng thái có hơn nửa số đống nhỏ nhất cho Bob.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 5005;
ll n, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll mn = *min_element(a + 1, a + n + 1), c = 0;
    for (ll i = 1; i <= n; i++)
        if (a[i] == mn) c++;
    cout << (c > n / 2 ? "Bob" : "Alice") << '\n';
}

Input2
1 1

OutputBob

Tranh điểm: DP minimax trên hiệu số

Khi hai người cùng tối đa điểm của mình trên một tổng cố định, đặt $f(\text{trạng thái})$ là hiệu “điểm người sắp đi trừ điểm người kia” khi cả hai chơi tối ưu. Người sắp đi chọn nước $x$ được $v_x$ điểm, rồi đổi vai: $f = \max_x (v_x - f(\text{trạng thái sau}))$. Có hiệu $d$ và tổng $S$ thì điểm người đầu là $(S + d) / 2$. Một số bài có cấu trúc đặc biệt cho phép tham lam (sắp giảm dần rồi chọn lần lượt), nhưng khi các lượt ảnh hưởng nhau qua hình dạng trạng thái thì cần DP.

Ví dụLấy Số Hai Đầu

Đề. Dãy $n \le 5000$ số nguyên (có thể âm, trị tuyệt đối tới $10^9$). Hai người lần lượt lấy một số ở đầu trái hoặc đầu phải và cộng vào điểm mình, cùng tối đa điểm mình. In điểm người đầu.

Lời giải. Gọi $f(l, r)$ là điểm người đi lượt này hơn đối thủ khi còn đoạn $a_l..a_r$. Lấy đầu trái được $a_l$, rồi đối thủ hơn mình $f(l + 1, r)$; lấy đầu phải tương tự. Vậy $f(l, r) = \max(a_l - f(l + 1, r),\ a_r - f(l, r - 1))$, $f(l, l) = a_l$. Biết tổng $S$ và hiệu $d = f(1, n)$ thì điểm người đầu là $(S + d) / 2$.

Bước 1: một mảng cho độ dài hiện tại. dp[l] ở vòng độ dài len là $f(l, l + len - 1)$. Lúc tính, dp[l + 1] vẫn là giá trị độ dài cũ, tức $f(l + 1, r)$; dp[l] cũ là $f(l, r - 1)$. Duyệt $l$ tăng dần nên đọc dp[l + 1] trước khi nó bị ghi. Bộ nhớ $O(n)$ thay vì $n^2$ số long long.

for (ll len = 2; len <= n; len++)
    for (ll l = 1; l + len - 1 <= n; l++) {
        ll r = l + len - 1;
        dp[l] = max(a[l] - dp[l + 1], a[r] - dp[l]);
    }
cout << (sum + dp[1]) / 2 << '\n';

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 5005;
ll n, a[N], dp[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll sum = 0;
    for (ll i = 1; i <= n; i++) cin >> a[i], sum += a[i], dp[i] = a[i];
    for (ll len = 2; len <= n; len++)
        for (ll l = 1; l + len - 1 <= n; l++) {
            ll r = l + len - 1;
            dp[l] = max(a[l] - dp[l + 1], a[r] - dp[l]);
        }
    cout << (sum + dp[1]) / 2 << '\n';
}

Input1
1

Output1

$O(n^2)$ thời gian, $O(n)$ bộ nhớ.