【Python】サブリストの合計操作で2つのリストを一致させるプログラムの実装方法

問題の概要

2つのリスト l1 と l2 が与えられます。次の操作を何度でも繰り返し適用して、両方のリストを完全に一致させることを考えます。

• 操作: 連続する要素からなる部分リスト(サブリスト)を1つ選び、その部分リスト全体を要素の合計値1つで置き換える。

操作を適用した結果として作れるリストのうち、最も長くなるリストのサイズを返してください。どうしても一致させられない場合は -1 を返します。

入力例と動作イメージ

たとえば l1 = [1, 4, 7, 1, 2, 10]、l2 = [5, 6, 1, 3, 10] の場合、答えは 4 になります。以下の手順で操作すると、両方のリストを [5, 7, 3, 10] に一致させられるからです。

• l1 の部分リスト [1, 4] を合計して置き換え → [5, 7, 1, 2, 10]
• l1 の部分リスト [1, 2] を合計して置き換え → [5, 7, 3, 10]
• l2 の部分リスト [6, 1] を合計して置き換え → [5, 7, 3, 10]

これで両方のリストが一致し、長さは 4 となります。

解法のアプローチ:末尾からの貪欲法

この問題は、リストの末尾(右端)から順に比較していく貪欲法で効率的に解けます。

ポイントは、「部分リストを合計で置き換える」という操作が、隣接する要素を1つの区間へまとめる操作に相当する点です。つまり、最終的に一致したリストは「元のリストをいくつかの連続区間に分割し、各区間の合計を並べたもの」と捉えられます。なお、操作をしてもリストの総和は変わらないため、両リストの総和が等しくない場合は解が存在しません。

アルゴリズムの手順

1. i := len(l1) - 1、j := len(l2) - 1、res := 0 で初期化する。
2. i >= 0 かつ j >= 0 の間、以下を繰り返す。
   • l1[i] == l2[j] の場合:この要素は最終リストの1要素として確定できるので、res を +1 し、i と j をそれぞれ -1 する。
   • l1[i] < l2[j] の場合:l1 側の末尾が小さいので、直前の要素と結合して大きくする(l1[i-1] += l1[i])。その後 i を -1 する。
   • l1[i] > l2[j] の場合:l2 側に対して同様に l2[j-1] += l2[j] としてから j を -1 する。
3. ループ終了後、i と j がどちらも -1(両方のリストを使い切った)なら res を返す。片方だけ余っている場合は一致できないので -1 を返す。

Pythonでの実装例

class Solution:
   def solve(self, l1, l2):
      i, j, res = len(l1) - 1, len(l2) - 1, 0
      while i >= 0 and j >= 0:
         if l1[i] == l2[j]:
            res, i, j = res + 1, i - 1, j - 1
         elif l1[i] < l2[j]:
            if i > 0:
               l1[i - 1] += l1[i]
            i -= 1
         elif l1[i] > l2[j]:
            if j > 0:
               l2[j - 1] += l2[j]
            j -= 1
      return res if i == -1 and j == -1 else -1

ob = Solution()
l1 = [1, 4, 7, 1, 2, 10]
l2 = [5, 6, 1, 3, 10]
print(ob.solve(l1, l2))

入力

[1, 4, 7, 1, 2, 10], [5, 6, 1, 3, 10]

出力

4

コードのポイント

• 右端から処理する理由: 正の整数を扱う場合、部分リストの合計は元の要素以上の値になるため、末尾側から「末尾要素が小さければ左隣と結合して大きくする」という判断を繰り返せば、各時点の判断が後続のマッチングと矛盾しません。
• 境界チェック: i > 0 や j > 0 の確認により、先頭要素を超えて結合しようとするミスを防いでいます。
• 失敗判定: ループを抜けたときに片方のインデックスだけ残っている場合は、どんな分割をしても一致しないことを意味するため -1 を返します。
• 計算量: 各ステップで i または j が必ず減少するため、時間計算量は O(n + m)。追加メモリは O(1) で済みます(入力リストを書き換えてよい場合)。

まとめ

サブリストを合計値で置き換える操作によって2つのリストを一致させる問題は、末尾から貪欲に比較と結合を繰り返すことで線形時間で解けます。総和が等しいことの確認と、ループ終了時に両方のリストを使い切れたかのチェックが、正しく動作させるための鍵となります。