0w1

CFR 442 B. Andrey and Problem ( Math, Probability, Greedy )

Problem - B - Codeforces

題意:
你有一件事情要完成,但你太懶所以想請你朋友做。你可以同時請很多朋友做,但是如果兩個以上個朋友同時做出來,他們會覺得你把他們當工具人,不特別看待他們。求最佳策略下,可以不讓朋友傷心而完成這項作業的機率是多少。

資料規模:
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of Andrey's friends. The second line contains n real numbers pi (0.0 ≤ pi ≤ 1.0) — the probability that the i-th friend can come up with a problem. The probabilities are given with at most 6 digits after decimal point.
精度要求: 相對差距 1e-9

解法:
假設將 P 中的元素交換若干次後最佳策略為前 n 個人組成的集合。那麼此時的機率為:
Sigma{ P[ i ] * Pi{ 1 - P[ j ], for all i != j }, for all 0 ≤ i < n }
= Sigma{ P[ i ] / ( 1 - P[ i ] ), for all 0 ≤ i < n } * Pi{ 1 - P[ i ], for all 0 ≤ i < n }
接著考慮將一個 x > i 的 P[ x ] 新增至集合會產生什麼貢獻:
首先令原先的
S = Sigma{ P[ i ] / ( 1 - P[ i ] ), for all 0 ≤ i < n }
F = Pi{ 1 - P[ i ], for all 0 ≤ i < n }
delta( x ) = ( S + P[ x ] / ( 1 - P[ x ] ) * ( F * ( 1 - P[ x ] ) ) - S * F
= F * P[ x ] * ( 1 - S )
此時猜測由於 S 會不斷增加,直到超過 1 後加什麼都不好了,這世上現存在的理由。而在 S 超越上限之前,加什麼都是正貢獻的,差別在於貢獻的大小。
接著考慮新增 x 元素和 y 元素,x 元素比較優的條件為何:
Assuming delta( x ) - delta( y ) > 0 :
delta( x ) - delta( y ) = F * ( 1 - S ) * ( P[ x ] - P[ y ] ) > 0, which implies P[ x ] > P[ y ]
因此可以考慮,將原先的 P 數列由大到小排序,並枚舉前面連續段為集合的解。可以很快地用反證法知道,如果最佳解是非連續的,那麼拔掉比較弱的那個,取比較強的一定比較好。
最後要記得,如果原先有 P[ i ] = 1,要立刻回答 1 並退出,否則在這公式中會有 division by 0。

時間 / 空間複雜度:
O( N )

領悟:
將想要最佳化的數與式具體化。猜測貪心策略並反證之。

#include <bits/stdc++.h>
using namespace std;

int N;
double P[ 100 ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> P[ i ];
    if( P[ i ] == 1.0 ){ // otherwise RE later for division with 0
      cout << 1.0 << endl;
      exit( 0 );
    }
  }
  double ans = 0.0;
  sort( P, P + N, greater< double >() );
  for( int i = 0; i < N; ++i ){
    static double sum = 0.0, pi = 1.0;
    sum += P[ i ] / ( 1.0 - P[ i ] );
    pi *= 1.0 - P[ i ];
    ans = max( ans, sum * pi );
  }
  cout << fixed << setprecision( 10 ) << ans << endl;
  return 0;
}