TopCoder SRM 724 Div2 Hard UnfinishedTournamentEasy

意外とコード短いのよね。
https://community.topcoder.com/stat?c=problem_statement&pm=14747

問題

N人で総当たりの対戦ゲーを行うことを考える。
一部の試合は完了済みですでに結果が出ている。

未完の試合について勝者を任意に選べる場合、勝率の分散の最大値はいくつか。

解法

問題文の分散の式が地味にいやらしい。
分散は(二乗和の平均)-(平均の2乗)と書け、勝率の平均は明らかに0.5なので、あとは勝利回数の二乗和を最大化する問題となる。

分散を大きくするには、一部の人に勝ち負けを偏らせた方がいい。
よって順番を決めその順で勝ちを偏らせることを考えよう。
N!通り試すのはTLEで実現できないが、BitDPで行えばO(N^2*2^N)で処理できる。

int dp[1<<20];

class UnfinishedTournamentEasy {
	public:
	double maximal(vector <string> G) {
		int N=G.size();
		ZERO(dp);
		for(int mask=0;mask<1<<N;mask++) {
			int x,y;
			FOR(x,N) if((mask&(1<<x))==0) {
				int win=0;
				FOR(y,N) if(G[x][y]=='W' || (G[x][y]=='?'&&((mask&(1<<y))==0))) {
					win++;
				}
				dp[mask|(1<<x)]=max(dp[mask|(1<<x)],dp[mask]+win*win);
			}
		}
		return dp[(1<<N)-1]*1.0/(N*(N-1)*(N-1))-0.25;
	}
}

まとめ

問題設定はシンプルでいいね。