Tóm tắt đề bài

Cho \(N\) số nguyên dương được xếp thành một vòng tròn. Hai người chơi (Chủ nợ và SPyofgame) lần lượt lấy các số theo quy tắc:

1. Người thứ nhất (Chủ nợ) chọn một số bất kỳ trên vòng tròn.
2. Từ lượt thứ hai, mỗi người phải chọn một số nằm kề với các số đã được lấy trước đó.
3. Trò chơi kết thúc khi toàn bộ các số đã được lấy hết.
4. Người thắng là người lấy được nhiều số lẻ hơn.

Giả sử cả hai đều chơi tối ưu, hãy đếm số lượng vị trí bắt đầu mà Chủ nợ có thể chọn để chắc chắn giành chiến thắng.

Phân tích

• Tính chất trò chơi: Sau khi Chủ nợ chọn số đầu tiên tại vị trí \(i\), vòng tròn bị "ngắt" và trở thành một dãy hàng đợi hai đầu (deque). Các số còn lại tạo thành một dãy tuyến tính từ vị trí \(i+1\) đến \(i+N-1\) (theo mô-đun \(N\)). Ở mỗi lượt tiếp theo, người chơi chỉ có thể chọn số ở một trong hai đầu của dãy còn lại này.
• Mục tiêu: Ta chỉ quan tâm đến tính chẵn lẻ của các số. Do đó, có thể thay thế \(a_i\) bằng \(a_i \pmod 2\). Bài toán trở thành: Tìm cách chọn số đầu tiên \(a_i\) sao cho hiệu số lượng số lẻ của Chủ nợ và SPyofgame là dương.
• Giới hạn: \(N \leq 100\), đây là giới hạn nhỏ, cho phép sử dụng các thuật toán có độ phức tạp \(O(N^2)\) hoặc \(O(N^3)\).

Hướng giải quyết

1. Chuyển đổi bài toán

• Nhân đôi mảng \(a\) thành dãy \(A\) có \(2N\) phần tử để xử lý vòng tròn: \(A = \{a_1, a_2, \dots, a_N, a_1, a_2, \dots, a_N\}\).
• Với mỗi vị trí bắt đầu \(i \in [1, N]\), Chủ nợ lấy \(a_i\), dãy còn lại là \(A[i+1 \dots i+N-1]\). Đây là bài toán trò chơi trên dãy số kinh điển.

2. Quy hoạch động (Dynamic Programming)

Gọi \(f[l][r]\) là hiệu số lượng số lẻ tối đa mà người đi trước có thể đạt được so với người đi sau khi xét đoạn \([l, r]\).

• Trường hợp cơ sở: Nếu \(l = r\), người đi trước lấy luôn số đó: \(f[l][l] = A[l] \pmod 2\).
• Công thức truy hồi: Người đi trước có hai lựa chọn:
  • Lấy \(A[l]\), khi đó người đi sau sẽ nhận được hiệu số tối ưu trên đoạn \([l+1, r]\) là \(f[l+1][r]\). Hiệu số lúc này là: \(A[l] \pmod 2 - f[l+1][r]\).
  • Lấy \(A[r]\), khi đó người đi sau sẽ nhận được hiệu số tối ưu trên đoạn \([l, r-1]\) là \(f[l][r-1]\). Hiệu số lúc này là: \(A[r] \pmod 2 - f[l][r-1]\).
• Người chơi tối ưu sẽ chọn giá trị lớn nhất:

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

Với mỗi vị trí \(i\) Chủ nợ chọn đầu tiên:

• Số lẻ Chủ nợ nhận được từ lượt đầu: \(E = a_i \pmod 2\).
• Hiệu số lẻ tối ưu SPyofgame đạt được ở các lượt sau trên đoạn \([i+1, i+N-1]\) là \(f[i+1][i+N-1]\).
• Tổng hiệu số lẻ của Chủ nợ so với SPyofgame là: \(D = E - f[i+1][i+N-1]\).
• Nếu \(D > 0\), Chủ nợ thắng. Ta tăng biến đếm kết quả.

Độ phức tạp

• Thời gian: \(O(N^2)\) để tính bảng phương án DP.
• Bộ nhớ: \(O(N^2)\) để lưu trữ bảng DP.

Code tham khảo

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

const int INF = 1e9;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> a(2 * n + 1);
    // dp[l][r] lưu hiệu số lẻ tối đa người đi trước có thể lấy hơn người đi sau trong đoạn [l, r]
    vector<vector<int>> dp(2 * n + 1, vector<int>(2 * n + 1, 0));

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        // Chỉ quan tâm tính chẵn lẻ
        a[i] = a[i + n] = x % 2;
        dp[i][i] = dp[i + n][i + n] = a[i];
    }

    // Quy hoạch động tính hiệu số tối ưu cho mọi đoạn độ dài từ 1 đến n-1
    for (int len = 2; len <= n; len++) { // len là độ dài đoạn xét
        for (int l = 1; l + len - 1 <= 2 * n; l++) {
            int r = l + len - 1;
            dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
        }
    }

    int win_count = 0;
    // Thử từng vị trí i mà Chủ nợ chọn đầu tiên
    for (int i = 1; i <= n; i++) {
        int first_pick = a[i];
        // Sau khi chọn i, dãy còn lại là đoạn [i+1, i+n-1]
        // SPyofgame sẽ là người đi trước trong đoạn này
        int diff_remaining = dp[i + 1][i + n - 1];

        // Hiệu số cuối cùng của Chủ nợ so với SPyofgame
        if (first_pick - diff_remaining > 0) {
            win_count++;
        }
    }

    cout << win_count << endl;

    return 0;
}