読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

ABC037_C

C++ ABC

二重ループ中の計算

#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++);

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

より速い解
予めその数までの和を計算しておき,  S_{i} から S_{i+k}までの和はS_{i+k}-S_{i}という式を利用する.
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](透明と黄の間)

f:id:umashika5555:20170310021804p:plain