C++で解く「算術スライス」問題 ― 動的計画法による効率的な実装

問題の概要

少なくとも3つの要素から構成され、隣り合う任意の2要素間の差がすべて等しい数列を等差数列と呼びます。例えば、次のような数列は等差数列です。

• [1, 3, 5, 7, 9]（公差 2）
• [7, 7, 7, 7]（公差 0）
• [3, -1, -5, -9]（公差 -4）

一方、[1, 1, 2, 5, 7] は隣接要素間の差が一定ではないため、等差数列ではありません。

ここで、N 個の整数からなる 0 インデックスの配列 A が与えられます。この配列のスライスとは、0 ≤ P < Q < N を満たす整数のペア (P, Q) のことです。スライス (P, Q) が算術スライスであるとは、数列 A[P], A[P+1], ..., A[Q-1], A[Q] が等差数列になっていることを意味します。

本問題では、配列 A に含まれる算術スライスの総数を求める関数を実装します。

入出力の例

入力が [1, 2, 3, 4] の場合、答えは 3 になります。これは、以下の3つの算術スライスが存在するためです。

• [1, 2, 3]
• [2, 3, 4]
• [1, 2, 3, 4]

解法のアプローチ：動的計画法

この問題は、動的計画法（DP）を用いることで線形時間で効率的に解くことができます。ポイントは、「位置 i を終点とする算術スライスの個数」を dp[i] として記録することです。dp[i] には、A[i-2], A[i-1], A[i] が等差関係にあるときにのみ値が設定されます。

アルゴリズムの手順

• ret := 0、n := 配列 A のサイズとし、サイズ n の DP 配列 dp を用意する
• i = 2 から n - 1 まで繰り返す
  • A[i] - A[i-1] == A[i-1] - A[i-2] の場合（連続する3要素が等差関係にある場合）
    • dp[i] := 1 + dp[i-1] とする
    • ret に dp[i] を加算する
• 最後に ret を返す

この漸化式が正しい理由は、位置 i を終点とする算術スライスが、「位置 i-1 を終点とする算術スライスを1要素延長したもの」と「A[i-2], A[i-1], A[i] のみからなる長さ3の新しいもの」の2種類しか存在しないためです。したがって dp[i] = dp[i-1] + 1 が常に成立します。

C++による実装例

理解を深めるために、実際の C++ コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numberOfArithmeticSlices(vector<int>& A) {
      int ret = 0;
      int n = A.size();
      vector<int> dp(n);
      for(int i = 2; i < n; i++){
         if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
            dp[i] = 1 + dp[i - 1];
            ret += dp[i];
         }
      }
      return ret;
   }
};
main(){
   vector<int> v = {1,2,3,4};
   Solution ob;
   cout << (ob.numberOfArithmeticSlices(v));
}

実行結果

入力：

[1,2,3,4]

出力：

3

計算量の評価

• 時間計算量： O(n) — 配列を一度走査するだけで済みます
• 空間計算量： O(n) — DP 配列を使用します。ただし、直前の dp 値のみを参照するため、変数1つに置き換えれば O(1) に削減することも可能です