ABC003 C AtCoderプログラミング講座

問題

atcoder.jp

コード

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

typedef long long ll;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
/*--------------------------------------------*/

int main(){
  int N,K;
  cin >> N >> K;
  VLL r(N);
  rep(i,N) cin >> r[i];
  
  sort(ALL(r));
  
  double ans = 0;
  
  rep(i,K) ans = (ans + r[N+i-K] ) /2.0;
  
  cout << fixed << setprecision(6) << ans << endl;
}

解法

大きい方から K個を小さい順に用いる。 i回目に用いたものは K回後には \frac{1}{2^{K-i+1}}倍になっている。