← 返回 sofi 的题目列表RunCollection: Simulate chance of matching or beating personal best
类型:online_judge
Coding: Monte Carlo probability that an in-progress run matches or beats the personal best
You are implementing a statistics system for obstacle-course racing.
A Course has obstacle_count obstacles.
A Run stores the time (seconds) spent on each completed obstacle. A run may be incomplete.
A RunCollection stores multiple runs for the same course and can compute the personal best time.
Implement in RunCollection:
chance_of_personal_best(current_run) -> float
Given an in-progress current_run (possibly incomplete), estimate the probability that once completed it will beat or tie the current personal best.
Model:
For each remaining obstacle i not yet completed in current_run, its completion time is drawn uniformly at random from all recorded times for obstacle i across all other runs in the collection.
Incomplete historical runs contribute only the obstacles they actually completed.
Simulation:
Run 10,000 trials:
Sample times for each missing obstacle from its pool.
Compute total time for the completed run.
Count success if total time <= RunCollection.personal_best().
Return successes / 10,000.
Accuracy:
The returned value should be consistently within ±0.02 of the true probability.
Assumptions:
current_run.course == self.course
At least one historical run exists.
Performance note:
Precompute per-obstacle sampling pools to avoid scanning all runs inside each trial.
Examples:
[[3,3,2],[3,3,3]], current [3,3] => probability 1/2.
[[3,3,2,3],[3,3,3,2],[5,5,2]], current [3,3] => probability 5/6.
Constraints:
obstacle_count: 1..10,000
number of runs: 1..10,000
trials: 10,000
Example
Input
# Example 1
course_obstacles=3
runs=[[3,3,2],[3,3,3]]
current=[3,3]
Output
~0.50 (value should be in [0.48, 0.52])