srm 482 div2 easy AverageAverage

program topcoder
  • ビット演算の練習
    • ビット演算は優先順位がとても低いらしい。
    • if(combi & (1 << i)) で i 番目のビットが立っているかどうかが分かる。
    • 今回、関数名が思い出せなくて使わなかったけど__buildin_popcountという関数があるらしい。
  • 空でない組み合わせの数は n C m - 1 なので、注意。
  • 各数字に対して使うか使わないかで枝が分岐する木を辿って計算することも出来る。
    • この時、深さ優先でも幅優先でも構わないけど、深さ優先だと再帰を使って書ける。
  • 問題の意味をよく考えると、単にnumListの平均を返すだけで良い。
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
class AverageAverage{
public:
  double average(const vector<int>& ls, const int combi){
    int cnt = 0;
    double ret = 0;

    for(int i = 0; i < (int)ls.size(); i++){
      if(combi & (1 << i)){
	ret += ls[i];
	cnt ++;
      }
    }

    return ret / cnt;
  }

  double average(vector <int> numList){
    int combi = 1;
    int last = combi << numList.size();
    double sum = 0; 

    while(combi < last){
      sum += average(numList, combi);
      combi++;
    }

    return sum / (last - 1);
  }


};