結果
| 問題 |
No.1687 What the Heck?
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:18:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,897 bytes |
| コンパイル時間 | 896 ms |
| コンパイル使用メモリ | 85,008 KB |
| 実行使用メモリ | 13,312 KB |
| 最終ジャッジ日時 | 2025-05-14 13:19:14 |
| 合計ジャッジ時間 | 3,122 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 WA * 10 |
ソースコード
#include <iostream>
#include <vector>
#include <set>
#include <numeric> // Not used in the final solution, but often useful in competitive programming
#include <algorithm> // Used for std::prev
#include <iterator> // Included for std::prev
/*
* Problem Description Analysis:
* The problem asks us to find the maximum possible value of (Takeda's total score) - (Suzuki's total score).
* Takeda knows Suzuki's sequence of card plays P = (P_1, P_2, ..., P_N).
* Takeda has cards {1, 2, ..., N} and must use each card exactly once over N rounds.
* In round i (1 <= i <= N), Takeda plays card T_i and Suzuki plays P_i.
* Scoring for round i:
* - If T_i > P_i: Takeda gets i points. Contribution to difference: +i.
* - If P_i > T_i: Suzuki gets i points. Contribution to difference: -i.
* - If T_i = P_i: No points awarded. Contribution to difference: 0.
* Takeda needs to choose their sequence of plays T = (T_1, ..., T_N) such that the total score difference is maximized.
* T must be a permutation of {1, ..., N}.
*
* Constraints:
* N is up to 2 * 10^5. This suggests an O(N log N) or O(N) solution. O(N^2) is likely too slow.
* The maximum score difference can be large, potentially up to N*(N+1)/2, which requires a 64-bit integer type (long long in C++).
*
* Greedy Strategy:
* Consider the rounds in decreasing order of importance, i.e., from round N down to round 1. Round N has the highest potential point gain/loss (N), round N-1 has N-1 points, and so on.
* For each round i, Takeda wants to achieve the best possible outcome: Win > Draw > Lose.
* Let C_avail be the set of Takeda's available cards at the start of round i.
*
* Decision process for round i:
* 1. Can Takeda win? Check if there exists any card t in C_avail such that t > P_i.
* If yes: Takeda should win. To maximize future potential, Takeda should use the "cheapest" winning card, i.e., the minimum available card t > P_i. This saves larger cards which might be needed to win future rounds against high P_j values. Contribution: +i.
* 2. If Takeda cannot win: Can Takeda draw? Check if card P_i is in C_avail.
* If yes: Takeda should draw. Play card P_i. This outcome (0 points) is better than losing (-i points). Contribution: 0.
* 3. If Takeda cannot win or draw: Takeda must lose. This means all available cards t satisfy t < P_i.
* Takeda must play one of these cards. To maximize future potential, Takeda should use the "most expensive" losing card, i.e., the maximum available card t < P_i. This saves smaller cards which might be useful to win/draw against small P_j values in future rounds (rounds with smaller i). Contribution: -i.
*
* Implementation using std::set:
* `std::set<int>` can efficiently maintain the set of available cards.
* - Insert all cards 1 to N initially: O(N log N).
* - In round i:
* - Find minimum card > P_i: Use `available_cards.upper_bound(P_i)`. O(log N).
* - Check if P_i is available: Use `available_cards.find(P_i)`. O(log N).
* - Find maximum available card: Use `*available_cards.rbegin()` or `*std::prev(available_cards.end())`. O(1) or O(log N) depending on access method.
* - Remove a card: Use `available_cards.erase()`. O(log N).
* Total time complexity: O(N log N).
* Total space complexity: O(N) for storing P and the set.
* This fits within the typical limits for N = 2 * 10^5.
*/
int main() {
// Faster I/O operations for competitive programming
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of cards and rounds
std::cin >> N;
// Use 1-based indexing for the P array to align with problem statement rounds 1..N.
// The vector size is N+1, indices 1 to N will store Suzuki's card plays. Index 0 is unused.
std::vector<int> P(N + 1);
// Read Suzuki's card plays for each round
for (int i = 1; i <= N; ++i) {
std::cin >> P[i];
}
// A set to store the card numbers currently available for Takeda to play.
// std::set keeps elements sorted, enabling efficient search operations (log N).
std::set<int> available_cards;
for (int k = 1; k <= N; ++k) {
available_cards.insert(k);
}
// Variable to store the total score difference (Takeda's score - Suzuki's score).
// Use long long because the score difference can exceed the range of a 32-bit integer for large N.
long long total_score_diff = 0;
// Iterate through the rounds in decreasing order of point value, from N down to 1.
// This greedy approach prioritizes making the best decision for rounds with the highest impact first.
for (int i = N; i >= 1; --i) {
int p_i = P[i]; // Suzuki's card played in round i
// --- Strategy Step 1: Try to WIN using the smallest possible winning card ---
// Find the smallest card in `available_cards` that is strictly greater than `p_i`.
// `upper_bound(p_i)` returns an iterator to the first element in the set that is greater than `p_i`.
auto it_win = available_cards.upper_bound(p_i);
if (it_win != available_cards.end()) {
// A winning card exists. `it_win` points to the smallest such card.
// Play this card to win the round.
total_score_diff += (long long)i; // Takeda wins round i. Score difference increases by i.
available_cards.erase(it_win); // Remove the played card from the available set.
} else {
// Cannot win because no available card is greater than `p_i`.
// --- Strategy Step 2: Try to DRAW ---
// Check if the card `p_i` itself is available in Takeda's hand.
auto it_draw = available_cards.find(p_i);
if (it_draw != available_cards.end()) {
// Card `p_i` is available. Play it to achieve a draw.
// Score difference does not change in a draw (0 points awarded to both).
// No need to update total_score_diff += 0;
available_cards.erase(it_draw); // Remove the played card.
} else {
// --- Strategy Step 3: Must LOSE ---
// Cannot win and cannot draw. Takeda must play a card smaller than `p_i`.
// All remaining available cards must be less than `p_i`.
// Greedy choice: Play the largest available card (which is necessarily < p_i).
// This uses up the "least useful" card among the losing options, preserving smaller cards
// which might be more valuable in later (lower point value) rounds.
// Check if the set is empty. This is a safeguard; based on the game logic,
// the set should not be empty while there are still rounds to play (i >= 1).
if (!available_cards.empty()) {
// Find the largest element in the set.
// `std::prev(available_cards.end())` returns a forward iterator to the last (maximum) element.
auto fwd_it_lose = std::prev(available_cards.end());
total_score_diff -= (long long)i; // Takeda loses round i. Score difference decreases by i.
available_cards.erase(fwd_it_lose); // Remove the played card.
}
// else case: This block should not be reached under normal circumstances.
// If N >= 1, the loop runs for i from N down to 1. In each iteration, one card is removed.
// The set `available_cards` starts with N elements and becomes empty only after the loop finishes.
}
}
}
// Output the final maximum achievable score difference. Add a newline character at the end.
std::cout << total_score_diff << std::endl;
return 0; // Indicate successful execution
}