算術スライス II（サブシーケンス）を C++ で解く方法

問題概要

N 個の数値を含む配列 A があるとします。この配列における部分列スライスとは、0 <= K0 < K1 < K2 < … < Kn < N を満たす整数列 (K0, K1, K2, …, Kn) のことを指します。

A[K0], A[K1], …, A[Kn] が公差一定の等差数列を成すとき（n >= 2）、その部分列スライスは等差スライス（算術スライス）と呼ばれます。本問題では、配列 A に含まれる等差スライスの総数を求めることが課題です。

入出力例

入力が [2,4,6,8,10] の場合、答えは 7 となります。次の 7 つの等差スライスが存在するためです。

• [2,4,6]
• [4,6,8]
• [6,8,10]
• [2,4,6,8]
• [4,6,8,10]
• [2,4,6,8,10]
• [2,6,10]

解法の考え方

この問題は動的計画法（DP）を用いて解きます。dp[i][diff] を「インデックス i で終わり、公差が diff である弱い等差部分列の個数」と定義することで、長さ 3 以上の等差部分列だけを効率よく数え上げることができます。

具体的な手順は以下の通りです。

• ret := 0 と初期化します
• マップ dp と cnt を定義します
• 配列 A の要素から集合 s を作成します
• n := A のサイズとします
• i := 1 から開始し、i < n の間 i を 1 ずつ増やしながら以下を実行します
  • j := i - 1 から開始し、j >= 0 の間 j を 1 ずつ減らしながら以下を実行します
    • diff := A[i] - A[j] を計算します
    • diff が INT_MIN 以下または INT_MAX より大きい場合は、以降の処理をスキップして次の反復へ進みます
    • diff がマップ dp[j] に存在するなら temp := dp[j][diff]、存在しなければ temp := 0 とします
    • ret := ret + temp とします
    • (A[i] + diff) が集合 s に存在する場合、dp[i][diff] := dp[i][diff] + temp + 1 とします
• 最後に ret を返します

C++ による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int numberOfArithmeticSlices(vector<int>& A) {
      int ret = 0;
      unordered_map <lli, unordered_map <lli, lli> > dp, cnt;
      unordered_set <int> s (A.begin(), A.end());
      int n = A.size();
      for(int i = 1; i < n; i++){
         for(int j = i - 1; j >= 0; j--){
            lli diff = (lli)A[i] - (lli)A[j];
            if(diff <= INT_MIN || diff > INT_MAX) continue;
            int temp = dp[j].count(diff) ? dp[j][diff] : 0;
            ret += temp;
            if(s.count(A[i] + diff))dp[i][diff] += temp + 1;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,4,6,8,10};
   cout << (ob.numberOfArithmeticSlices(v));
}

入力

{2,4,6,8,10}

出力

7

計算量

• 時間計算量：O(n²) ― すべてのインデックスのペア (i, j) を一度ずつ調べるためです
• 空間計算量：O(n²) ― インデックスと公差の組み合わせごとに DP 値を保持する必要があるためです