Pythonで総和がkで割り切れる連続部分列の個数を求めるプログラム

問題の概要

配列 nums と整数 k が与えられたとき、「要素の総和が k で割り切れる」連続した部分列(サブ配列)の個数を求める問題です。

例として、k = 3、nums = [1, 2, 3, 4, 1] という入力を考えてみましょう。この場合、条件を満たす部分列は [3]、[1, 2]、[1, 2, 3]、[2, 3, 4] の 4 つであるため、出力は 4 となります。

アルゴリズムの考え方

この問題は「累積和」と「剰余(モジュロ)」を組み合わせることで効率的に解けます。ポイントは次の通りです。

• 先頭から順に累積和を計算し、その値を k で割った余りを記録していきます。
• 異なる位置で同じ余りの累積和が現れた場合、その間にある部分列の総和は必ず k の倍数になります。
• したがって、各余りがこれまで何回出現したかを数えておき、同じ余りが出るたびに「それまでの出現回数」を答えに加算すればよいことになります。
• x[0] を最初に 1 にしておくのは、「先頭から始まる部分列」も正しくカウントできるようにするためです(空の接頭辞を考慮しています)。

解法の手順

• 長さ k の配列 x を用意し、すべての要素を 0 で初期化します
• x[0] := 1 と設定します
• カウンタ r と累積和 s を 0 で初期化します
• nums の各要素 elem に対して、以下を繰り返します
  • s := (s + elem) mod k で s を更新します
  • r := r + x[s] で答えに加算します
  • x[s] := x[s] + 1 で出現回数を記録します
• 最終的な r を返します

実装例(Python)

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

def solve(k, nums):
   x = [0]*k
   x[0] = 1
   r=s=0
   for elem in nums:
      s = (s+elem) % k
      r += x[s]
      x[s] += 1
   return r

k = 3
nums = [1,2,3,4,1]
print(solve(k, nums))

入力

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

出力

4

計算量

配列 nums を一度だけ走査するため、時間計算量は O(n) です。また、余りごとの出現回数を格納する配列が必要なため、空間計算量は O(k) となります。すべての部分列を素朴に調べる O(n²) の方法に比べて大幅に高速に動作します。