結果
| 問題 |
No.174 カードゲーム（Hard）
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,950 bytes |
| コンパイル時間 | 1,100 ms |
| コンパイル使用メモリ | 120,396 KB |
| 実行使用メモリ | 90,656 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:45 |
| 合計ジャッジ時間 | 4,523 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 TLE * 1 -- * 9 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
#include <unordered_map> // Use unordered_map for potentially better average performance than map
#include <iomanip>
#include <cmath> // For basic math functions if needed
// Platform-specific optimizations for bit manipulation intrinsics
// Check compiler and include intrinsics if available
#if defined(__GNUC__) || defined(__clang__)
// GCC or Clang: use built-in functions __builtin_ctz and __builtin_popcount
#define custom_ctz(x) __builtin_ctz(x)
#define custom_popcount(x) __builtin_popcount(x)
#elif defined(_MSC_VER)
// MSVC: use intrinsics _BitScanForward and __popcnt
#include <intrin.h>
// Define custom_ctz equivalent for MSVC
inline unsigned long msvc_bsf_ulong(unsigned long mask) {
unsigned long index;
// _BitScanForward returns non-zero if a set bit is found and sets index.
// Returns zero if mask is zero.
if (_BitScanForward(&index, mask)) return index;
// The behavior of __builtin_ctz(0) is undefined.
// In this code, ctz is called inside loops `while (mask > 0)`, ensuring mask is non-zero.
// So we don't need to worry about mask=0 case here.
// If it were possible, we might return a special value like -1 or handle it explicitly.
return 0; // Default return, should not be reached for non-zero mask
}
#define custom_ctz(x) (int)msvc_bsf_ulong((unsigned long)(x))
// Define custom_popcount equivalent for MSVC
#define custom_popcount(x) (int)__popcnt((unsigned int)(x))
#else
// Fallback implementations if no specific intrinsics are detected/available
// This implementation of ctz finds the index of the least significant bit
int fallback_ctz(int mask) {
if (mask == 0) return 0; // Define behavior for 0 mask, though likely unused here
int count = 0;
// Check bits from right to left (0-indexed)
while ((mask & 1) == 0) {
mask >>= 1;
count++;
// Add safety break for potentially large integers, though int is usually 32 bits
if (count >= 32) return -1; // Indicate error or handle appropriately
}
return count;
}
// This implementation of popcount counts the number of set bits
int fallback_popcount(int mask) {
int count = 0;
while (mask > 0) {
mask &= (mask - 1); // This clears the least significant set bit
count++;
}
return count;
}
#define custom_ctz(x) fallback_ctz(x)
#define custom_popcount(x) fallback_popcount(x)
#endif
using namespace std;
int N; // Number of cards per player
double PA, PB; // Probabilities for A and B to play their smallest card
vector<int> A_sorted, B_sorted; // Sorted lists of initial cards for A and B
// Using unordered_map for memoization. Key is a combination of two masks.
// Key type is long long to accommodate up to 40 bits (20 for each player).
unordered_map<long long, double> memo;
// Recursive function to calculate expected score with memoization
double dp(int mask_A, int mask_B) {
// Base case: if no cards are left, expected score is 0
if (mask_A == 0) {
return 0.0;
}
// Create a unique key for the current state (mask_A, mask_B)
// Shift mask_A left by 20 bits (since N <= 20) and OR with mask_B
long long state_key = ((long long)mask_A << 20) | mask_B;
// Check if the result for this state is already memoized
auto it = memo.find(state_key);
if (it != memo.end()) {
return it->second; // Return cached result
}
// Calculate the number of cards remaining for each player (k)
int k = custom_popcount(mask_A);
// Find the indices of the minimum value cards currently held by A and B
// This relies on the cards being sorted initially. The LSB set in the mask corresponds to the minimum available card.
int min_A_idx = custom_ctz(mask_A);
int min_B_idx = custom_ctz(mask_B);
double expected_value = 0.0; // Accumulator for the expected score from this state
// Calculate the probability of playing a non-minimum card
// Handle the case k=1 separately to avoid division by zero
double prob_A_other = (k <= 1) ? 0.0 : (1.0 - PA) / (double)(k - 1.0);
double prob_B_other = (k <= 1) ? 0.0 : (1.0 - PB) / (double)(k - 1.0);
// Iterate through all possible cards A can play using bit manipulation
// This loop iterates through each set bit in mask_A
int current_mask_A = mask_A;
while (current_mask_A > 0) {
// Get the index 'i' of the least significant set bit (current card A to consider)
int i = custom_ctz(current_mask_A);
int card_A = A_sorted[i]; // Get the actual card value
double prob_A; // Probability A plays this card
// Determine the probability A plays card_A based on the rules
if (k == 1) { // If only one card left, must play it
prob_A = 1.0;
} else { // Otherwise, depends if it's the minimum card
prob_A = (i == min_A_idx) ? PA : prob_A_other;
}
// Iterate through all possible cards B can play using bit manipulation
int current_mask_B = mask_B;
while (current_mask_B > 0) {
// Get the index 'j' of the least significant set bit (current card B to consider)
int j = custom_ctz(current_mask_B);
int card_B = B_sorted[j]; // Get the actual card value
double prob_B; // Probability B plays this card
// Determine the probability B plays card_B based on the rules
if (k == 1) { // If only one card left, must play it
prob_B = 1.0;
} else { // Otherwise, depends if it's the minimum card
prob_B = (j == min_B_idx) ? PB : prob_B_other;
}
// Calculate the score A gets in this specific match if A wins (card_A > card_B)
double current_score = (card_A > card_B) ? (double)(card_A + card_B) : 0.0;
// Determine the masks for the next state by removing the played cards
// Use XOR to toggle the bit corresponding to the played card's index
int next_mask_A = mask_A ^ (1 << i);
int next_mask_B = mask_B ^ (1 << j);
// Recursively call dp for the next state and add the weighted contribution
// The total expected score is the immediate score + expected future score
expected_value += prob_A * prob_B * (current_score + dp(next_mask_A, next_mask_B));
// Clear the least significant set bit in current_mask_B to move to the next card for B
current_mask_B &= current_mask_B - 1;
}
// Clear the least significant set bit in current_mask_A to move to the next card for A
current_mask_A &= current_mask_A - 1;
}
// Store the computed expected value in the memoization table before returning
return memo[state_key] = expected_value;
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input values N, PA, PB
cin >> N >> PA >> PB;
// Read card values for players A and B
vector<int> A_cards(N), B_cards(N);
for (int i = 0; i < N; ++i) cin >> A_cards[i];
for (int i = 0; i < N; ++i) cin >> B_cards[i];
// Create sorted copies of the card lists
A_sorted = A_cards;
B_sorted = B_cards;
sort(A_sorted.begin(), A_sorted.end());
sort(B_sorted.begin(), B_sorted.end());
// Calculate the initial mask where all bits are set (representing all cards available)
// (1 << N) - 1 creates a mask with N set bits: 11...1 (N times)
int initial_mask = (1 << N) - 1;
// Call the recursive DP function starting from the initial state (all cards available)
double result = dp(initial_mask, initial_mask);
// Output the final result with the required precision
cout << fixed << setprecision(15) << result << endl;
return 0;
}