Ad Hoc Game Theory

Thắng và 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. Nó 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. Đồ thị trạng thái không có chu trình thì tính theo thứ tự ngược của nước đi, từ trạng thái gần kết thúc.

Hình dưới tính bảng này cho trò lấy sỏi. Đổi tập số sỏi được lấy mỗi lượt để thấy quy luật.

Tham số tới $10^{18}$ thì không tính hết được. Ta tính brute force cho $n$ nhỏ, nhìn ra chu kỳ, rồi chứng minh 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;
#define 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';
}

ChạyInput1
1

OutputB

Độ phức tạp: 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;
#define 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';
    }
}

ChạyInput1
0 3

OutputBob

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 đó chiến lược không còn ý nghĩa: 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 thay đổi đú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 thì xâu cuối cùng là duy nhất, như rút gọn ngoặc, nên số lần xóa luôn như 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;
#define 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';
    }
}

ChạyInput1
1
1

Outputmaomao90

Đối xứng

Nếu người thứ hai luôn đi được nước gương của nước vừa rồi thì 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 phải đưa trạng thái về dạng đối xứng, ví dụ chiếm đúng tâm.

Tổng quát hơn là ghép cặp: chia các nước đi thành cặp sao cho đối thủ dùng một nước thì nước còn lại của cặp vẫn hợp lệ. 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;
#define 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';
}

ChạyInput3 3 1

OutputFirst

Tranh điểm

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}))$. Biết hiệu $d$ và tổng $S$ thì điểm người đầu là $(S + d) / 2$.

Một số bài cho phép tham lam (sắp giảm dần rồi chọn lần lượt). Khi các lượt ảnh hưởng nhau qua hình dạng trạng thái thì cần DP.

Trong hình, mỗi ô $f(l, r)$ lấy từ hai ô kề màu xanh: lấy số trái hay số phải, rồi đổi vai.

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;
#define 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';
}

ChạyInput1
1

Output1

$O(n^2)$ thời gian, $O(n)$ bộ nhớ. Cuốn mảng không chỉ tiết kiệm bộ nhớ, nó còn nhanh hơn nhiều:

Cùng $8 \cdot 10^6$ ô cần tính, mảng một chiều nhanh hơn bảng hai chiều duyệt theo độ dài khoảng 15 lần, và duyệt theo hàng cũng chậm hơn khoảng 6 lần. Quy tắc: DP chỉ cần lớp trước thì cuốn mảng, cả bộ nhớ lẫn tốc độ đều lợi.