Pythonでリストの最大パワーを求める：要素を1つ移動して最大化するアルゴリズム

問題の定義

リストの「パワー」とは、すべてのインデックス i における (i + 1) × list[i] の総和として定義される値です。数式で表すと次のようになります。

$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[i]$$

ここで、N 個の正の整数からなるリスト nums が与えられます。私たちが行える操作は、リスト内の任意の 1 つの要素を選び、それを別の任意の位置へ移動（入れ替えではなく移動）することだけです。リストの先頭や末尾への移動も許されており、そもそも何も移動しないという選択も可能です。このとき、実現できるリストのパワーの最大値を求め、その結果を 10^9 + 7 で割った余りとして返してください。

たとえば、入力が nums = [4, 2, 1] の場合、出力は 16 になります。その理由は以下の通りです。

• 初期状態のパワー：1×4 + 2×2 + 3×1 = 11
• 4 を末尾へ移動して [2, 1, 4] とすると、パワーは 1×2 + 2×1 + 3×4 = 16 となり、これが最大値になります。

解法のアプローチ

この問題を効率的に解くための鍵となるのは、Convex Hull Trick（凸包テクニック）と呼ばれる手法です。ある要素を位置 j に移動したときのパワーの変化量は、j に関する一次関数として表現できます。そこで、直線群の凸包を事前に構築しておき、各要素ごとに二分探索で最適な挿入位置を求めることで、全体を O(N log N) の計算量で処理できます。

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

• P := [0]、base := 0 として初期化します。

• A の各要素 x とその 1 始まりのインデックス i について、次の処理を行います。

  • P の末尾に P[-1] + x を追加します（累積和の構築）。

  • base := base + i * x と更新します（初期パワーの計算）。

• 関数 eval_at() を定義します。引数は j と x で、-j * x + P[j] を返します。

• 関数 intersection() を定義します。引数は j1 と j2 で、(P[j2] - P[j1]) / (j2 - j1) を返します。

• hull := [-1]、indexes := [0] として初期化します。

• j を 1 から P のサイズ未満までループさせます。

  • hull が空でなく、intersection(indexes[-1], j) <= hull[-1] である間、hull と indexes の末尾要素を削除します。

  • hull の末尾に intersection(indexes[-1], j) を追加し、indexes の末尾に j を追加します。

• ans := base として初期化します。

• A の各要素 x とそのインデックス i について、次の処理を行います。

  • ソート順を保ったまま x を hull に挿入できる位置 j を二分探索で求めます。

  • j := max(j - 1, 0) とします。

  • ans := max(ans, base + eval_at(i, x) - eval_at(indexes[j], x)) として答えを更新します。

• ans mod (10^9 + 7) を返します。

実装例

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

import bisect
class Solution:
    def solve(self, A):
        P = [0]
        base = 0
        for i, x in enumerate(A, 1):
            P.append(P[-1] + x)
            base += i * x
        def eval_at(j, x):
            return -j * x + P[j]
        def intersection(j1, j2):
            return (P[j2] - P[j1]) / (j2 - j1)
        hull = [-1]
        indexes = [0]
        for j in range(1, len(P)):
            while hull and intersection(indexes[-1], j) <= hull[-1]:
                hull.pop()
                indexes.pop()
            hull.append(intersection(indexes[-1], j))
            indexes.append(j)
        ans = base
        for i, x in enumerate(A):
            j = bisect.bisect(hull, x)
            j = max(j - 1, 0)
            ans = max(ans, base + eval_at(i, x) - eval_at(indexes[j], x))
        return ans % (10 ** 9 + 7)

ob = Solution()
print(ob.solve([4, 2, 1]))

入力

[4, 2, 1]

出力

16

まとめ

本記事では、リストのパワーを最大化する問題を Convex Hull Trick を用いて O(N log N) で解く方法を紹介しました。単純な全探索では各要素の移動先をすべて試す必要があり O(N²) の計算量がかかりますが、一次関数の凸包と二分探索を組み合わせることで大幅な高速化が可能です。競技プログラミングで頻出のテクニックなので、ぜひマスターしておきましょう。