Gỡ rối tư duy về quy hoạch động博弈

Lý thuyết trò chơi kết hợp với quy hoạch động (DP) là một chủ đề nâng cao thường gặp trong các bài toán tối ưu hóa có tính đối kháng. Trong mô hình này, hai hoặc nhiều người tham gia thực hiện các lượt đi luân phiên. Mục tiêu cuối cùng của mỗi bên đều là đạt được điều kiện thắng lợi, giả định rằng tất cả người chơi đều sử dụng chiến lược tối ưu.

Các điều kiện kết thúc thường xoay quanh việc tích lũy điểm số đến ngưỡng nhất định hoặc đạt được một cấu hình bàn cờ cụ thể. Kết quả cuộc chơi thường rơi vào một trong ba trường hợp:

• Bên thứ A thắng, bên B thua.
• Bên thứ A thua, bên B thắng.
• Hòa nhau.

Kiến trúc trạng thái cơ bản

Để giải quyết vấn đề bằng DP, ta cần xác định chính xác trạng thái hiện tại. Thông tin tối thiểu bao gồm tình huống bàn cờ và lượt di chuyển của ai (có thể dùng 0 hoặc 1). Nếu liên quan đến điểm số, trạng thái cũng phải lưu trữ giá trị điểm của các bên.

Chúng ta thường gọi người đang đến lượt là prior thủ (tiên thủ) và người còn lại là hậu thủ. Kết quả từ góc nhìn tiên thủ được phân loại:

• Tiên thủ chắc chắn thắng (ký hiệu 1).
• Tiên thủ chắc chắn thua (ký hiệu 0).
• Hòa (ký hiệu 2).

Một lưu ý quan trọng: Vai trò tiên thủ có thể thay đổi hoặc cố định tùy thuộc luật chơi khi trạng thái biến đổi.

Hai dạng bài toán phổ biến

1. Trò chơi công bằng (Impartial Game)

Ở dạng này, danh sách các nước đi khả thi là giống hệt nhau cho bất kỳ người nào ở cùng một vị trí, ví dụ như trò Nim với đống sỏi. Do tính đối xứng này, chúng ta không cần phân biệt vai trò người chơi trong trạng thái DP, chỉ cần quan tâm xem trạng thái hiện tại là thắng hay thua.

2. Trò chơi tổng bằng không (Zero-Sum Game)

Tổng tài nguyên hoặc điểm số trong trò chơi là hằng số. Bất kỳ lợi ích nào một bên giành được sẽ tương ứng với tổn thất của bên kia. Điều này cho phép chúng ta rút gọn trạng thái, thay vì lưu điểm số của cả hai, ta chỉ cần lưu điểm của tiên thủ hoặc chênh lệch điểm số giữa hai bên.

Ví dụ minh họa

Bài toán 1: CF859C - Quy tắc chia bánh

Đây là dạng vừa công bằng vừa tổng bằng không. Ta định nghĩa dp[i] là số điểm tối đa mà người đi trước có thể thu được khi xử lý từ phần tử thứ i đến hết mảng.

Việc tính toán nên thực hiện theo chiều ngược lại (từ n về 1) bởi lẽ quy định ai đi trước ở đầu dãy đã xác định, nhưng thứ tự sau đó phức tạp hơn do quyền quyết định chuyển giao liên tục. Khi xét tới i:

• Nếu chọn nhường miếng cho đối thủ: Điểm không đổi, giá trị là dp[i+1].
• Nếu chọn ăn miếng hiện tại: Đối thủ trở thành người đi tiếp. Giá trị nhận được là tổng phần dư trừ đi điểm tốt nhất đối thủ kiếm được từ trạng thái kế tiếp, cộng thêm giá trị hiện tại.

Phương trình truy hồi: dp[i] = max(dp[i+1], total_suffix - dp[i+1] + value[i]).

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 105;
int values[MAX_N];
int dp_cache[MAX_N];
int n;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> values[i];
    }

    int current_suffix_sum = 0;
    for (int i = n; i >= 1; --i) {
        int take_option = current_suffix_sum - dp_cache[i + 1] + values[i];
        int pass_option = dp_cache[i + 1];
        dp_cache[i] = max(take_option, pass_option);
        current_suffix_sum += values[i];
    }

    cout << current_suffix_sum - dp_cache[1] << " " << dp_cache[1] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Bài toán 2: AT_dp_k - Đập đá

