AGC010F Tree Game

Let \( val[u] \) represent the number of stones located at node \( u \). A useful heuristic arises when considering a node \( u \) with a single child \( v \). If \( val[u] \le val[v] \), and the first player moves the token to \( v \), the second player can immediately move it back to \( u \). This traps the first player, leading to a loss. Consequent, we can deduce that moving a token to a node with a strictly greater value is never an optimal strategy.

To solve the problem, we iterate through every node as a potential starting position, treating that node as the root of the tree. We define a state \( dp[u] \) which is true if the player whose turn it is can force a win starting from node \( u \), assuming the subtree is rooted accordingly.

The transition is as follows: \( dp[u] \) is true if and only if there exists a child \( v \) of \( u \) such that \( val[v] < val[u] \) and \( dp[v] \) is false. If the current player moves to such a \( v \), the opponent faces a losing position: moving back up to \( u \) allows the original player to descend again, while moving down with in the subtree is already guaranteed to be a losing move for the opponent.

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

using namespace std;

const int MAX_N = 3005;
vector<int> adj[MAX_N];
int nodeValues[MAX_N];
bool winState[MAX_N];

bool determineWin(int currentNode, int parentNode) {
    winState[currentNode] = false;
    for (int neighbor : adj[currentNode]) {
        if (neighbor == parentNode) continue;
        if (nodeValues[neighbor] >= nodeValues[currentNode]) continue;
        
        if (!determineWin(neighbor, currentNode)) {
            winState[currentNode] = true;
        }
    }
    return winState[currentNode];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int numNodes;
    cin >> numNodes;
    
    for (int i = 1; i <= numNodes; ++i) {
        cin >> nodeValues[i];
    }
    
    for (int i = 0; i < numNodes - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= numNodes; ++i) {
        fill(winState, winState + numNodes + 1, false);
        if (determineWin(i, 0)) {
            cout << i << " ";
        }
    }
    
    return 0;
}

AGC002E Candy Piles

This problem requires a clever transformation. First, sort the pile sizes in descending order. We can visualize the piles as a Ferrers diagram or a histogram.

If we list the piles as \( h_1, h_2, \dots, h_n \), the diagram is formed by columns where the \( i \)-th column has height \( h_i \).

The two operations become: 1. Removing the bottom row (equivalent to taking one candy from every non-empty pile). 2. Removing the leftmost column (equivalent to taking the entire smallest pile).

This transforms the game into moving a token from the bottom-left corner \((1, 1)\) of the diagram. The token can move either Up (corresponding to removing a row) or Right (corresponding to removing a column). A key observation is that cells on the same diagonal share the same game outcome (N-position or P-position). This can be proven by contradiction.

Thus, the state of \((1, 1)\) is identical to the state of \((i, i)\) where \( i \) is the largest index such that \( h_i \ge i \). We need to determine if \((i, i)\) is a winning position for the first player.

From \((i, i)\), the moves are: 1. Up: There are \( h_i - i \) steps vertically. The first player wins if this distance is odd. 2. Right: The token moves to columns where the height is at least \( i \). Let \( j \) be the furthest column index such that \( h_j = i \). The horizontal distance is \( j - i \). The first player wins if this distance is odd.

If either condition is met, the first player wins.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> heights(n);
    for (int i = 0; i < n; ++i) {
        cin >> heights[i];
    }
    
    sort(heights.rbegin(), heights.rend());
    
    // Find the largest i such that h[i] >= i (1-based index logic)
    // Loop conditions are adapted to avoid bounds checking
    for (int i = 0; i < n; ++i) {
        // Check if this is the boundary where condition fails for next
        if (i + 1 < n && heights[i + 1] < i + 2) {
            int index = i + 1; // 1-based
            
            bool moveUpWins = ((heights[i] - index) % 2) != 0;
            bool moveRightWins = false;
            
            // Count piles with height exactly equal to index (which is i+1)
            // starting from i+1
            int j = i + 1;
            while (j < n && heights[j] >= index) {
                if (heights[j] == index) {
                    moveRightWins = !moveRightWins;
                }
                j++;
            }
            
            if (moveUpWins || moveRightWins) {
                cout << "First" << endl;
            } else {
                cout << "Second" << endl;
            }
            return 0;
        }
    }
    
    // Default fallback if loop completes without finding boundary
    // (e.g. strictly decreasing sequence)
    cout << "Second" << endl;
    return 0;
}

