Pythonでリストを左右から順に圧縮し、1つの要素になるまで変形するプログラム

数値のリスト nums が与えられたとき、リストの左端と右端から交互に隣接する要素同士を足し合わせて圧縮（スクイーズ）し、要素が1つだけ残るまでこの操作を繰り返します。そして、各ステップにおけるリストの状態をすべて返すのが目的です。

たとえば、入力が nums = [10, 20, 30, 40, 50, 60] の場合、出力は次のようになります。

[ [10, 20, 30, 40, 50, 60],
  [30, 30, 40, 110],
  [60, 150],
  [210]
]

解決のための手順

この問題は、次のアルゴリズムで解くことができます。

• 初期状態として nums 自身を格納したリスト ret を作成する
• nums の長さが 1 より大きい間、以下の処理を繰り返す
  • 長さが 2 の場合：nums[0] + nums[1] のみを要素とする新しいリストを作る
• 長さが 3 の場合：nums[0] + nums[1] + nums[2] のみを要素とする新しいリストを作る
• それ以外の場合：「先頭2要素の和」＋「中央の要素群（インデックス2 から後ろから3番目まで）」＋「末尾2要素の和」をこの順に連結した新しいリストを作る
• 更新後の nums を ret の末尾に追加する

処理の流れを詳しく見る

入力 [10, 20, 30, 40, 50, 60] を例に、各ステップの変化を確認してみましょう。

• ステップ1：先頭2つ（10＋20＝30）と末尾2つ（50＋60＝110）を足し、中央の [30, 40] をそのまま残す → [30, 30, 40, 110]
• ステップ2：先頭2つ（30＋30＝60）と末尾2つ（40＋110＝150）を足す。中央に要素はない → [60, 150]
• ステップ3：残った2つを足す（60＋150＝210）→ [210]

これで要素が1つになったため、処理は終了です。

実装例

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

サンプルコード

class Solution:
   def solve(self, nums):
      ret = [nums]
      while len(nums) > 1:
         if len(nums) == 2:
            nums = [nums[0] + nums[1]]
         elif len(nums) == 3:
            nums = [nums[0] + nums[1] + nums[2]]
         else:
            nums = [nums[0] + nums[1]] + nums[2:-2] + [nums[-2] + nums[-1]]
         ret.append(nums)
      return ret

ob = Solution()
print(ob.solve([10, 20, 30, 40, 50, 60]))

入力

[10, 20, 30, 40, 50, 60]

出力

[[10, 20, 30, 40, 50, 60], [30, 30, 40, 110], [60, 150], [210]]

ポイントのまとめ

このアルゴリズムの核となるのは、スライス表記 nums[2:-2] を使って「両端を除いた中央部分」を取り出す点です。これにより、先頭と末尾から対称的に要素を統合しながら、リスト全体を段階的に縮小していくことができます。要素数が 2 または 3 になったタイミングで特別な処理に分岐することで、最終的に必ず1つの要素に収束させられる仕組みになっています。