Bài tập này thuộc nhóm công bằng nhưng không nhất thiết là tổng bằng không vì mục đích là vượt qua cột mốc chứ không phải tích điểm. Ta đặt status[k] là true nếu số lượng đá k tồn tại chiến lược để người đi trước thắng, ngược lại là false.

Quan hệ đệ quy: Nếu từ i bước xuống j, và status[j] là thua, thì status[i] ngay lập tức là thắng (vì mình ép đối thủ vào thế thua). Chúng ta duyệt qua từng trạng thái từ 1 đến target và kiểm tra tất cả các kiểu bỏ stones có sẵn.

#include <iostream>
#include <vector>

using namespace std;

const int MAX_K = 100005;
const int MAX_MOVES = 105;
bool win_state[MAX_K];
int allowed_moves[MAX_MOVES];
int num_types, target_stones;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> num_types >> target_stones;
    for (int i = 0; i < num_types; ++i) {
        cin >> allowed_moves[i];
    }

    for (int current = 1; current <= target_stones; ++current) {
        for (int j = 0; j < num_types; ++j) {
            if (current >= allowed_moves[j] && !win_state[current - allowed_moves[j]]) {
                win_state[current] = true;
                break; 
            }
        }
    }

    cout << (win_state[target_stones] ? "First\n" : "Second\n");
    return 0;
}

Bài toán 3: CF786A - Berzerk

Trong tình huống này, hai phe có bộ số bước khác nhau và vòng lặp tồn tại (đồ thị chứa chu trình). Không thể dùng DP thuần túy vì rủi ro vòng lặp vô tận. Phương pháp chuẩn là sử dụng BFS kết hợp với phương pháp topo-sort từ trạng thái kết thúc.

Chúng ta khởi tạo trạng thái chưa biết. Từ trạng thái thua (vào bẫy), ta lan truyền trạng thái thắng cho các vị trí có thể đi ngay đến đó. Ngược lại, nếu mọi đường đi từ một vị trí đều dẫn đến thắng cho đối phương, thì vị trí đó là thua. Số cạnh đi ra giúp xác định khi nào một trạng thái chuyển sang thua.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_NODES = 7005;
int steps[2][MAX_NODES];
int out_degree[2][MAX_NODES];
int game_result[2][MAX_NODES]; // 0: Lose, 1: Win, 2: Loop
int cycle_length;
vector<int> moves[2];
queue<pair<int, int>> processing_q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> cycle_length;
    for (int p = 0; p <= 1; ++p) {
        int cnt; cin >> cnt;
        while (cnt--) {
            int val; cin >> val;
            moves[p].push_back(val);
        }
        out_degree[p].assign(cycle_length, moves[p].size());
    }

    fill(game_result[0], game_result[0] + cycle_length, 2);
    fill(game_result[1], game_result[1] + cycle_length, 2);

    game_result[0][0] = 0; 
    game_result[1][0] = 0;
    processing_q.push({0, 0}); 
    processing_q.push({1, 0});

    while (!processing_q.empty()) {
        auto [turn, pos] = processing_q.front();
        processing_q.pop();
        
        int opponent_turn = 1 - turn;
        int res = game_result[turn][pos];

        for (int step : moves[opponent_turn]) {
            int prev_pos = (pos + cycle_length - step % cycle_length) % cycle_length;
            
            if (game_result[opponent_turn][prev_pos] != 2) continue;

            if (res == 0) {
                game_result[opponent_turn][prev_pos] = 1;
                processing_q.push({opponent_turn, prev_pos});
            } else {
                out_degree[opponent_turn][prev_pos]--;
                if (out_degree[opponent_turn][prev_pos] == 0) {
                    game_result[opponent_turn][prev_pos] = 0;
                    processing_q.push({opponent_turn, prev_pos});
                }
            }
        }
    }

    for (int t = 0; t <= 1; ++t) {
        for (int i = 1; i < cycle_length; ++i) {
            if (game_result[t][i] == 1) cout << "Win ";
            else if (game_result[t][i] == 0) cout << "Lose ";
            else cout << "Loop ";
        }
        cout << "\n";
    }
    return 0;
}

Bài toán 4: CF1987D - Thế giới của tôi

Nếu các số là duy nhất, trò chơi rất đơn giản. Tuy nhiên, khi xuất hiện các phần tử trùng lặp, người chơi thứ hai (B) cần chiến thuật ngăn chặn người chơi thứ nhất (A) ăn nhiều lớp nhất bằng cách tiêu tốn lượt đi của mình.

