第６回日本情報オリンピック 本選 「最大の和」

部分点解法についてのソースも乗のっけていこうと思いましたが、AOJで部分点採点してくれないことに気が付いたのでやめます。すいません。

• 部分点解法

a[i]からa[i+k-1]までの和をfor文で求め、これを0<=i<=Nの範囲で行う。
オーダーはO(NK).
参考までに↓

int max = 0
for(int i = 0;i <= N-k+1){
  int tmp = 0;
  for(int j = 0;j < k;j++){
    tmp += a[i+j];
  }
  ans = max(ans,tmp);
}

しかしこれでは計算量が多すぎて全体の60%の得点しか得られない。

• 満点解法

1. a[0]からa[k-1]の合計を求め、次にその合計からa[0]を引き、a[k]を足す。これをすべての範囲で繰り返してその中の最大の数が答え。O(N)
2. BIT(binary indexed tree)を用いる。ちょいと難しいし、おすすめしない。O(N log N)（たぶん）気が向いたらやってソース載せます。
3. 累積和を使う。int型でなんとかおさまる（はず）。O(N).

単純に解法1が一番よさそうなので解法1のソースを載せます。

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
  
  int n,k,sum = 0,ans = 0,a[100002];
  
  scanf("%d%d",&n,&k);
  
  
  for(int i = 0;i < n;i++){
    scanf("%d",&a[i]);
    if(i < k){
      sum += a[i];
    }
  }
  
  ans = sum;
  
  for(int i = k;i < n;i++){
    sum -= a[i-k];
    sum += a[i];
    ans = max(ans,sum);
  }
  
  printf("%d\n",ans);
  
  return 0;
}

やっぱり累積和もやりたかったからやった。

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){

  
  int n,k,ans = 0,a[100002]={0};
  
  scanf("%d%d",&n,&k);

  for(int i = 1;i <= n;i++){
    int tmp;
    scanf("%d",&tmp);
    a[i] = a[i-1] + tmp;
  }

 for(int i = k;i <= n;i++){
   ans = max(ans,a[i]-a[i-k]);
 }
 
  printf("%d\n",ans);

  
  return 0;
}