概要

各楽曲を「直前に再生する曲」として連結していくときの最大スコアを動的計画法で求める問題です。漸化式が「直線の最大値クエリ」の形になるため、Li Chao Tree（凸包トリック） を用いて高速化します。

考察

DP の定義

「最後に選んだ曲が \(i\) であるようなプレイリスト」の総合スコアの最大値を \(dp_i\) とおきます。

• 曲 \(i\) を単体で選ぶ場合：\(dp_i = A_i\)
• 曲 \(i\) の直前に曲 \(j\)（\(j\) は \(i\) より前にある曲）を置く場合： $\(dp_i = dp_j + A_i + B_j \times B_i\)$

両者をまとめると、次の漸化式が得られます。

\[dp_i = A_i + \max\Bigl(0,\ \max_{j<i}\bigl(dp_j + B_j \times B_i\bigr)\Bigr)\]

ここで \(\max(0, \cdots)\) の \(0\) は「前に何も繋げず、\(i\) から始める」場合に対応します。

最終的な答えは \(\max_i dp_i\) です。

素朴なアプローチの問題点

\(dp_i\) を求める際に、毎回すべての \(j < i\) を調べると \(O(N^2)\) となり、\(N \le 10^5\) では間に合いません（TLE）。

高速化のアイデア

漸化式の中核である $\(\max_{j<i}\bigl(dp_j + B_j \times B_i\bigr)\)\( に注目します。\)x = B_i$ とみなすと、これは

\[\max_{j<i}\bigl(\underbrace{B_j}_{\text{傾き}} \cdot x + \underbrace{dp_j}_{\text{切片}}\bigr)\]

という、複数の直線の中で \(x = B_i\) における最大値を求める操作になっています。

曲 \(j\) を処理し終えるたびに「傾き \(B_j\)、切片 \(dp_j\)」の直線を追加し、曲 \(i\) を処理するときに \(x = B_i\) での最大値を問い合わせれば良い、という流れになります。

アルゴリズム

直線群に対する「直線の追加」と「ある \(x\) での最大値クエリ」を効率よく行うデータ構造として Li Chao Tree を使います。

通常の凸包トリックは傾きやクエリ点が単調である必要がありますが、本問題では \(B_j\)（傾き）も \(B_i\)（クエリ点）も任意の整数なので、それらに制約のない Li Chao Tree が適しています。

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

1. クエリ点になりうる \(x = B_i\) の候補は \(B\) の値そのものなので、\(B\) の値を座標圧縮して Li Chao Tree の区間とする。
2. \(i = 1, 2, \ldots, N\) の順に：
   • \(x = B_i\) での直線群の最大値 \(bp\) を query で取得する。
   • \(bp < 0\) なら \(0\) に置き換える（単体スタートの選択肢）。
   • \(dp_i = A_i + bp\) を計算し、答えを更新する。
   • 傾き \(B_i\)・切片 \(dp_i\) の直線を Li Chao Tree に insert する。

\(i\) を昇順に処理することで、「query 時には \(j < i\) の直線だけが追加済み」という順序が自然に保証されます。

Li Chao Tree の動作イメージ

各ノードは「その区間で（おそらく）最大になっている直線」を 1 本保持します。

• insert：新しい直線とノードの直線を区間の中央で比較し、勝った方をノードに残し、負けた方を「優勢になりうる側の子」へ再帰的に降ろしていきます。
• query：根からクエリ点を含む葉まで降りながら、通過した各ノードの直線の値を評価し、その最大値を答えとします。

どちらも木の高さ分、すなわち \(O(\log N)\) で完了します。

計算量

• 時間計算量: \(O(N \log N)\)（各曲につき insert と query をそれぞれ \(O(\log N)\) で行う）
• 空間計算量: \(O(N)\)（Li Chao Tree のノード配列）

実装のポイント

• 64bit整数：\(A_i, B_i\) が最大 \(10^6\) 程度なので、\(B_j \times B_i\) や累積で大きな値になります。NEG = -(1 << 62) を「直線がまだ無いことを表す番兵」として用いています（Python では多倍長整数なので桁あふれの心配はありませんが、値域を意識した設計になっています）。

• 座標圧縮：xs = sorted(set(B)) でクエリ点候補を圧縮し、comp で値からインデックスを引けるようにしています。Li Chao Tree はこの離散点集合上で動作します。

• bp < 0 の処理：直前に何も繋げず曲 \(i\) 単体から始める方が得なケースに対応するため、最大値が負なら \(0\) に置き換えています。これにより「単体スコア」と「連結スコア」を統一的に扱えます。

• 処理順序：for i in range(n) の中で「query → dp 計算 → insert」の順を守ることで、\(i\) より前の曲の直線だけが参照される正しさが保たれます。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    A = [0] * n
    B = [0] * n
    idx = 1
    for i in range(n):
        A[i] = int(data[idx]); B[i] = int(data[idx + 1])
        idx += 2

    xs = sorted(set(B))
    nn = len(xs)
    comp = {v: i for i, v in enumerate(xs)}
    NEG = -(1 << 62)
    size = 4 * nn
    M = [0] * size
    Bb = [NEG] * size

    def insert(nm, nb):
        node = 1; l = 0; r = nn - 1
        while True:
            mid = (l + r) >> 1
            xm = xs[mid]
            cm = M[node]; cb = Bb[node]
            if nm * xm + nb > cm * xm + cb:
                M[node] = nm; Bb[node] = nb
                nm, nb = cm, cb
            if l == r:
                return
            xl = xs[l]
            if nm * xl + nb > M[node] * xl + Bb[node]:
                node = node << 1; r = mid
            else:
                xr = xs[r]
                if nm * xr + nb > M[node] * xr + Bb[node]:
                    node = (node << 1) | 1; l = mid + 1
                else:
                    return

    def query(xi):
        x = xs[xi]
        node = 1; l = 0; r = nn - 1
        res = NEG
        while True:
            v = M[node] * x + Bb[node]
            if v > res:
                res = v
            if l == r:
                break
            mid = (l + r) >> 1
            if xi <= mid:
                node = node << 1; r = mid
            else:
                node = (node << 1) | 1; l = mid + 1
        return res

    ans = NEG
    for i in range(n):
        bi = B[i]
        xi = comp[bi]
        bp = query(xi)
        if bp < 0:
            bp = 0
        dpi = A[i] + bp
        if dpi > ans:
            ans = dpi
        insert(bi, dpi)

    print(ans)

main()

---

この解説は claude4.8opus-high によって生成されました。