結果
| 問題 |
No.973 余興
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,669 bytes |
| コンパイル時間 | 843 ms |
| コンパイル使用メモリ | 81,748 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:21:00 |
| 合計ジャッジ時間 | 10,927 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 2 |
| other | AC * 11 TLE * 1 -- * 42 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
// Define a constant for maximum N + padding, useful for array declarations if needed
// Using N+2 size arrays/vectors to handle boundary checks gracefully (indices L+k > N or R-k < 1)
const int MAXN_PADDED = 5005 + 2;
// Global arrays for storing cream puff values and prefix sums
// Using 1-based indexing for easier mapping to problem statement indices L and R
long long a[MAXN_PADDED];
long long prefix_sum[MAXN_PADDED];
// DP table: win[L][R] will be true if the player whose turn it is can win starting from state [L, R]
// Otherwise, it will be false (meaning it's a losing state / P-position)
vector<vector<bool>> win;
// Helper function to calculate the sum of nutritional values for cream puffs in range [l, r]
// Uses prefix sums for O(1) time calculation.
// Inline suggests the compiler to replace the function call with its body, potentially minor speedup.
inline long long get_sum(int l, int r) { // 1-based indices
// If the range is invalid (left index > right index), the sum is 0
if (l > r) return 0;
// Calculate sum using precomputed prefix sums
return prefix_sum[r] - prefix_sum[l - 1];
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of cream puffs
long long X; // Maximum allowed calorie intake per turn
cin >> N >> X;
// Read nutritional values for each cream puff
for (int i = 1; i <= N; ++i) {
cin >> a[i];
}
// Calculate prefix sums for efficient range sum queries
prefix_sum[0] = 0;
for (int i = 1; i <= N; ++i) {
prefix_sum[i] = prefix_sum[i - 1] + a[i];
}
// Initialize the DP table `win` with size (N+2) x (N+2)
// All entries are initialized to false by default.
// False represents a losing state (P-position). True represents a winning state (N-position).
win.resize(N + 2, vector<bool>(N + 2, false));
// Dynamic Programming approach: Iterate through all possible contiguous subsegments [L, R]
// We compute the win/loss status for shorter segments first, building up to the full segment [1, N].
// Outer loop iterates over the length of the subsegment.
for (int length = 1; length <= N; ++length) {
// Inner loop iterates over the starting position L of the subsegment.
for (int L = 1; L <= N - length + 1; ++L) {
int R = L + length - 1; // Calculate the ending position R based on L and length
// Find k_max_L: the maximum number of cream puffs `k` that can be eaten from the left end (starting at L)
// such that the total nutritional value does not exceed X.
// We use a linear scan which is efficient if k_max_L is typically small.
int k_max_L = 0;
long long current_sum_L = 0;
for (int k = 1; k <= length; ++k) {
current_sum_L += a[L + k - 1]; // Add the next cream puff's value
if (current_sum_L <= X) {
k_max_L = k; // Update max k if sum is within limit
} else {
break; // Sum exceeds X, cannot eat more from this end
}
}
// Find k_max_R: similar calculation for eating from the right end (starting at R).
int k_max_R = 0;
long long current_sum_R = 0;
for (int k = 1; k <= length; ++k) {
current_sum_R += a[R - k + 1]; // Add the next cream puff's value (from right)
if (current_sum_R <= X) {
k_max_R = k; // Update max k
} else {
break; // Sum exceeds X
}
}
// Determine if the current state [L, R] is a winning state.
// A state is winning if there exists at least one move to a losing state for the opponent.
bool found_winning_move = false;
// Check possible moves from the left end: eating k = 1 to k_max_L puffs.
for (int k = 1; k <= k_max_L; ++k) {
int next_L = L + k; // New left index after eating k puffs
int next_R = R; // Right index remains the same
// Check if the move ends the game (results in an empty segment)
if (next_L > next_R) {
// In misere play, the player making the move that empties the segment loses.
// Therefore, this is not a winning move for the current player.
continue;
}
// If the resulting state [next_L, next_R] is a losing state for the opponent (!win[next_L][next_R]),
// then the current player has found a winning move.
if (!win[next_L][next_R]) {
found_winning_move = true;
break; // Found a winning move, no need to check further moves from left
}
}
// If no winning move was found by eating from the left, check moves from the right end.
if (!found_winning_move) {
// Check possible moves from the right end: eating k = 1 to k_max_R puffs.
for (int k = 1; k <= k_max_R; ++k) {
int next_L = L; // Left index remains the same
int next_R = R - k; // New right index after eating k puffs
// Check if the move ends the game
if (next_L > next_R) {
// This move makes the current player lose. Not a winning move.
continue;
}
// If the resulting state [next_L, next_R] is a losing state for the opponent,
// then the current player has found a winning move.
if (!win[next_L][next_R]) {
found_winning_move = true;
break; // Found a winning move
}
}
}
// Update the DP table: state [L, R] is winning if a winning move was found.
win[L][R] = found_winning_move;
}
}
// The final result depends on the status of the initial state [1, N].
// If win[1][N] is true, the first player (A) has a winning strategy.
// Otherwise, the second player (B) has a winning strategy.
if (win[1][N]) {
cout << "A" << endl;
} else {
cout << "B" << endl;
}
return 0;
}