/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 675 点
問題文
高橋君と青木君はカードゲームをします。ゲームは以下のルールで進行します。
- 高橋君がデッキ A_1, A_2, \dots, A_N を提示する。ここで N \geq 3 である。
- 青木君がデッキ B_1, B_2, B_3 を提示する。
- 高橋君は青木君のデッキのうちいずれか 1 個を選び BAN する。青木君もまた高橋君のデッキのうちいずれか 1 個を選び BAN する。この 2 つの BAN 操作は 同時に 行われる。(つまり、一方が他方の選択を知って行動することはできない。)
- その後、高橋君と青木君は自身が提示したデッキの中から使用するデッキを 同時に 宣言する。ただし BAN されたデッキは宣言できない。
- その後、2 人は宣言したデッキを用いて 1 回だけ戦う。戦いの結果、どちらか一方が勝者となる。
整数 X_{i,j} (1 \leq i \leq N, 1 \leq j \leq 3) が与えられます。p_{i,j} = \dfrac{X_{i,j}}{10^6} とします。p_{i,j} は高橋君がデッキ A_i を、青木君がデッキ B_j を用いて戦った時の高橋君の勝率です。p_{i,j} の値は高橋君も青木君もあらかじめ知っています。
双方が自身の勝率を最大化するように行動した時の高橋君の勝率を求めてください。
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
双方が自身の勝率を最大化するように行動した時の高橋君の勝率とは？
各段階でプレイヤーはその時点までに公開されている情報に基づいて可能な選択肢それぞれに合計が 1 となるように確率を割り当て、その確率に従ってランダムに 1 つ選ぶ戦略を取る。プレイヤーは、「勝率としてありうる最小値」、すなわち「相手が自身の勝率を最小化するような戦略を選んだ時の勝率」を最大化する戦略を選ぶ。条件を満たす戦略の選び方が複数ある場合はどれを選んでも良い。
両者がこの方針に従って行動した時、戦略の選び方によらず高橋君の勝率は一意に定まる。この値を求めよ。
制約
- 1 \leq T \leq 500
- 3 \leq N \leq 5 \times 10^4
- 0 \leq X_{i,j} \leq 10^6
- 全てのテストケースに対する N の総和は 5 \times 10^4 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースでは、入力は以下の形式で与えられる。
N
X_{1,1} X_{1,2} X_{1,3}
X_{2,1} X_{2,2} X_{2,3}
\vdots
X_{N,1} X_{N,2} X_{N,3}
出力
T 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。
各テストケースでは双方が自身の勝率を最大化するように行動した時の高橋君の勝率を出力せよ。出力された答えは、真の値との絶対誤差または相対誤差が 10^{-6} 以下である時に正答とみなされる。
入力例 1
1 3 600000 500000 100000 400000 700000 300000 800000 200000 900000
出力例 1
0.5272727272727272
双方が自身の勝率を最大化するように行動した時の高橋君の勝率は 0.5272727 \cdots です。
入力例 2
3 6 402522 269943 705465 529104 292257 262398 598965 708517 393767 10680 760196 459175 163269 555933 100458 252724 762224 143581 4 720086 398924 165990 446155 678065 592893 674921 176800 484411 222632 81476 633357 5 212176 543920 484352 23874 760886 95861 291354 504948 790821 523486 327166 289413 621589 178581 628701
出力例 2
0.5136657634439492 0.5120053615937050 0.5396248345565982
入力例 3
6 3 600000 300000 100000 0 400000 600000 700000 400000 100000 3 700000 700000 200000 0 0 900000 500000 600000 900000 5 1000000 658525 1000000 867635 1000000 259903 727305 342912 1000000 995128 432824 1000000 69492 105991 1000000 6 900000 700000 300000 600000 300000 500000 900000 100000 900000 900000 1000000 0 800000 200000 900000 700000 800000 900000 7 300000 900000 800000 600000 1000000 700000 700000 200000 1000000 1000000 200000 200000 200000 400000 1000000 500000 800000 900000 900000 500000 800000 5 500000 500000 41274 270488 520436 605863 247128 522516 149943 502751 491747 516407 503752 488744 31814
出力例 3
0.3520000000000000 0.5571428571428572 0.9951279999999999 0.8478260869565216 0.8336956521739129 0.4988562153245037
Score : 675 points
Problem Statement
Takahashi and Aoki play a card game. The game proceeds according to the following rules.
- Takahashi presents decks A_1, A_2, \dots, A_N. Here N \geq 3.
- Aoki presents decks B_1, B_2, B_3.
- Takahashi chooses one deck from Aoki's decks and bans it. Aoki also chooses one deck from Takahashi's decks and bans it. These two ban operations are performed simultaneously. (That is, neither player can act based on the other's choice.)
- Then, Takahashi and Aoki each simultaneously declare which deck from their own presented decks they will use. However, the banned deck cannot be declared.
- Then, the two players battle exactly once using their declared decks. As a result, one of them wins.
You are given integers X_{i,j} (1 \leq i \leq N, 1 \leq j \leq 3). Let p_{i,j} = \dfrac{X_{i,j}}{10^6}. p_{i,j} is Takahashi's win rate when Takahashi uses deck A_i and Aoki uses deck B_j. Both Takahashi and Aoki know the values of p_{i,j} in advance.
Find Takahashi's win rate when both players act to maximize their own win rate.
T test cases are given; solve each of them.
What is Takahashi's win rate when both players act to maximize their own win rate?
At each stage, each player assigns probabilities summing to 1 to the available choices based on the information revealed up to that point, and randomly selects one choice according to those probabilities.Each player chooses a strategy that maximizes "the minimum possible win rate," that is, "the win rate when the opponent chooses a strategy that minimizes the player's win rate." If there are multiple strategies satisfying this condition, any of them may be chosen.
When both players act according to this policy, Takahashi's win rate is uniquely determined regardless of the specific strategy chosen. Find this value.
Constraints
- 1 \leq T \leq 500
- 3 \leq N \leq 5 \times 10^4
- 0 \leq X_{i,j} \leq 10^6
- The sum of N over all test cases is at most 5 \times 10^4.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
For each test case, the input is given in the following format.
N
X_{1,1} X_{1,2} X_{1,3}
X_{2,1} X_{2,2} X_{2,3}
\vdots
X_{N,1} X_{N,2} X_{N,3}
Output
Output T lines. The i-th line should contain the answer to the i-th test case.
For each test case, output Takahashi's win rate when both players act to maximize their own win rate. The output is considered correct if the absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
1 3 600000 500000 100000 400000 700000 300000 800000 200000 900000
Sample Output 1
0.5272727272727272
Takahashi's win rate when both players act to maximize their own win rate is 0.5272727 \cdots.
Sample Input 2
3 6 402522 269943 705465 529104 292257 262398 598965 708517 393767 10680 760196 459175 163269 555933 100458 252724 762224 143581 4 720086 398924 165990 446155 678065 592893 674921 176800 484411 222632 81476 633357 5 212176 543920 484352 23874 760886 95861 291354 504948 790821 523486 327166 289413 621589 178581 628701
Sample Output 2
0.5136657634439492 0.5120053615937050 0.5396248345565982
Sample Input 3
6 3 600000 300000 100000 0 400000 600000 700000 400000 100000 3 700000 700000 200000 0 0 900000 500000 600000 900000 5 1000000 658525 1000000 867635 1000000 259903 727305 342912 1000000 995128 432824 1000000 69492 105991 1000000 6 900000 700000 300000 600000 300000 500000 900000 100000 900000 900000 1000000 0 800000 200000 900000 700000 800000 900000 7 300000 900000 800000 600000 1000000 700000 700000 200000 1000000 1000000 200000 200000 200000 400000 1000000 500000 800000 900000 900000 500000 800000 5 500000 500000 41274 270488 520436 605863 247128 522516 149943 502751 491747 516407 503752 488744 31814
Sample Output 3
0.3520000000000000 0.5571428571428572 0.9951279999999999 0.8478260869565216 0.8336956521739129 0.4988562153245037