結果
| 問題 |
No.425 ジャンケンの必勝法
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 6,265 bytes |
| コンパイル時間 | 1,253 ms |
| コンパイル使用メモリ | 100,612 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:54 |
| 合計ジャッジ時間 | 1,780 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 18 |
ソースコード
#include <iostream> // For standard input/output operations (cin, cout)
#include <vector> // For using std::vector dynamic arrays
#include <cmath> // For mathematical functions like std::abs, std::max, std::min
#include <iomanip> // For output formatting like std::fixed and std::setprecision
#include <algorithm> // Required for std::max and std::min functions
int main() {
// Optimize standard input/output operations for faster execution
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int P0_percent, Q_percent; // Input variables for initial p (p0) and change q, as percentages
// Read the integer percentage values for p0 and q from standard input
std::cin >> P0_percent >> Q_percent;
// Convert percentage values P0_percent and Q_percent to integer indices/parameters P0 and Q.
// P0 represents the initial probability p after the first draw, as k in k/100.
// Q represents the change in probability p after subsequent draws, as k in k/100.
int P0 = P0_percent;
int Q = Q_percent;
// E[k] will store the probability that Negi eventually wins the game,
// given that the current round follows a draw and Negi's probability
// of using the winning strategy in this round is k/100.
// There are 101 possible states for k, corresponding to percentages 0% through 100%.
std::vector<double> E(101);
// Initialize the probability vector E. A reasonable initial guess can speed up convergence.
// 0.5 is a neutral guess. Initializing with 0.0 also works but might take slightly longer.
for (int k = 0; k <= 100; ++k) {
E[k] = 0.5; // Initial guess for the probability
}
// E_new is used to store the updated values of E in each iteration without interfering
// with calculations within the same iteration that depend on previous E values.
std::vector<double> E_new(101);
// max_diff tracks the maximum absolute change in any E[k] value during an iteration.
// Used to check for convergence. Initialized to a value > tolerance.
double max_diff = 1.0;
int iterations = 0; // Counts the number of iterations performed.
// Set a maximum number of iterations to prevent infinite loops in edge cases (though unlikely here).
const int MAX_ITERATIONS = 10000;
// Set the convergence tolerance. This should be smaller than the required output precision (10^-6).
// Using 1e-12 provides a good margin of safety.
const double CONVERGENCE_TOLERANCE = 1e-12;
// This loop implements the value iteration method to solve the system of linear equations for E_k.
// It continues until the values converge (max_diff <= tolerance) or max iterations are reached.
while (max_diff > CONVERGENCE_TOLERANCE && iterations < MAX_ITERATIONS) {
max_diff = 0.0; // Reset max_diff for the current iteration
// Iterate through all possible states k (representing probability p = k/100)
for (int k = 0; k <= 100; ++k) {
// Determine the indices for the states reached after a draw, depending on strategy choice.
// If Negi used the winning strategy (prob p=k/100) and drew, the next state's probability index is max(0, k-Q).
int prev_k_idx = std::max(0, k - Q);
// If Negi did not use the winning strategy (prob 1-p) and drew, the next state's index is min(100, k+Q).
int next_k_idx = std::min(100, k + Q);
// Apply the derived recurrence relation for E[k]:
// E_k = P(Win this round | p=k/100) + Sum over draw outcomes [ P(Draw outcome) * E[next state] ]
// The simplified equation is:
// E_k = (k+200)/600 + (k/200)*E[prev_k_idx] + ((100-k)/300)*E[next_k_idx]
// Calculate the constant term (related to winning probability in the current round)
// Need to cast k to double for floating point division
E_new[k] = (static_cast<double>(k) + 200.0) / 600.0;
// Add contributions from future states, weighted by the probability of reaching them via a draw
// Term related to using the winning strategy and drawing: (k/100) * (1/2) * E[prev_k_idx] = (k/200) * E[prev_k_idx]
E_new[k] += (static_cast<double>(k) / 200.0) * E[prev_k_idx];
// Term related to not using the winning strategy and drawing: (1 - k/100) * (1/3) * E[next_k_idx] = ((100-k)/300) * E[next_k_idx]
E_new[k] += ( (100.0 - static_cast<double>(k)) / 300.0) * E[next_k_idx];
// Calculate the absolute difference between the new value and the old value for convergence check.
double diff = std::abs(E_new[k] - E[k]);
// Update max_diff if the current difference is the largest seen in this iteration.
if (diff > max_diff) {
max_diff = diff;
}
}
// After calculating all new values, update the E vector for the next iteration.
// std::vector assignment performs a deep copy.
E = E_new;
iterations++; // Increment iteration counter
}
// After the loop finishes (either convergence or max iterations), E[P0] holds the computed probability
// that Negi wins eventually, given that the first draw occurred and the initial probability p was p0 = P0/100.
double final_E_P0 = E[P0];
// Calculate the final answer: The overall probability that Negi wins the game starting from the first round.
// P(Negi wins) = P(Negi wins Round 1) + P(Draw Round 1) * P(Negi wins eventually | Draw Round 1)
// In the first round, both play randomly: P(Win R1) = 1/3, P(Draw R1) = 1/3.
// P(Win eventually | Draw R1) is exactly what E[P0] represents.
// Therefore, P(Negi wins) = 1/3 + (1/3) * E[P0]
double result = 1.0/3.0 + (1.0/3.0) * final_E_P0;
// Output the final computed probability with the required precision.
// std::fixed ensures decimal notation. std::setprecision(15) ensures enough decimal places for the required tolerance.
std::cout << std::fixed << std::setprecision(15) << result << std::endl;
return 0; // Indicate successful execution
}