おじさんの競プロ記録

自分の力で解答できた問題を振り返り、理解を深めたいです。

AtCoder Beginner Contest 037 C - 総和

問題

問題文へ

長さNの数列{a_i}と1以上N以下の整数が与えられます。この数列には長さKの連続する部分がN-K+1個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。

制約

  • {1 \leqq K \leqq N \leqq 10^5}
  • {0 \leqq a_i \leqq 10^8}
  • {a_i}は整数である。

考えたこと

すべてのパターンを逐一足し算したのでは間に合わなさそうです。累積和を使うことにしました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll N, K;
  cin >> N >> K;
  vector<ll> a(N);
  rep(i, N) cin >> a[i];

  vector<ll> s(N + 1, 0);
  for (int i = 0; i < N; ++i) s[i + 1] = s[i] + a[i];

  ll ans = 0;
  int left = 0;
  int right = K;
  while (right <= N) {
    ans += s[right] - s[left];
    ++left;
    ++right;
  }

  cout << ans << endl;
  
  return 0;
}

解説を読んで

とくにありません。