AtCoder

ABC280 B問題(Inverse Prefix Sum)を解く

AtCoder_ABC280_B

AtCoder が提供しているABC(AtCoder Beginner Contest)280 のB問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。

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

B問題 Inverse Prefix Sum(Difficulty : 22)

問題はリンク先をご覧ください。

ABC280 B問題 Inverse Prefix Sum

累積和から元の数列を求める問題です。AtCoder Problems による Difficulty は、22 でした。ABC B問題として、簡単な問題です。

解答案

問題を解く方針を書きだします。

  • 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個違いミスをすることがあります。累積和を書くルールを自分なりに定めて、一貫して使うことがよいと考えています。

    ABC280 について、引き続き、D問題まで紹介します。

    COMMENT

    メールアドレスが公開されることはありません。 が付いている欄は必須項目です

    CAPTCHA