AtCoder が提供しているABC（AtCoder Beginner Contest）280 のB問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Inverse Prefix Sum（Difficulty : 22）
問題はリンク先をご覧ください。
累積和から元の数列を求める問題です。AtCoder Problems による Difficulty は、22 でした。
解答案
問題を解く方針を書きだします。
- N と 累積和を表す数列を読み込む。
- 累積和の数列から元の数列を出力する。
累積和の定義も記しておきます。
$n$ 個の数列 $A_i \; (i = 0, 1, 2, …, n – 1)$ に対して、以下の数列 $S_i \; (i = 0, 1, 2, …, n)$ を $A$ の累積和と呼びます。
- $s[0] = 0$
- $s[i] = \sum_{j = 0}^{i – 1} A_j (i = 1, 2, 3, …, n)$
ある数列 $A$ の数列の最初の $n$ 個の和が累積和となります。累積和を使うと、数列の特定の範囲の和を速く求めることができます。今回の問題に関しては、以下が成立しています。
$$A_i = S_{i + 1} – S_i \; (i = 0, 1, 2, …, n – 1)$$
C++ プログラム例（ABC280B）
上で記述した累積和の定義に従い計算します。問題文は、数列 A の添え字を 1 から記述しています。プログラムでは、上の定義に従い数列 A の添え字を0から考えています。
以下が、C++の実装例です。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<ll> s(n + 1);
s[0] = 0;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
for (int i = 0; i < n; ++i) {
cout << s[i + 1] - s[i] << " \n"[i == n - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC280B）
Python の場合は、数列 S を読み込むときに、添え字が 0 から格納されます。そのため $A[0]$ を $S[0]$ として出力して、残りの $A$ も、$S[i] – S[i – 1]$ として出力しました。
"""AtCoder Beginner Contest 280 B"""
n = int(input())
s = list(map(int, input().split()))
print(s[0], end="")
for i in range(1, n):
print(f" {s[i] - s[i - 1]}", end="")
print("")添え字の使い方は、一貫して使わないと気持ち悪いです。冒頭で述べた累積和の説明と添え字が合うように $S[0]$ に $0$ を insert します。これにより、C++ 版と添え字の考えた方が一致しました。
"""AtCoder Beginner Contest 280 B"""
n = int(input())
s = list(map(int, input().split()))
s.insert(0, 0)
for i in range(n):
print(s[i + 1] - s[i], end=" " if i != n - 1 else "\n")
print("")どちらも「AC」と判定されました。
最後に
累積和を使う問題は、添え字の1個違いミスをすることがあります。累積和を書くルールを自分なりに定めて、一貫して使うことがよいと考えています。
引き続き ABC の問題を紹介していきます。
