Hiểu bài toán

Bài toán mô tả một trò chơi xập xệ (card game) giữa 2 người chơi, Tí và Tèo, trên một bộ bài đặc biệt gồm n lá bài được đánh số từ 1 đến n (lá 1 ở dưới cùng, lá n ở trên cùng). Mỗi lá bài có màu Đỏ (1) hoặc Đen (0). Luật chơi: Hai người chơi luân phiên nhau bốc bài. Mỗi lượt, một người có thể bốc từ 1 đến k lá bài (không được vượt quá số bài còn lại).

Điểm số của một người trong một lượt bốc bằng chính số lượng lá bài Đỏ trong số bài vừa bốc. Mục tiêu cuối cùng là tổng điểm của người chơi nào cao hơn thì người đó thắng.

Đề bài yêu cầu: Với thông tin trước về màu sắc các lá bài và giá trị k, cả hai người chơi đều chơi tối ưu (chiến thuật). Hãy xác định:

1. Ai là người thắng? (In 'YES' nếu có người thắng, 'NO' nếu hòa).
2. Nếu có người thắng, in ra tổng điểm của người thua cuộc.

Lưu ý quan trọng: Do thứ tự bốc là từ trên xuống (lá có chỉ số cao nhất trước), ta có thể coi các lá bài được xếp thành một dãy từ trái sang phải (lá n, n-1, ..., 1). Ván bài bắt đầu từ lá đầu tiên (lá n).

Các cách tiếp cận

Cách Quy hoạch động (Dynamic Programming)

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

using namespace std;

int main() {
    int k, n;
    if (!(cin >> k >> n)) return 0;
    string s;
    cin >> s;

    // Duyệt theo thứ tự từ trái sang phải (từ trên xuống)
    // dp[i]: điểm số tối đa người chơi hiện tại có thể đạt được 
    // khi bắt đầu lượt chơi tại vị trí i (tức là các lá bài từ i đến n-1 đã được bốc)
    // Hoặc hiểu theo cách khác: hiệu số điểm (điểm người hiện tại - điểm người tiếp theo)
    // nếu người hiện tại bắt đầu bốc tại vị trí i.

    vector<int> dp(n + 1, 0);
    // base case: nếu bắt đầu tại n (không còn bài), điểm là 0.

    for (int i = n - 1; i >= 0; --i) {
        int red_count = 0;
        // Thử tất cả các nước đi hợp lệ (bốc từ 1 đến k lá)
        int best_diff = -1e9;

        for (int j = 0; j < k && i + j < n; ++j) {
            if (s[i + j] == '1') red_count++;

            // Nếu bốc j+1 lá, điểm mình nhận là red_count.
            // Phần còn lại bắt đầu từ i + j + 1, đối thủ sẽ chơi tối ưu.
            // Giá trị còn lại cho mình từ phần sau là -dp[i + j + 1]
            // (vì dp định nghĩa là diff của người bắt đầu)

            int current_diff = red_count - dp[i + j + 1];
            best_diff = max(best_diff, current_diff);
        }
        dp[i] = best_diff;
    }

    int diff = dp[0]; // Diff = Diem_Ti - Diem_Teo

    if (diff == 0) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        int total_red = 0;
        for (char c : s) if (c == '1') total_red++;

        if (diff > 0) { // Ti thắng
            // Diem_Ti + Diem_Teo = total_red
            // Diem_Ti - Diem_Teo = diff
            // => Diem_Teo = (total_red - diff) / 2
            cout << (total_red - diff) / 2 << endl;
        } else { // Teo thắng (diff < 0)
            // Diem_Teo - Diem_Ti = -diff
            // => Diem_Ti = (total_red - (-diff)) / 2 = (total_red + diff) / 2
            cout << (total_red + diff) / 2 << endl;
        }
    }

    return 0;
}

• Time Complexity: O(n * k)
• Space Complexity: O(n)

Đây là phương pháp chuẩn cho các trò chơi thông tin hoàn hảo (Perfect Information Game). Ta định nghĩa trạng thái là 'vị trí bắt đầu hiện tại'.

1. Quy hoạch động:

   • Gọi dp[i] là hiệu số điểm (điểm người chơi hiện tại - điểm người chơi tiếp theo) tối đa có thể đạt được khi bắt đầu bốc tại lá bài thứ i (theo thứ tự từ trên xuống).
   • Bài toán cơ sở: dp[n] = 0 (không còn bài).
   • Công thức truy hồi: Tại vị trí i, người chơi có thể bốc len lá bài (1 <= len <= k). Điểm nhận được là số lá đỏ trong len lá đó. Sau đó, đến lượt đối thủ bắt đầu tại i + len. Do dp[i + len] là hiệu số điểm của người bắt đầu tại i + len (tức là điểm của đối thủ trừ đi điểm của người chơi hiện tại ở phần còn lại), nên tổng hiệu số của người chơi hiện tại tại i là: dp[i] = max(red_count - dp[i + len]) với len chạy từ 1 đến k.

2. Tính toán kết quả:

   • dp[0] chính là Diem_Ti - Diem_Teo.
   • Nếu dp[0] == 0 thì hòa -> In 'NO'.
   • Nếu dp[0] != 0 -> In 'YES'.
   • Để tìm điểm của người thua, ta cần biết tổng điểm (Tổng số lá đỏ) và hiệu số.
     • Tong_Diem + Hieu_So = 2 * Diem_Thuong (nếu người thắng là người đi trước).
     • Công thức chung: Diem_Thua = (Tong_Diem - |dp[0]|) / 2.

Phương pháp này đảm bảo tìm ra đường đi tối ưu cho cả hai người.

Cách Tối ưu hóa Truy hồi (Sliding Window / Deque Optimization)

