SRM577

Easy ("EllysRoomAssignments", 250)

最初、トップから20人ずつ取ってて数あわないなあとか思ってた
→case 4で{11人,10人}に分かれるのを見て間違いに気づいた。
サンプルケースが親切なので、言われたとおりにやるだけの問題。
間違えそうなので

• 参加人数が部屋数で割り切れる場合・割り切れない場合
• Ellyが最後の余りに入る場合・入らない場合

で分けて考えた。

妙に時間がかかってしまった。
縦横を混同して間違えそうになる。自分でわかりやすい名前をつける等しないと。

62分かけて書いたがWA。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

string concat(vector<string>& strs) {
  stringstream ss;
  tr(it, strs) ss << *it;
  return ss.str();
}

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '¥0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

class EllysRoomAssignmentsDiv1 {
 public:
  double getAverage(vector<string> ratings_) {
    vector<int> ratings = map_atoi(split(concat(ratings_)));
    int elly_rating = ratings[0];
    sort(all(ratings), greater<int>());
    // cout << ratings << endl;
    tr(it,ratings){
      assert(1200 <= *it && *it <= 3923);
    }

    int N = sz(ratings);

    if (N < 20) {
      int sum = 0;
      tr(it, ratings) sum += *it;
      return (double)sum / N;
    }

    int R = N / 20; if (N % 20) ++R;
    int G = (N + (R-1)) / R;
    // printf("N=%d, R=%d, G=%d¥n", N, R, G);
    int rem = N % R;

    vector<int>::iterator at = find(all(ratings), elly_rating);
    int elly_rank = (int)(at - ratings.begin()), elly_g = elly_rank/R;
    // printf("Elly: rating=%d, rank=%d, group#=%d¥n", elly_rating, elly_rank, elly_g);

    vector<int> r_sum(G, 0); // R人組のグループ毎合計
    rep(i, N) {
      r_sum[i/R] += ratings[i];
    }
    // cout << "r_sum:" << r_sum << endl;

    if (rem == 0) {
      double sum = 0;
      rep(g, G){
        if (g == elly_g) {
          sum += (double)elly_rating;
        } else {
          sum += (double)r_sum[g]/R;
        }
      }
      return sum / G;
    } else {
      double sum = 0;
      if (elly_g == G-1) {
        rep(g, G-1){
          sum += (double)r_sum[g]/R;
        }
        sum += (double)elly_rating;
        return sum / G;
      } else {
        rep(g, G-1) {
          if (g == elly_g) {
            sum += (double)elly_rating;
          } else {
            sum += (double)r_sum[g]/R;
          }
        }

        double a1 = (sum + r_sum[G-1]/rem)/G;
        double a2 = sum / (G-1);
        return (a1*rem + a2*(R-rem))/R;
      }
    }
  }
};

System Testで落ちたケースを見るといずれも僅差なので精度が悪いのかなと
r_sum を vector<int> から vector<double> にしたら通った。

あ。分かった。最後の

  double a1 = (sum + r_sum[G-1]/rem)/G;

のr_sumに(double)キャストするの忘れてる。

教訓

中の値がintだからって律儀にvector<int>で書かなくてもいい。キャストして割り算して使うなら最初からdoubleで。