結果
| 問題 |
No.102 トランプを奪え
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:02:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 139 ms / 5,000 ms |
| コード長 | 9,993 bytes |
| コンパイル時間 | 740 ms |
| コンパイル使用メモリ | 75,840 KB |
| 実行使用メモリ | 19,552 KB |
| 最終ジャッジ日時 | 2025-05-14 13:04:05 |
| 合計ジャッジ時間 | 1,651 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring> // For std::fill, requires <algorithm>, sometimes <cstring> helps with pointer arithmetic or related types? Included to be safe.
// Correct header for std::fill is <algorithm>. <cstring> is for C memory/string functions.
using namespace std;
// Store initial pile sizes globally
int N_initial[4];
// Store total number of cards globally
int total_cards;
// Constants defining maximum values based on problem constraints
const int MAXN = 13; // Maximum number of cards in a single pile
const int MAX_TOTAL_CARDS = 52; // Maximum total number of cards (13 * 4)
// Memoization table using a multi-dimensional array.
// Dimensions correspond to state variables: [n1][n2][n3][n4][h1][player]
// Sizes are MAXN+1 for pile sizes (0 to MAXN), MAX_TOTAL_CARDS+1 for Taro's hand size (0 to MAX_TOTAL_CARDS), and 2 for player (0 for Taro, 1 for Jiro).
int memo[MAXN + 1][MAXN + 1][MAXN + 1][MAXN + 1][MAX_TOTAL_CARDS + 1][2];
// A special value distinct from any possible score difference, used to indicate that a state has not been computed yet.
// The score difference h1 - h2 ranges from -total_cards to +total_cards. Minimum is -52, Maximum is +52.
const int UNCOMPUTED = -1e9; // -1 billion is safely outside the possible score range.
// Recursive function implementing the minimax algorithm with memoization (Dynamic Programming)
// State is defined by (n1, n2, n3, n4, h1, is_taro_turn)
// n1..n4: number of cards remaining in each pile
// h1: number of cards in Taro's hand
// is_taro_turn: boolean indicating whose turn it is (true for Taro, false for Jiro)
// Returns the maximum possible final score difference (h1 - h2) achievable from the given state, assuming optimal play.
int solve(int n1, int n2, int n3, int n4, int h1, bool is_taro_turn) {
// Base case: If all piles are empty, the game ends.
if (n1 == 0 && n2 == 0 && n3 == 0 && n4 == 0) {
// Calculate Jiro's final hand size (h2). Total cards = h1 + h2.
int h2 = total_cards - h1;
// Return the final score difference.
return h1 - h2;
}
// Determine the player index for accessing the memoization table: 0 for Taro, 1 for Jiro.
int player_idx = is_taro_turn ? 0 : 1;
// Use a reference to the memo table entry for efficiency. Avoids copying the state key.
int& memo_val = memo[n1][n2][n3][n4][h1][player_idx];
// Check if the result for this state has already been computed and stored in the memo table.
if (memo_val != UNCOMPUTED) {
return memo_val; // Return the memoized result.
}
// Calculate Jiro's current hand size (h2). This is needed for the card stealing logic.
// Total cards taken so far = total_cards - cards_remaining.
// And total cards taken = h1 + h2.
int cards_remaining = n1 + n2 + n3 + n4;
int cards_taken = total_cards - cards_remaining;
int h2 = cards_taken - h1;
// Defensive check: In a correct game flow, h1 and h2 should always be non-negative.
// Adding max(0, ...) ensures robustness against potential negative values due to bugs elsewhere, though ideally unnecessary.
// This check is important because division and ceiling/floor operations assume non-negative inputs based on game logic.
h1 = max(0, h1);
h2 = max(0, h2);
// Variable to store the best score achievable from the current state.
int best_score;
// Store current pile sizes in an array for easier iteration over possible moves.
int current_piles[4] = {n1, n2, n3, n4};
// Logic for Taro's turn (player 0). Taro wants to maximize the final score difference (h1 - h2).
if (is_taro_turn) {
// Initialize best_score to a very small value.
best_score = -1e9;
// Iterate through each of the four piles.
for (int i = 0; i < 4; ++i) {
// Check if the current pile is not empty.
if (current_piles[i] > 0) {
// Iterate through the possible number of cards to take (1, 2, or 3).
for (int k = 1; k <= min(3, current_piles[i]); ++k) {
// Calculate the state after Taro takes k cards from pile i.
int next_piles[4]; // Array to store the pile sizes for the next state.
for(int j=0; j<4; ++j) next_piles[j] = current_piles[j]; // Copy current pile sizes.
next_piles[i] -= k; // Update the size of the chosen pile.
int next_h1; // Calculate Taro's hand size for the next state.
if (next_piles[i] == 0) { // If Taro took the last card from pile i...
// Taro gains k cards taken, plus steals ceil(h2/2) cards from Jiro.
// ceil(x/2) can be calculated as (x + 1) / 2 using integer division.
next_h1 = h1 + k + (h2 + 1) / 2;
} else { // If pile i is not empty after taking k cards...
// Taro simply gains the k cards he took.
next_h1 = h1 + k;
}
// Recursively call solve for the next state, which will be Jiro's turn (false).
// Update best_score with the maximum score found among all possible moves.
best_score = max(best_score, solve(next_piles[0], next_piles[1], next_piles[2], next_piles[3], next_h1, false));
}
}
}
}
// Logic for Jiro's turn (player 1). Jiro wants to minimize the final score difference (h1 - h2).
else {
// Initialize best_score to a very large value.
best_score = 1e9;
// Iterate through each of the four piles.
for (int i = 0; i < 4; ++i) {
// Check if the current pile is not empty.
if (current_piles[i] > 0) {
// Iterate through the possible number of cards to take (1, 2, or 3).
for (int k = 1; k <= min(3, current_piles[i]); ++k) {
// Calculate the state after Jiro takes k cards from pile i.
int next_piles[4]; // Array to store the pile sizes for the next state.
for(int j=0; j<4; ++j) next_piles[j] = current_piles[j]; // Copy current pile sizes.
next_piles[i] -= k; // Update the size of the chosen pile.
int next_h1; // Calculate Taro's hand size for the next state.
if (next_piles[i] == 0) { // If Jiro took the last card from pile i...
// Jiro steals ceil(h1/2) cards from Taro. Taro's hand size becomes floor(h1/2).
// floor(x/2) is calculated as x / 2 using integer division.
next_h1 = h1 / 2;
} else { // If pile i is not empty after taking k cards...
// Taro's hand size remains unchanged.
next_h1 = h1;
}
// Jiro's hand size (h2) increases by k cards taken, plus any stolen cards.
// This change in h2 is implicitly handled by the calculation within the recursive call based on next_h1 and remaining cards.
// Recursively call solve for the next state, which will be Taro's turn (true).
// Update best_score with the minimum score found among all possible moves.
best_score = min(best_score, solve(next_piles[0], next_piles[1], next_piles[2], next_piles[3], next_h1, true));
}
}
}
}
// Store the computed best score for the current state in the memoization table before returning it.
return memo_val = best_score;
}
// Function to initialize the memoization table with the UNCOMPUTED value.
// This is done once at the beginning of the program.
void initialize_memo() {
// Calculate the total number of elements in the multi-dimensional memo array.
// Use size_t for potentially large sizes to avoid overflow.
size_t total_elements = (size_t)(MAXN + 1) * (MAXN + 1) * (MAXN + 1) * (MAXN + 1) * (MAX_TOTAL_CARDS + 1) * 2;
// Get a pointer to the first element of the memo array. This allows treating it as a flat 1D array for initialization.
int* p = &memo[0][0][0][0][0][0];
// Use std::fill (from <algorithm>) to efficiently set all elements to the UNCOMPUTED value.
std::fill(p, p + total_elements, UNCOMPUTED);
}
int main() {
// Optimize C++ standard input/output streams for faster execution.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read the initial number of cards in each of the four piles from standard input.
cin >> N_initial[0] >> N_initial[1] >> N_initial[2] >> N_initial[3];
// Calculate the total number of cards across all piles.
total_cards = 0;
for(int i=0; i<4; ++i) total_cards += N_initial[i];
// Initialize the memoization table. This ensures that we can detect uncomputed states.
initialize_memo();
// Call the recursive function `solve` to determine the outcome of the game starting from the initial state.
// Taro starts the game (is_taro_turn = true), and initially has 0 cards (h1 = 0).
int final_score_diff = solve(N_initial[0], N_initial[1], N_initial[2], N_initial[3], 0, true);
// Determine the winner based on the final score difference (h1 - h2).
if (final_score_diff > 0) {
// If the score difference is positive, Taro has more cards than Jiro.
cout << "Taro" << endl;
} else if (final_score_diff < 0) {
// If the score difference is negative, Jiro has more cards than Taro.
cout << "Jiro" << endl;
} else {
// If the score difference is zero, they have the same number of cards.
cout << "Draw" << endl;
}
return 0; // Indicate successful program execution.
}