ABC037 C問題（総和）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）037 C問題をC++で解いてみました。ABC037は、2016年5月7日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 総和（Difficulty : 915（参考値））

問題の詳細は、リンク先をご覧ください。

ABC037 C問題 総和

1次元の累積和を使う典型問題です。AtCoder Problems による Difficulty は 915（参考値）でした。

解答案

前回は2次元の累積和を用いた問題を紹介しました（昨日の記事）。今回は基本となる1次元の累積和を用いた問題を紹介します。

要素数 $N$ の配列 $a_0, a_1, \cdots, a_{n-1}$ に対して、累積和 $s$ を以下のように定義します。

$$s_0 = 0, \; s_{i+1} = s_i + a_i \;\; (i = 0, …, n-1)$$

この定義で求めた累積和 s に対して、$\sum_{L \leqq i < R} a_i = s_R-s_L$ となります。

コードは以下となります。

	int n;
	cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

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

C++ プログラム例（ABC037C）

上記の累積和を用いることで、この問題を解くことができます。累積和を活用する典型的な問題と言えます。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

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

	ll result = 0;
	for (int left = 0; left + k - 1 < n; ++left) {
		int right = left + k;
		result += s[right] - s[left];
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

1次元の累積和のプログラムをテンプレート化してから、1個違いミスをしなくなりました。

引き続き ABC の問題を紹介していきます。