SRM 690 div2 medium GerrymanderEasy

問題

問題概要

AとBが与えられる。そのなかから、連続するK以上の部分のAの合計と、Bの合計をそれぞれ出して、(Bの合計)/(Aの合計) の最大値を求める。

解法

全探索で通る。単純にすべての区間について、(Bの合計)/(Aの合計)を出していけばいい。これだとn=1000でO(n³)になって通らない気がしたが、通った。よくわからない。
O(n²)に落とすことができる。すべての区間を求めていくときに、左の位置を決めて右に伸ばしていく。だから、毎回左の位置から右の位置までなまて合計を出さなくても、右に区間を伸ばしたときは、前に出した区間の合計に区間を伸ばしたところ値を足すだけで、次の区間の合計を求めることができる。

ミス

問題文を読み間違えていて、混乱した。連続した部分ではなく、どこでもよいから、K箇所以上選べばよいと思い、蟻本p132にある平均最大化を行うのかと思い、それを書いてしまったが、サンプル1でおかしくなって気づいた。
consecutive numbersは連続した数字。

コード

区間を伸ばすときに、最右辺のみを足したもの(AC)

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

class GerrymanderEasy{
public:
    double getmax(vector <int> A, vector <int> B, int K){
        double ans = 0.0;
        //連続しk以上の部分での最大値
        for (int i = 0; i < A.size(); ++i){
            ll sumA = 0, sumB = 0;
            for (int j = i; j < A.size(); ++j){
                sumA += A[j];
                sumB += B[j];
                if(j - i + 1 < K) continue;//k以上
                ans = max(ans, (double)sumB / (double)sumA);
            }
        }
        return ans;
    }
};

ただ、全探索した計算量がとても危ない気がするコード(AC)

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

class GerrymanderEasy{
public:
    double getmax(vector <int> A, vector <int> B, int K){
        double ans = 0.0;
        //連続しk以上の部分での最大値
        for (int i = 0; i < A.size(); ++i){
            ll sumA = 0, sumB = 0;
            for (int j = i; j < A.size(); ++j){
                sumA += A[j];
                sumB += B[j];
                if(j - i + 1 < K) continue;//k以上
                ans = max(ans, (double)sumB / (double)sumA);
            }
        }
        return ans;
    }
};