TopCoder SRM 579 - 1000: RockPaperScissors

Problem Statement

在一个袋子里有n个骰子，每个骰子有300面，第i个骰子ai面上有石头，bi面上有布，ci面上有骰子。
游戏持续n轮，每一轮你需要从石头、剪刀、布中选择一个，
然后从袋子中等概率随机取出一个骰子，并滚动它来产生你对手的手势。
接着这个骰子会被扔掉。

注意，你只知道这次滚动的结果，却不知道取出的骰子是哪一个。
每一轮胜利获得3分，平局获得1分，失败不得分。
你需要求出最优策略下你的期望得分。
n<=50，0<=ai,bi,ci<=300，ai+bi+ci=300。

Rock-paper-scissors is a famous hand game played by two people. In this game, each of the players forms one of three possible hand gestures: rock, paper, or scissors. Both players do so at the same time, and they show their gesture to the opponent. The result of the game is determined by the two gestures shown. If they are the same, the game is a draw. Otherwise, the winning player is determined by the following rules:

Rock defeats scissors.
Scissors defeat paper.
Paper defeats rock.

In this problem, you are going to play rock-paper-scissors against a bag of dice. There are N dice in the bag. Each dice has some faces that show a picture of a rock, others with a picture of paper, and the remaining faces show scissors. On the outside, all dice look the same, so you cannot distinguish between them. However, on the inside each die can be biased in a different way. That is, if you roll a particular die, the probability of getting each of the three gestures is not necessarily uniform.

Your game will take N turns. The game starts with all N dice inside the bag. In each turn, you first choose a gesture you want to play. Then you choose a random die from the bag and roll it to generate your opponent's move. The die is then thrown away. (Hence, after all N turns are over, the bag will be empty, and you played against each die exactly once.)

The games you play against the dice are scored as follows:

For each win you get 3 points.
For each draw you get 1 point.
For each loss you get 0 points.

You are given three int[]s: rockProb, paperProb, and scissorsProb. For each i, when die number i is cast, the probability that it will choose rock is rockProb[i] / 300.0. Similarly, paperProb[i] / 300.0 and scissorsProb[i] / 300.0 are the probabilities of getting paper and scissors on die i.

Your task is to find the strategy for this game that maximizes the expected total number of points you get. Compute and return the best possible expected score.

Definition

Class RockPaperScissors
Method bestScore
Parameters vector<int> , vector<int> , vector<int>
Returns double
Method signature double bestScore(vector<int> rockProb, vector<int> paperProb, vector<int> scissorsProb)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

Your return value must have a relative or an absolute error of less than 1e-9.

Constraints

rockProb will contain between 1 and 50 elements, inclusive.
paperProb and scissorsProb will each contain the same number of elements as rockProb.
Each element of rockProb, paperProb and scissorsProb will be between 0 and 300, inclusive.
For each i, rockProb[i]+paperProb[i]+scissorsProb[i] will be exactly 300.

Test cases

input
- rockProb { 100, 100, 100 }
- paperProb { 100, 100, 100 }
- scissorsProb { 100, 100, 100 }
output
Returns 3.999999999999999

note

In this case, all the given dice are uniform. Therefore, your strategy does not matter. In each turn, your expected score is 3*(1/3) + 1*(1/3) + 0*(1/3) = 4/3. The total expected score is therefore 3 * 4/3 = 4.
input
- rockProb { 300 }
- paperProb { 0 }
- scissorsProb { 0 }
output
Returns 3.0

note

There is only one die, and it always shows rock. You should choose paper and you are guaranteed to win and score 3 points.
input
- rockProb { 300, 0, 0 }
- paperProb { 0, 300, 0 }
- scissorsProb { 0, 0, 300 }
output
Returns 6.333333333333332

note

In your first turn the probability of seeing each gesture is the same. Thus regardless of your choice, your expected score for this turn is 4/3. However, in the second turn you already know which die has been removed from the bag. This helps you play better. For example, if the first die showed rock, you know that only paper and scissors are left. The optimal strategy in this situation is to choose scissors: with probability 1/2 you win, and with probability 1/2 you draw. Thus the expected score for the second turn is 3*(1/2) + 1*(1/2) = 2. In the third turn you know what to play to win. The expected total score is 4/3 + 2 + 3 = 6.333333333.
input
- rockProb { 100, 0 }
- paperProb { 200, 100 }
- scissorsProb { 0, 200 }
output
Returns 3.7222222222222223
input
- rockProb { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
- paperProb { 150, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300 }
- scissorsProb { 150, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
output
Returns 149.00000000000003

back to the menu