結果
| 問題 |
No.298 話の伝達
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:04:08 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,121 bytes |
| コンパイル時間 | 345 ms |
| コンパイル使用メモリ | 82,344 KB |
| 実行使用メモリ | 140,872 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:01 |
| 合計ジャッジ時間 | 8,098 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 WA * 1 TLE * 1 -- * 4 |
ソースコード
import sys
# Increase recursion depth limit. The maximum recursion depth could potentially be N,
# although typical depth might be related to the longest path in the DAG.
# Setting it to a value somewhat larger than N should be safe.
# N <= 20, so 20*2 = 40 is small. Let's set it higher for safety margin.
try:
sys.setrecursionlimit(2050)
except OverflowError: # Some systems might have a hard limit
pass
# Read N, M from input
N, M = map(int, sys.stdin.readline().split())
# Create an adjacency list representation for predecessors.
# `adj[B]` will store a list of tuples `(A, P)`, where A is a predecessor of B,
# and P is the probability (C/100.0) of transmission from A to B.
adj = {}
for i in range(N):
adj[i] = [] # Initialize empty list for each node 0 to N-1
# Read M relationships and populate the adjacency list
for _ in range(M):
A, B, C = map(int, sys.stdin.readline().split())
# The problem guarantees A != B.
# Store predecessor A and its transmission probability C/100.0 for node B.
adj[B].append((A, C / 100.0))
# Memoization table (cache) to store computed probabilities P(S).
# Keys are integer bitmasks representing subsets S. Values are the computed probabilities.
memo = {}
# Define the recursive function to compute P(S), the probability that *all* nodes
# in the set S start talking about the topic.
# S is represented by an integer bitmask `mask`.
def compute_P(mask):
"""
Computes the probability that all nodes specified by the set bits in 'mask'
eventually start talking about the topic. Uses recursion with memoization.
P(S) = P(intersection_{v in S} S_v) where S_v is the event node v starts talking.
"""
# Base case 1: P(emptyset) = 1.0. The intersection over an empty set of events is the whole sample space.
# This is important for the recursion logic when mask_without_k becomes 0.
if mask == 0:
return 1.0
# Base case 2: P({0}) = 1.0. Group 0 starts the conversation by definition.
# The mask `1` represents the set {0}.
if mask == 1:
return 1.0
# Check if the result for this mask is already computed and stored in the memo table.
if mask in memo:
return memo[mask]
# Identify the node 'k' with the highest index among nodes in the set S represented by 'mask'.
# `mask.bit_length() - 1` gives the index of the most significant bit set in the mask.
k = mask.bit_length() - 1
# Retrieve the list of predecessors for node k from the adjacency list.
# Use adj.get(k, []) to safely handle cases where k might not be in adj keys (though it should be).
predecessors = adj.get(k, [])
# If node k is not node 0 (i.e., k > 0) and has no predecessors, it can never start talking.
# Therefore, the probability P(S) that all nodes in S (including k) start talking must be 0.
# Note: Since mask > 1, k must be > 0 in this function body after base cases.
if not predecessors:
memo[mask] = 0.0
return 0.0
# Calculate the mask representing the set S \ {k}.
# This is done by flipping the k-th bit using XOR operation.
mask_without_k = mask ^ (1 << k)
# Initialize the total probability for the current calculation using Inclusion-Exclusion Principle.
total_prob = 0.0
num_preds = len(predecessors)
# Iterate through all non-empty subsets J of the predecessors of k.
# A subset J is represented by an integer 'i' from 1 to 2^num_preds - 1.
# Each bit in 'i' corresponds to a predecessor in the `predecessors` list.
for i in range(1, 1 << num_preds):
# Calculate the product of transmission probabilities for predecessors in the current subset J.
current_J_prob_product = 1.0
# Determine the mask for the recursive call: It starts with S \ {k}.
recursive_mask = mask_without_k
subset_J_size = 0 # Keep track of the size of the subset J, |J|.
# Iterate through the indices of the predecessors list to check which ones are in J.
for j_idx in range(num_preds):
# Check if the j_idx-th predecessor is included in subset J (check j_idx-th bit of i).
if (i >> j_idx) & 1:
pred_node, pred_prob = predecessors[j_idx]
# Multiply the probabilities for this edge into the product for J.
current_J_prob_product *= pred_prob
# Add the predecessor node `pred_node` to the set required for the recursive call.
# The recursive call needs P(S \ {k} U A_J), where A_J = {pred_node | j_idx-th pred is in J}.
# Set the corresponding bit for `pred_node` in `recursive_mask`.
recursive_mask |= (1 << pred_node)
subset_J_size += 1 # Increment the size of J.
# Make the recursive call to compute P(S \ {k} U A_J).
# Multiply by the product of probabilities for transmissions from A_J to k.
term = compute_P(recursive_mask) * current_J_prob_product
# Apply the sign according to the Inclusion-Exclusion Principle based on the size of J.
# If |J| is odd, the term has a positive sign (+).
# If |J| is even, the term has a negative sign (-).
if subset_J_size % 2 == 1:
total_prob += term
else:
total_prob -= term
# Store the computed probability for the current mask `mask` in the memo table.
memo[mask] = total_prob
# Return the computed probability.
return total_prob
# Handle the trivial case where N=1. The only group is 0.
# It starts talking with probability 1, and it is also the target group N-1.
if N == 1:
print(f"{1.0:.10f}")
else:
# The target is group N-1. We need to compute P({N-1}).
# The mask representing the set {N-1} is 1 shifted left by (N-1).
target_mask = 1 << (N - 1)
# Call the function to compute the probability for the target set {N-1}.
result = compute_P(target_mask)
# Print the final result formatted to 10 decimal places as required.
print(f"{result:.10f}")