Pythonで配列を3つの部分配列に分割する有効な方法の数を求めるプログラム

問題の概要

整数要素からなる配列 nums が与えられます。この配列を3つの部分配列に分割する「良い分割（good split）」の総数を求めましょう。答えは非常に大きな値になる可能性があるため、結果は 10⁹ + 7 で割った余りとして返します。

ここで「良い分割」とは、配列を左から右へ向かって3つの空でない連続した部分配列（左・中央・右）に分け、次の条件を両方とも満たす分割のことです。

• 左側の要素の合計 ≦ 中央の要素の合計
• 中央の要素の合計 ≦ 右側の要素の合計

具体例

たとえば、入力が nums = [2,3,3,3,7,1] の場合、出力は 3 になります。条件を満たす分割方法が次の3通り存在するためです。

• [2], [3], [3,3,7,1]
• [2], [3,3], [3,7,1]
• [2,3], [3,3], [7,1]

解法の考え方：累積和と二ポインタ

この問題は、累積和（プレフィックスサム）と二ポインタのテクニックを組み合わせると効率的に解けます。すべての分割位置を総当たりすると計算量が膨大になりますが、累積和を使えば各区間の合計を即座に求められ、さらにポインタを単調に進めることで中央部分の取り得る範囲を高速に特定できます。

アルゴリズムの手順

• n := nums のサイズ、m := 10⁹+7 とします。
• ss := サイズ (n+1) の配列を作成し、すべて 0 で初期化します。
• nums の各インデックス i と値 val に対して、ss[i] := ss[i-1] + val として累積和を構築します。
• r := 0、rr := 0、ans := 0 で初期化します。
• l を 1 から n-2 までループします。
  • r := max(r, l+1)
  • r < n-1 かつ ss[r] - ss[l] < ss[l] の間、r を 1 ずつ増やします（中央部分の最小境界を探索）。
  • rr := max(rr, r)
  • rr < n-1 かつ ss[n] - ss[rr+1] ≧ ss[rr+1] - ss[l] の間、rr を 1 ずつ増やします（中央部分の最大境界を探索）。
  • ss[l] > ss[r] - ss[l] の場合、ループを抜けます。
  • ss[r] - ss[l] > ss[n] - ss[r] の場合、次の反復へ進みます。
  • ans := (ans + rr - r + 1) mod m
• 最後に ans を返します。

Pythonでの実装例

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

def solve(nums):
   n, m = len(nums), 10**9+7
   ss = [0] * (1+n)
   for i, val in enumerate(nums, 1):
      ss[i] = ss[i-1] + val

   r = rr = ans = 0
   for l in range(1, n-1):
      r = max(r, l+1)
      while r < n-1 and ss[r]-ss[l] < ss[l]:
         r += 1
      rr = max(rr, r)
      while rr < n-1 and ss[n]-ss[rr+1] >= ss[rr+1]-ss[l]:
         rr += 1
      if ss[l] > ss[r]-ss[l]:
         break
      if ss[r]-ss[l] > ss[n]-ss[r]:
         continue
      ans = (ans+rr-r+1) % m
   return ans

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

入力

[1,7,3,6,5]

出力

3

計算量

ポインタ r と rr は後戻りせず単調に進むため、全体の時間計算量は O(n) になります。また、累積和を格納するため O(n) の追加メモリを使用します。このアプローチにより、大規模な入力でも高速に答えを求めることができます。