結果

問題 No.1613 Rush and Remove
ユーザー qwewe
提出日時 2025-05-14 13:20:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 3,715 bytes
コンパイル時間 1,133 ms
コンパイル使用メモリ 97,500 KB
実行使用メモリ 814,464 KB
最終ジャッジ日時 2025-05-14 13:22:01
合計ジャッジ時間 4,045 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 4 MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>

// Mask type for column configuration. std::vector<bool> is specialized
// and works as a key in std::map.
using Mask = std::vector<bool>;

// Memoization table for Grundy values of column states.
std::map<Mask, int> memo;
// Global H to be accessible in the recursive function easily.
int H_global;

// Calculates Grundy value for a given column configuration.
int calculate_grundy_for_column(const Mask& current_mask) {
    // Check if already computed.
    if (memo.count(current_mask)) {
        return memo[current_mask];
    }

    // Base case: if the column is empty, Grundy value is 0.
    // Check if all elements are false.
    bool all_empty = true;
    for (int i = 0; i < H_global; ++i) {
        if (current_mask[i]) {
            all_empty = false;
            break;
        }
    }
    if (all_empty) {
        return memo[current_mask] = 0;
    }

    std::set<int> reachable_grundy_values;

    // Iterate over each possible piece to select.
    // r_idx is the 0-indexed row of the piece.
    for (int r_idx = 0; r_idx < H_global; ++r_idx) {
        if (!current_mask[r_idx]) {
            continue; // No piece at this row.
        }

        // Piece at r_idx (0-indexed) selected. This corresponds to problem's i = r_idx + 1.
        // Choose i* (1-indexed) from 1 to i (i.e., r_idx + 1).
        // Convert i* to 0-indexed new_top_r_idx = i* - 1.
        // So, new_top_r_idx ranges from 0 to r_idx.
        for (int new_top_r_idx = 0; new_top_r_idx <= r_idx; ++new_top_r_idx) {
            // Cells for new pieces are new_top_r_idx to r_idx-1 (0-indexed).
            // These must be empty.
            bool placement_possible = true;
            for (int k = new_top_r_idx; k < r_idx; ++k) {
                if (current_mask[k]) {
                    placement_possible = false;
                    break;
                }
            }

            if (!placement_possible) {
                continue;
            }

            // If placement is possible, construct the next state.
            Mask next_mask = current_mask;
            next_mask[r_idx] = false; // Remove piece from r_idx.

            // Place new pieces.
            for (int k = new_top_r_idx; k < r_idx; ++k) {
                next_mask[k] = true;
            }
            
            // Recursively find Grundy value of the next state and add to set.
            reachable_grundy_values.insert(calculate_grundy_for_column(next_mask));
        }
    }

    // Calculate Mex of the set of reachable Grundy values.
    int mex = 0;
    while (reachable_grundy_values.count(mex)) {
        mex++;
    }
    
    return memo[current_mask] = mex;
}


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

    int H, W;
    std::cin >> H >> W;
    H_global = H; // Set global H

    std::vector<std::string> board_str(H);
    for (int i = 0; i < H; ++i) {
        std::cin >> board_str[i];
    }

    int total_nim_sum = 0;

    for (int j = 0; j < W; ++j) { // Iterate over each column
        Mask column_mask(H);
        // Populate mask for current column
        for (int i = 0; i < H; ++i) {
            if (board_str[i][j] == 'o') {
                column_mask[i] = true;
            } else {
                column_mask[i] = false;
            }
        }
        // Calculate Grundy value for this column and XOR with total.
        total_nim_sum ^= calculate_grundy_for_column(column_mask);
    }

    if (total_nim_sum != 0) {
        std::cout << "First" << std::endl;
    } else {
        std::cout << "Second" << std::endl;
    }

    return 0;
}
0