概要

音楽プレイリストを部分列として選び、連続する曲の相性値の積と全曲の単体スコアの合計で総合スコアを計算します。総合スコアの最大値を求める問題です。

考察

この問題は、DP（動的計画法）を用いて解くことを考えます。

最後に選んだ曲が曲 \(i\) であるときの、その時点での最大スコアを dp[i] とします。 曲 \(i\) を選ぶ直前に選んだ曲を曲 \(j\) （\(j < i\)）とすると、曲 \(j\) から曲 \(i\) への遷移スコアは \(A_i + B_j \times B_i\) となります。したがって、dp[i] は以下の式で計算できます。

\[ \text{dp}[i] = A_i + \max(0, \max_{j < i} (\text{dp}[j] + B_j \times B_i)) \]

ここで、max(0, ...) は曲 \(i\) をプレイリストの1曲目として選ぶ場合（前の曲が存在しない場合）を表しています。

このDPの遷移式を素朴に計算すると、各 \(i\) に対して過去のすべての \(j\) を走査する必要があり、時間計算量が \(O(N^2)\) となり、\(N \leq 10^5\) の制約ではTLE（時間切れ）になります。

そこで、式を変形して注目します。\(\max_{j < i} (\text{dp}[j] + B_j \times B_i)\) の部分を見ると、これは \(y = B_j \times x + \text{dp}[j]\) という直線に対して、\(x = B_i\) を代入したときの最大値を求める問題と同一であることがわかります。

すなわち、「直線の追加」と「ある \(x\) における最大値クエリ」を高速に処理できれば、このDPを高速化できます。\(x\) の範囲は \(B_i\) の制約より \(-10^6 \leq x \leq 10^6\) です。

アルゴリズム

この問題では Li Chao Tree（李超木） というデータ構造を使用します。Li Chao Tree は、直線の追加と最小値（または最大値）クエリをそれぞれ \(O(\log V)\) （\(V\) は座標の範囲）で行えるデータ構造です。

アルゴリズムの手順は以下の通りです： 1. \(x\) の範囲を \(-10^6\) から \(10^6\) とした Li Chao Tree を初期化します。 2. 初期状態として、「何も選ばない」状態を表す \(y = 0\) の直線（傾き \(0\)、切片 \(0\)）を追加します。これにより、dp[i] の計算式の \(\max(0, \dots)\) を自然に処理できます。 3. 各曲 \(i\) について、\(x = B_i\) での最大値クエリを発行し、その結果に \(A_i\) を足したものを dp[i] とします。 4. dp[i] が全体の最大値であれば答えを更新します。 5. 次の曲のために、直線 \(y = B_i \times x + \text{dp}[i]\) を Li Chao Tree に追加します。

計算量

• 時間計算量: \(O(N \log V)\) \(N\) 回のクエリと直線追加を行い、1回あたり \(O(\log V)\) （\(V \approx 2 \times 10^6\)）かかります。
• 空間計算量: \(O(V)\) Li Chao Tree はセグメント木と同様の構造を持つため、座標の範囲 \(V\) に比例したノード数を持ちます。この実装では \(4 \times V\) 程度の配列を使用します。

実装のポイント

• \(B_i\) が負の値をとるため、Li Chao Tree の座標空間も負の領域を含むように X_MIN = -10**6 として設定する必要があります。

• 直線の追加やクエリの際に、区間の中点 mid = (l + r) // 2 などを用いて再帰的（または反復的）に木を探索します。本実装ではスタックオーバーフローを防ぐため、反復（ループ）で実装しています。

• C++などと異なりPythonでは再帰が遅いため、反復処理にすることで実行時間を短縮できます。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        a, b = map(int, input().split())
        A[i] = a
        B[i] = b

    INF = 10**18
    X_MIN = -10**6
    X_MAX = 10**6 + 1

    size = X_MAX - X_MIN
    tree_m = [0] * (4 * size)
    tree_b = [-INF] * (4 * size)

    def add_line(m, b):
        l = X_MIN
        r = X_MAX
        node = 1
        while True:
            cur_m = tree_m[node]
            cur_b = tree_b[node]
            mid = (l + r) // 2
            
            if m * mid + b > cur_m * mid + cur_b:
                tree_m[node], m = m, cur_m
                tree_b[node], b = b, cur_b
                
            if r - l == 1:
                break
                
            if m * l + b > tree_m[node] * l + tree_b[node]:
                node = node * 2
                r = mid
            elif m * (r - 1) + b > tree_m[node] * (r - 1) + tree_b[node]:
                node = node * 2 + 1
                l = mid
            else:
                break

    def query(x):
        l = X_MIN
        r = X_MAX
        node = 1
        res = -INF
        while True:
            val = tree_m[node] * x + tree_b[node]
            if val > res:
                res = val
            if r - l == 1:
                break
            mid = (l + r) // 2
            if x < mid:
                node = node * 2
                r = mid
            else:
                node = node * 2 + 1
                l = mid
        return res

    # 初期状態として y = 0 (m=0, b=0) の直線を追加
    add_line(0, 0)

    ans = -INF
    for i in range(N):
        q = query(B[i])
        dp = A[i] + q
        if dp > ans:
            ans = dp
        add_line(B[i], dp)

    print(ans)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。