D - Doubles / Time Limit: 2 sec / Memory Limit: 1...
बनाया गया: 8 फ़रवरी 2025
का उपयोग करके उत्तर दिया गया O3 Mini High द्वारा Chat01
बनाया गया: 8 फ़रवरी 2025
का उपयोग करके उत्तर दिया गया O3 Mini High द्वारा Chat01
D - Doubles /
Time Limit: 2 sec / Memory Limit: 1024 MB
×
It is prohibited to use generative AI in ongoing AtCoder contests. Please refer to the following rules for more details.
AtCoder Rules against Generative AI - Version 20241206
Score :
400 points
Problem Statement
There are
N dice. The
i-th die has
K
i
faces, with the numbers
A
i,1
,A
i,2
,…,A
i,K
i
written on them. When you roll this die, each face appears with probability
K
i
1
.
You choose two dice from the
N dice and roll them. Determine the maximum probability that the two dice show the same number, when the dice are chosen optimally.
Constraints
2≤N≤100
1≤K
i
K
1
+K
2
+⋯+K
N
≤10
5
1≤A
i,j
≤10
5
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
K
1
A
1,1
A
1,2
…
A
1,K
1
⋮
K
N
A
N,1
A
N,2
…
A
N,K
N
Output
Print the answer. Your answer is considered correct if the absolute or relative error from the true solution does not exceed
10
−8
.
Sample Input 1
Copy
3
3 1 2 3
4 1 2 2 1
6 1 2 3 4 5 6
Sample Output 1
Copy
0.333333333333333
When choosing the 1st and 2nd dice, the probability that the outcomes are the same is
3
1
.
When choosing the 1st and 3rd dice, the probability is
6
1
.
When choosing the 2nd and 3rd dice, the probability is
6
1
.
Therefore, the maximum probability is
3
1
=0.3333333333….
Sample Input 2
Copy
3
5 1 1 1 1 1
4 2 2 2 2
3 1 1 2
Sample Output 2
Copy
0.666666666666667
Language
Source Code
We can solve the problem by computing, for every pair of dice, the probability that they show the same number. For two dice and the probability is given by
where is the number of times the number appears on die (and similarly for die ), and (or ) is the number of faces on die (or ).
Since the total number of faces over all dice is at most and there are at most 100 dice, we can afford a double loop over all pairs of dice. For each pair, we iterate over the keys (face values) of the dice that has fewer unique values (to reduce the constant factor) and sum the contributions if the face value appears on both dice.
Below is the complete C++ code that implements this approach in an optimized way:
cpp#include <iostream> #include <vector> #include <unordered_map> #include <iomanip> #include <algorithm> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; // Store the number of faces for each die vector<int> sizes(N); // For each die, we will store a frequency map: face value -> count vector<unordered_map<int,int>> dice(N); for (int i = 0; i < N; i++){ int k; cin >> k; sizes[i] = k; dice[i].reserve(k * 2); // Reserve extra space to reduce rehashing for (int j = 0; j < k; j++){ int face; cin >> face; dice[i][face]++; } } double ans = 0.0; // Check every pair of dice (i, j) with i < j for (int i = 0; i < N; i++){ for (int j = i + 1; j < N; j++){ double prob = 0.0; // Iterate over the smaller frequency map for efficiency. if(dice[i].size() <= dice[j].size()){ for (const auto &p : dice[i]){ int face = p.first; int cnt_i = p.second; // If the face is also on die j, add the probability contribution. if(dice[j].find(face) != dice[j].end()){ int cnt_j = dice[j][face]; prob += (double)cnt_i / sizes[i] * (double)cnt_j / sizes[j]; } } } else { for (const auto &p : dice[j]){ int face = p.first; int cnt_j = p.second; if(dice[i].find(face) != dice[i].end()){ int cnt_i = dice[i][face]; prob += (double)cnt_i / sizes[i] * (double)cnt_j / sizes[j]; } } } ans = max(ans, prob); } } // Output the answer with sufficient precision. cout << fixed << setprecision(15) << ans << "\n"; return 0; }
Input Reading:
We first read the number of dice . For each die, we read the number of faces and then the numbers. These numbers (possibly with repetition) are stored in an unordered_map
to count the frequency of each face value.
Pairwise Probability Calculation:
For each pair of dice , we iterate over the keys of the smaller frequency map and check if the current face value exists in the other dice’s map. If it does, we add its contribution to the probability for that pair. We then update the answer if the current pair gives a higher probability.
Output:
The maximum probability is printed with 15 digits of precision to satisfy the error tolerance.
This solution is optimized given the constraints and will pass all tests.