UVa435 Block Voting

問題
http://uva.onlinejudge.org/external/4/435.html

概要
党が連立したとき全体で過半数の投票数を獲得すると、その連合した党は選挙に勝つことが出来る。ここで各党に対して投票数でない新たな強さの指標 power index を考える。power index とは、あとひとつ多くの党と連合したら過半数の人数を超えるという場合の数を指す。各党について power index を求めよ。

解法
2^20 のビット全探索をして数え上げる。dfs で実装するのはきつい。
連合している党の集合に対して、その人数の合計を持つ配列を持つ。
その中から、連合している党は過半数未満だが、あとひとつ党を加えると過半数を超えるという集合を炙りだして全ての場合の数を求める。

出力の形式の指定に「（各テストケースごとに）P行の出力に続いて改行を出力せよ」と書かれている。テストケースの間ではないことに注意。（これを間違えると Presentation Error でなく Wrong Answer となる）

反省
本番は dfs で実装しようとして詰んでしまっていた。
また、巡回セールスマンの場合は、時間計算量が O(2^n * n^2)のため 2^16 程度までしかビットの配列の要素を持つことはしないが、ビット全探索の場合はそれ以上の要素を配列に持つことができる事実が抜けていた。

int main() {
  
  int Tc;
  cin >> Tc;
  
  while(Tc--) {
    
    int N; cin >> N;
    
    VI vec(N);
    int sum = 0;
    
    for(int i=0; i<N; i++) {
      cin >> vec[i];
      sum += vec[i];
    }
    
    VI combi(1<<N);
    for(int S=0; S<(1<<N); S++) {
      for(int i=0; i<N; i++) {
	if( (S>>i) & 1 ) combi[S] += vec[i];
      }
    }
    
    VI ans(N);
    
    for(int S=0; S<(1<<N); S++) {
      for(int i=0; i<N; i++) {
	if( !( (S >> i) & 1)
	    && combi[S] <= sum/2 && sum/2 < combi[S]+vec[i]
	    ) {
	  ans[i] ++;
	}
      }
    }
    
    for(int i=0; i<N; i++) {
      cout << "party " << i+1 << " has power index " << ans[i] << endl;
    }
    
    cout << endl;
  }
  
  return 0;
}