結果
| 問題 |
No.173 カードゲーム（Medium）
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:08 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,080 bytes |
| コンパイル時間 | 1,204 ms |
| コンパイル使用メモリ | 112,944 KB |
| 実行使用メモリ | 7,840 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:36 |
| 合計ジャッジ時間 | 6,263 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 TLE * 1 -- * 7 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <map> // Use map for memoization and storing distributions
#include <vector>
#include <algorithm>
#include <iomanip>
#include <utility> // For pair
using namespace std;
int N; // Number of cards per player / number of matches
double PA, PB; // Probabilities for A and B to play their smallest card
vector<int> A_cards_initial, B_cards_initial; // Initial hands for A and B
// Memoization table: maps state (mask_A, mask_B) to the probability distribution of final score differences
// The distribution map maps score difference (int) to probability (double)
map<pair<int, int>, map<int, double>> memo;
// Helper function to get the list of currently available cards for a player based on their mask
// Returns a vector of pairs: {card_value, original_index}
// The original index is needed to update the bitmask correctly
vector<pair<int, int>> get_cards(int mask, const vector<int>& initial_cards) {
vector<pair<int, int>> current_cards;
// Efficiently count bits to reserve space, might offer minor speedup
current_cards.reserve(__builtin_popcount(mask));
for (int i = 0; i < N; ++i) {
// If the i-th bit is set in the mask, the i-th card from the initial hand is available
if ((mask >> i) & 1) {
current_cards.push_back({initial_cards[i], i});
}
}
return current_cards;
}
// Recursive function with memoization to calculate the probability distribution of final score differences
// state is defined by the masks representing remaining cards for A and B
map<int, double> solve(int mask_A, int mask_B) {
// Base case: No cards left. The game ends. Score difference from this point is 0 with probability 1.0.
if (mask_A == 0) {
return {{0, 1.0}};
}
// Define the current state using the masks
pair<int, int> state = {mask_A, mask_B};
// Check if the result for this state is already computed and stored in the memo table
auto it = memo.find(state);
if (it != memo.end()) {
return it->second; // Return cached result
}
// Get the current hands for A and B based on the masks
vector<pair<int, int>> current_A_cards = get_cards(mask_A, A_cards_initial);
vector<pair<int, int>> current_B_cards = get_cards(mask_B, B_cards_initial);
// k is the number of cards remaining for each player
int k = current_A_cards.size();
// Initialize the resulting distribution for the current state
map<int, double> res_dist;
// Case 1: Only one card left for each player (k=1)
// They must play these cards. Probability of this move is 1.0.
if (k == 1) {
int val_A = current_A_cards[0].first; // A's card value
int idx_A = current_A_cards[0].second; // A's card original index
int val_B = current_B_cards[0].first; // B's card value
int idx_B = current_B_cards[0].second; // B's card original index
// Calculate the score difference change for this match
int score_diff_change = 0;
if (val_A > val_B) { // A wins the match
score_diff_change = val_A + val_B;
} else { // B wins the match (cards are distinct, so val_B > val_A)
score_diff_change = -(val_A + val_B);
}
// The next state has masks with the played cards removed (becomes empty masks)
// Recursively call `solve` for the next state. This will hit the base case.
map<int, double> sub_dist = solve(mask_A ^ (1 << idx_A), mask_B ^ (1 << idx_B));
// Update the result distribution for the current state
// For each possible final score difference D_sub from the subproblem,
// the final score difference from the current state is (score_diff_change + D_sub).
// The probability p_sub is carried over.
for (auto const& [D_sub, p_sub] : sub_dist) {
res_dist[score_diff_change + D_sub] += p_sub;
}
} else { // Case 2: Two or more cards left for each player (k >= 2)
// Find the minimum card value and its original index for player A
int min_A_val = 1001, min_A_idx = -1; // Initialize min_A_val > max possible card value
for(const auto& p : current_A_cards) {
if (p.first < min_A_val) {
min_A_val = p.first;
min_A_idx = p.second;
}
}
// Find the minimum card value and its original index for player B
int min_B_val = 1001, min_B_idx = -1; // Initialize min_B_val > max possible card value
for(const auto& p : current_B_cards) {
if (p.first < min_B_val) {
min_B_val = p.first;
min_B_idx = p.second;
}
}
// Iterate over all possible pairs of cards that A and B can play
for (const auto& pA : current_A_cards) {
int val_A = pA.first;
int idx_A = pA.second;
double prob_A; // Probability that A plays this card `val_A`
// Calculate probability based on A's strategy
if (idx_A == min_A_idx) { // A plays the smallest card
prob_A = PA;
} else { // A plays a card other than the smallest
// k >= 2 is guaranteed in this branch
prob_A = (1.0 - PA) / (k - 1);
}
for (const auto& pB : current_B_cards) {
int val_B = pB.first;
int idx_B = pB.second;
double prob_B; // Probability that B plays this card `val_B`
// Calculate probability based on B's strategy
if (idx_B == min_B_idx) { // B plays the smallest card
prob_B = PB;
} else { // B plays a card other than the smallest
// k >= 2 is guaranteed in this branch
prob_B = (1.0 - PB) / (k - 1);
}
// Probability of this specific pair (A plays val_A, B plays val_B) occurring
double prob_pair = prob_A * prob_B;
// Optimization: If probability is negligible, skip computation for this pair
// Using a small epsilon threshold
if (prob_pair < 1e-18) continue;
// Calculate the score difference change for this match
int score_diff_change = 0;
if (val_A > val_B) { // A wins the match
score_diff_change = val_A + val_B;
} else { // B wins the match
score_diff_change = -(val_A + val_B);
}
// Determine the masks for the next state by removing the played cards
// Use XOR to toggle the corresponding bit off
int next_mask_A = mask_A ^ (1 << idx_A);
int next_mask_B = mask_B ^ (1 << idx_B);
// Recursively call `solve` for the next state
map<int, double> sub_dist = solve(next_mask_A, next_mask_B);
// Update the result distribution for the current state
// Aggregate probabilities from the subproblem outcomes
for (auto const& [D_sub, p_sub] : sub_dist) {
// The final score difference `score_diff_change + D_sub` occurs with probability `prob_pair * p_sub`
res_dist[score_diff_change + D_sub] += prob_pair * p_sub;
}
}
}
}
// Store the computed distribution in the memo table before returning
return memo[state] = res_dist;
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input values: N, PA, PB
cin >> N >> PA >> PB;
// Resize vectors to hold N cards each
A_cards_initial.resize(N);
B_cards_initial.resize(N);
// Read initial cards for player A
for (int i = 0; i < N; ++i) cin >> A_cards_initial[i];
// Read initial cards for player B
for (int i = 0; i < N; ++i) cin >> B_cards_initial[i];
// The initial state has all cards available for both players
// The mask `(1 << N) - 1` has the lower N bits set to 1.
int initial_mask = (1 << N) - 1;
// Call the recursive function starting from the initial state
// This computes the probability distribution of the final score difference
map<int, double> final_dist = solve(initial_mask, initial_mask);
// Calculate the total probability that player A wins
// A wins if the final score difference (A's score - B's score) is strictly positive (D > 0)
double prob_A_wins = 0.0;
for (auto const& [D, p] : final_dist) { // Iterate through the final distribution map
if (D > 0) { // Check if score difference is positive
prob_A_wins += p; // Add the probability of this outcome to the total
}
}
// Print the final result with high precision
cout << fixed << setprecision(17) << prob_A_wins << endl;
return 0;
}