#include <iostream>
#include <vector>
#include <string>
#include <deque>

using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    string s;
    cin >> s;

    vector<int> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + (s[i] == '1');
    }

    vector<int> dp(n + 1, 0);
    deque<int> dq;
    dq.push_back(n); // Base case index

    for (int i = n - 1; i >= 0; --i) {
        // Loại bỏ các index nằm ngoài phạm vi k
        while (!dq.empty() && dq.front() > i + k) {
            dq.pop_front();
        }

        // dp[i] = (pref[i + len] - pref[i]) - dp[i + len]
        //        = pref[i + len] - (pref[i] + dp[i + len])
        // Ta cần max giá trị này
        // Tương đương max(pref[j] - dp[j]) với j trong [i+1, i+k]

        // Tiến hành cập nhật deque với các giá trị mới (index i+1)
        int val = pref[i + 1] - dp[i + 1];
        while (!dq.empty() && (pref[dq.back()] - dp[dq.back()]) <= val) {
            dq.pop_back();
        }
        dq.push_back(i + 1);

        int j = dq.front();
        dp[i] = pref[j] - pref[i] - dp[j];
    }

    int diff = dp[0];
    if (diff == 0) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        int total_red = pref[n];
        if (diff > 0) cout << (total_red - diff) / 2 << endl;
        else cout << (total_red + diff) / 2 << endl;
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Phương pháp này là phiên bản tối ưu của Quy hoạch động bằng cách loại bỏ vòng lặp duyệt k.

1. Phân tích công thức: dp[i] = max(red_count(i, len) - dp[i + len]) Mà red_count(i, len) = pref[i + len] - pref[i] => dp[i] = max( (pref[i + len] - dp[i + len]) - pref[i] )

   Trong đó i là cố định, pref[i] là cố định. Ta chỉ cần tìm max(pref[j] - dp[j]) trong khoảng j từ i + 1 đến i + k (đặt j = i + len).

2. Cách giải quyết:

   • Duyệt i từ n-1 về 0.
   • Duy trì một deque (hàng đợi hai đầu) lưu trữ các chỉ số j sao cho giá trị pref[j] - dp[j] giảm dần.
   • Khi duyệt tới i, ta biết giá trị pref[i+1] - dp[i+1] đã được tính toán.
   • Bước 1: Loại bỏ các j ở đầu deque nếu j > i + k (nằm ngoài phạm vi cho phép bốc).
   • Bước 2: Thêm i+1 vào deque (loại bỏ các phần tử ở cuối deque có giá trị pref[j] - dp[j] nhỏ hơn hoặc bằng giá trị mới).
   • Bước 3: dp[i] = pref[dq.front()] - pref[i] - dp[dq.front()].

Độ phức tạp giảm từ O(n*k) xuống O(n) do mỗi index được thêm và bớt khỏi deque đúng 1 lần.

Cách Greedy (Heuristic) - Sai

// Pseudocode minh hoa
int greedy(int current_pos, int k, string s) {
    int current_points = 0;
    // Logic sai: Luôn bốc max số lá đỏ có thể trong phạm vi k
    // Hoặc bốc nhiều nhất có thể
    // Logic này không đảm bảo tối ưu全局 vì không tính đến việc 
    // 'dồn' bài cho đối thủ hoặc để lại bài tốt cho lượt sau.
    return current_points;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Lưu ý: Đây là một cách tiếp cận thường bị hiểu lầm và dẫn đến sai lầm trong các bài toán game lý thuyết trò chơi.

• Giả định sai: Một số người chơi có thể nghĩ rằng chiến thuật tối ưu là "luôn bốc nhiều lá bài đỏ nhất có thể trong 1 lần bốc" hoặc "luôn bốc tối đa k lá".
• Tại sao sai? Trong game này, việc bốc bài không chỉ giúp bạn có điểm ngay lập tức mà còn quyết định ai sẽ là người bắt đầu ở mảng bài còn lại. Ví dụ, nếu bạn để lại một cụm bài đỏ cho đối thủ ở lượt sau, bạn có thể thua đậm hơn. Do đó, chỉ có Quy hoạch động mới đảm bảo tìm ra nước đi tối ưu absolutes.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Xác định hướng bài toán: Bài toán là một trò chơi đối kháng hoàn hảo (Perfect Information Game), do đó Quy hoạch động (Dynamic Programming) là công cụ phù hợp nhất.
• Định nghĩa trạng thái: Trạng thái của trò chơi được xác định hoàn toàn bởi số lượng bài còn lại. Do thứ tự bốc là từ trên xuống, ta có thể quy về chỉ số bắt đầu của phần bài còn lại.
• Cách tính kết quả cuối: Hiệu số điểm (Diff) giữa hai người chơi là dp[0]. Từ Diff và Tổng số lá đỏ (Tổng điểm), ta có thể suy ra điểm của người thua cuộc bằng công thức: Diem_Thua = (Tong_Diem - |Diff|) / 2.

Lỗi thường gặp

• Lầm tưởng về thứ tự bài: Người mới chơi thường bị nhầm lẫn giữa việc bài được bốc từ 'trên xuống' và cách nhập vào. Dãy đầu vào là từ lá 1 đến lá n, nhưng lá n nằm ở top. Cần xử lý chuỗi hoặc lặp ngược lại cho hợp lý.
• Quên kiểm tra điều kiện hòa: Đề bài yêu cầu in 'NO' nếu không ai thắng (tức hiệu số điểm bằng 0).
• Sử dụng Greedy thay cho DP: Cố gắng tìm một quy luật đơn giản để bốc bài (ví dụ: bốc tối đa k lá, hoặc bốc đến khi nào hết lá đỏ) sẽ không bao giờ đảm bảo tối ưu cho các test phức tạp.