Sắp xếp và nhóm các số giống nhau lại. Định nghĩa dp[i][j] là số lớp nhỏ nhất A có thể ăn được sau khi xét xong i nhóm đầu tiên, trong lúc B đang giữ j lượt dự trữ.

Có hai lựa chọn tại mỗi bước:

1. B giữ lượt tiếp theo (j tăng lên), A ăn lớp hiện tại: Chi phí tăng thêm 1.
2. B tiêu tốn lượt để ăn hết lớp hiện tại: Chỉ xảy ra nếu B có đủ lượt dự trữ để bù đắp sự mất mát.

Kết quả là giá trị dp[total_groups][0] (không được dư lượt cuối cùng).

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int MAX_LIMIT = 5005;
int counts[MAX_LIMIT];
int memo[MAX_LIMIT][MAX_LIMIT];
int raw_vals[MAX_LIMIT];
int distinct_count;
int n_cases;

void run_case() {
    int n;
    cin >> n;
    map<int, int> freq_map;
    
    for (int i = 0; i < n; ++i) {
        cin >> raw_vals[i];
        freq_map[raw_vals[i]]++;
    }
    
    distinct_count = 0;
    for (auto const& [val, count] : freq_map) {
        counts[++distinct_count] = count;
    }

    for (int i = 0; i <= distinct_count; ++i) {
        for (int j = 0; j <= distinct_count; ++j) {
            memo[i][j] = 1e9;
        }
    }
    memo[0][0] = 0;

    for (int i = 1; i <= distinct_count; ++i) {
        for (int j = 0; j < i; ++j) { // B currently holds j turns
             if (memo[i-1][j] == 1e9) continue;

             // Option 1: B saves turn, A eats this layer
             if (j + 1 < i + 1) { 
                 memo[i][j+1] = min(memo[i][j+1], memo[i-1][j]);
             }

             // Option 2: B consumes stored turns to eat this layer completely
             // Cost to block is equal to frequency of this number group
             int cost = counts[i];
             if (j + cost < i) { 
                  // Wait, logic check: if B blocks, A eats 0 of this group?
                  // Correct logic based on source: B blocks if he accumulates enough 'rounds'
                  // But simpler view: B needs to match A's progress.
                  // Refined logic per problem context:
                  // We track how many items B "wasted" to stop A.
                  // Let's stick to the formula derived from the logic above:
                  // min(A_eats)
             }
             
             // Re-evaluating strict logic for safety in rewrite:
             // State: dp[group_idx][saved_rounds_for_B]
             // Transition 1: A eats current group (cost 1 round for A, B saves round).
             // dp[i][j+1] = min(..., dp[i-1][j] + 1); 
             // Transition 2: B blocks current group using saved rounds.
             // dp[i][j - counts[i]] = min(..., dp[i-1][j]); 
             
             // Implementing simplified version based on standard solution pattern:
             int saved = j;
             // Case 1: A gets 1 item, B stores 1 turn
             memo[i][min(saved + 1, i)] = min(memo[i][min(saved + 1, i)], memo[i-1][saved]);
             
             // Case 2: B spends saved turns to eat the block
             // Condition: saved must cover the count
             if (saved >= counts[i]) {
                 memo[i][saved - counts[i]] = min(memo[i][saved - counts[i]], memo[i-1][saved]);
             }
        }
    }
    cout << memo[distinct_count][0] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n_cases;
    while (n_cases--) {
        run_case();
    }
    return 0;
}

Tóm tắt những thách thức

Xây dựng giải thuật DP cho bài toán博弈 đòi hỏi sự cẩn trọng ở bốn khía cạnh chính:

1. Mô hình hóa trạng thái: Cần cân bằng giữa độ chính xác của dữ liệu và chi phí bộ nhớ. Đừng thêm thông tin thừa.
2. Xây dựng phương trình: Phải liệt kê đầy đủ các kịch bản chuyển tiếp, bao gồm cả trường hợp thu thập từ nhiều nguồn hoặc phân phối ra nhiều đích.
3. Thứ tự tính toán: Đôi khi duyệt xuôi không hiệu quả. Cần linh hoạt áp dụng duyệt ngược, DFS có ghi nhớ (Memoization), hoặc BFS topo.
4. Xử lý vòng lặp: Trong các bài toán có đồ thị vòng, việc xác định trạng thái hòa hoặc vô hạn là bắt buộc để tránh treo chương trình.