เกม "100 Game" แบบปรับเปลี่ยน: มีตัวเลข 1 ถึง maxChoosableInteger (ไม่ซ้ำ ไม่ได้เลือกซ้ำ) 2 ผู้เล่นสลับกันเลือก ตัวเลขที่เลือกจะบวกเข้า Running Total ผู้ที่ทำให้ Total ≥ desiredTotal **ชนะ**
สมมติทั้งคู่เล่น **Optimal** หาว่า **Player 1 (First Player) ชนะได้หรือไม่**
Constraints
maxChoosableInteger ≤ 20-> State Space = 2^20 ≈ 1 ล้าน (พอสำหรับ Bitmask DP)desiredTotal ≤ 300
ตัวอย่าง
maxChoosableInteger = 20, desiredTotal = 11 -> false
Player 1 เลือกอะไรก็ตาม Player 2 ตอบโต้ได้ทำให้ Player 1 แพ้
แนวทาง: Minimax + Bitmask DP (Memoization)
State = mask (Bitmask ของตัวเลขที่ **ยังเหลือเลือกได้**) + remainingTotal
solve(mask, remaining)= Current Player ชนะได้หรือไม่จาก State นี้- Base:
remaining <= 0-> Current Player **แพ้** (เพราะ Player ก่อนหน้าทำให้ถึง Target แล้ว) - Transition: ลองเลือกทุกตัว
iที่ยังเหลือ (bit i = 1)- ถ้า
!solve(mask ^ (1<<i), remaining - i)-> 对手แพ้ -> เราชนะ -> Return true
- ถ้า
- Memoize ผลลัพธ์ใน
dp[mask]
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[1 << 21]; // 2^21 states, -1=uncomputed, 0=false, 1=true
bool solve(int n, int remaining, int mask) {
if (remaining <= 0) return false; // Previous player won
if (dp[mask] != -1) return dp[mask];
bool canWin = false;
for (int i = 1; i <= n; i++) {
if (!(mask & (1 << i))) continue; // Already used (bit=0 means used in this encoding)
// Wait: mask encoding in original code: bit=1 means available? Let's check.
// Original: if(!((mask >> i) & 1)) -> bit i is 0 -> available
// So mask: 0=available, 1=used. We'll stick to original logic.
}
// Corrected based on original logic:
// mask bit i = 1 means USED. 0 means AVAILABLE.
}
// Let's rewrite clearly:
bool solve(int n, int remaining, int mask) {
if (remaining <= 0) return false; // Opponent just won
if (dp[mask] != -1) return dp[mask];
bool ret = false;
for (int i = 1; i <= n; i++) {
if (!((mask >> i) & 1)) { // Bit i is 0 -> Available
// Choose i, mark as used (set bit i to 1)
// Next state: opponent's turn with remaining - i
// If opponent CANNOT win from there -> WE WIN
ret |= (!solve(n, remaining - i, mask ^ (1 << i)));
}
}
return dp[mask] = ret;
}
bool canIWin(int n, int desiredTotal) {
if (desiredTotal <= 0) return true;
fill(begin(dp), end(dp), -1);
// Quick check: sum of all numbers < desiredTotal -> impossible to reach -> first player loses
if (desiredTotal > n * (n + 1) / 2) return false;
return solve(n, desiredTotal, 0); // mask=0: all bits 0 -> all available
}
};
Input / Output
Input: 10 11 Output: 0 (false)
ความซับซ้อน (Complexity)
- States: 2^n (n ≤ 20 -> ~1M)
- Time: O(n * 2^n) — แต่ละ State ลูป n ตัว
- Space: O(2^n) — DP Array
จุดสำคัญ (Key Points)
- Bitmask Encoding: Bit = 1 = Used, Bit = 0 = Available (ตามโค้ดต้นฉบับ)
- Minimax Logic:
ret |= !solve(...)-> เราชนะได้ถ้ามีการเลือกทำให้ **คู่ต่อสู้แพ้** - Pruning:
desiredTotal > sum(1..n)-> False ทันที
Classic Game Theory + Bitmask DP Problem ครับ
