ABC037_C

二重ループ中の計算

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,k,a[MAX_N],tmp;
    int *s;
    long long int res = 0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-k+1;i++){
        s = a+i;
        for(int j=0;j<k;j++){
            res += *(s++);// <----
        }
    }
    cout<<res<<endl;
    return 0;
}

←の部分は逆参照子の後にポインタsを一つ進めている.

1. res += *s;
   s++;

2. res += *s++;

3. res += *(s++);

のどれでも通すことができた.

より速い解
予めその数までの和を計算しておき, という式を利用する.
O(N)で解ける.
最後にi = n-k のときにsum[(n-k)+k] -sum[n-k]なので二番目のfor文でi=nすなわちsum[n]も計算しておくことがポイント.

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,k,a[MAX_N],sum[MAX_N];
    long long int res = 0;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    sum[0]=0;
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i-1];
    for(int i=0;i<n-k+1;i++)res+=sum[i+k]-sum[i];
    cout<<res<<endl;
    return 0;
}

下図はn=5,k=3
1,2,4,8,16の場合
最初の3つの和は青の高さまですなわちsum[3](青と緑の間)-sum[0](透明と黄の間)