P5363 [SDOI2019] Moving Coins

This problem involves moving coins on a line segment. The crucial observation is that moving a coin generally only affects the distances (gaps) between adjacent coins. The state of the game can be described entirely by these gaps.

If we treat the gap between the rightmost coin and the endpoint as the 0-th pile, and the gaps to the left as piles 1, 2, etc., the game maps perfectly to Staircase Nim.

In Staircase Nim, a player wins if the XOR of the pile sizes at odd indices (1, 3, 5...) is non-zero. Therefore, we need to count the number of configurations where the XOR of these specific gaps is 0 (losing positions), and subtract this from the total number of configurations.

Since XOR is a bitwise operation, we can use a dynamic programming approach handling one bit at a time. Let \( dp[bit][count] \) be the number of ways to distribute stones considering the first \( bit \) bits, using \( count \) total stones, such that the XOR of odd-indexed piles is 0.

For a specific bit, the number of odd-indexed piles where this bit is set must be even. If we let \( oddCount \) be the number of odd-indexed piles, we select \( k \) of them to have this bit set (where \( k \) is even). The transition involves combinatorial selection \( C(oddCount, k) \). Finally, we distribute the remaining stones to the even-indexed piles and odd-indexed piles (for higher bits) using standard combinations.

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 9;
const int MAX_BIT = 30;
const int MAX_STONES = 4e5 + 5;

long long fact[MAX_STONES];
long long invFact[MAX_STONES];
long long dp[MAX_BIT][MAX_STONES];

long long fastPow(long long base, int exp) {
    long long res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return ((fact[n] * invFact[k]) % MOD) * invFact[n - k] % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    // Precompute factorials and modular inverses
    fact[0] = 1;
    for (int i = 1; i < MAX_STONES; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invFact[MAX_STONES - 1] = fastPow(fact[MAX_STONES - 1], MOD - 2);
    for (int i = MAX_STONES - 2; i >= 0; --i) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
    
    int oddPiles = (m + 1) / 2;
    int evenPiles = m - oddPiles + 1; // Including pile 0
    int maxGapSum = n - m;
    
    dp[0][0] = 1;
    
    for (int bit = 1; bit < MAX_BIT; ++bit) {
        int weight = 1 << (bit - 1);
        for (int currentSum = 0; currentSum <= maxGapSum; ++currentSum) {
            long long ways = 0;
            // k must be even
            for (int k = 0; k <= oddPiles; k += 2) {
                if (k * weight <= currentSum) {
                    ways = (ways + dp[bit - 1][currentSum - k * weight] * comb(oddPiles, k)) % MOD;
                }
            }
            dp[bit][currentSum] = ways;
        }
    }
    
    long long losingStates = 0;
    // Calculate total losing configurations
    for (int used = 0; used <= maxGapSum; ++used) {
        // Distribute remaining stones to even piles
        long long ways = (dp[MAX_BIT - 1][used] * 
                         comb(maxGapSum - used + evenPiles - 1, evenPiles - 1)) % MOD;
        losingStates = (losingStates + ways) % MOD;
    }
    
    long long totalStates = comb(n, m);
    long long answer = (totalStates - losingStates + MOD) % MOD;
    
    cout << answer << endl;
    return 0;
}

P2490 [SDOI2011] Black and White Chess

This problem follows a similar structure to the previous one but applies the mechanics of K-Nim. The distances between tokens again define the piles, but the win condition depends on the XOR of piles modulo a specific parameter or constraint related to K.