Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-19

SRM382 div2 (過去問)

01:01

Easy - ContiguousSubsequences

与えられた数列aのサブセットのうち, 要素の値の平均が最大のものをさがす. ただしサブセットの要素数は最小Kとする.

ふつうに全パターンを調べます. タイの場合の優先度とループの境界に注意します.

class ContiguousSubsequences {
public:
  vector <int> findMaxAverage(vector <int> a, int K) {
    vector <int> ret(2, 0);
    double maxi = 0;

    for (int i=K; i<=a.size(); i++) {
      for (int j=a.size()-i; j>=0; j--) {
        double sum = 0;
        for (int k=j; k<j+i; k++)
          sum += a[k];
        sum /= (double)i;
        if (maxi <= sum) {
          maxi = sum;
          ret[0] = j;
          ret[1] = j+i-1;
        }
      }
    }

    return ret;
  }
};