概要

各楽曲を「末尾」とするプレイリストの最大スコアを動的計画法で求める問題です。隣り合う曲の相性値の積 \(B_{c_{j-1}} \times B_{c_j}\) が「直線の評価」とみなせることに着目し、Li Chao Tree（直線の集合の最大値クエリ） を使って高速化します。

考察

DP の定式化

「楽曲 \(i\) を末尾とするプレイリストの総合スコアの最大値」を \(\mathrm{dp}[i]\) と定義します。

楽曲 \(i\) を末尾とするとき、その直前の状況は次の 2 通りです。

• 楽曲 \(i\) 単独（\(k=1\)）：スコアは \(A_i\)。
• ある楽曲 \(j\)（\(j<i\)）の後に \(i\) を置く：直前のプレイリストのスコア \(\mathrm{dp}[j]\) に、新たな曲のスコア \(A_i\) とボーナス \(B_j \times B_i\) が加わるので \(\mathrm{dp}[j] + A_i + B_j \times B_i\)。

したがって、

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

となります（\(\max\) の中の \(0\) は「単独で始める」ケースに対応）。答えは全 \(i\) における \(\mathrm{dp}[i]\) の最大値です。

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

上の式を素直に計算すると、各 \(i\) について \(j<i\) をすべて調べるため \(O(N^2)\) となり、\(N \le 10^5\) では間に合いません（TLE）。

どう高速化するか

ここで重要な観察です。\(\max\) の中身

\[ \mathrm{dp}[j] + B_j \times B_i \]

を、変数 \(x = B_i\) についての一次関数とみなすと、

\[ f_j(x) = B_j \cdot x + \mathrm{dp}[j] \]

という 傾き \(B_j\)、切片 \(\mathrm{dp}[j]\) の直線 になります。すると \(\max_{j<i}(\cdots)\) は、

これまでに追加した直線たちの集合を点 \(x = B_i\) で評価したときの最大値

を求める操作そのものです。これは Convex Hull Trick や Li Chao Tree が得意とする処理です。

今回は \(B_i\) が単調とは限らず、追加する直線の傾きも順序がバラバラなので、任意の点クエリ・任意の傾きに対応できる Li Chao Tree を使います。

アルゴリズム

楽曲を \(i=1,2,\dots,N\) の順に処理しながら次を行います。

1. クエリ：現在の直線集合を点 \(x = B_i\) で評価し、最大値 best を得る。
2. DP 更新：\(\mathrm{dp}[i] = A_i + \max(0, \text{best})\) を計算し、答えを更新する。
3. 直線追加：傾き \(B_i\)、切片 \(\mathrm{dp}[i]\) の直線を Li Chao Tree に追加する。

これにより「\(j<i\) のものだけが集合に入っている」状態でクエリできるので、DP の依存関係も正しく保たれます。

Li Chao Tree のポイント

Li Chao Tree は、\(x\) 座標の候補を葉に対応させたセグメント木上で「区間の代表点における最大の直線」を管理するデータ構造です。本問では評価点 \(x\) として現れる値は \(B_i\) のいずれかなので、\(B_i\) を座標圧縮して葉に割り当てています。

• addLine：区間の中央点で勝っている方の直線をそのノードに残し、負けた直線を片方の子へ再帰的に下ろしていく。
• query：根から該当の葉まで降りながら、通過した各ノードの直線を評価して最大値を取る。

計算量

• 時間計算量: \(O(N \log N)\)
  （座標圧縮のソートと、各曲ごとの Li Chao Tree への追加・クエリがそれぞれ \(O(\log N)\)）
• 空間計算量: \(O(N)\)
  （セグメント木のノード数は座標数に比例）

実装のポイント

• 「単独で始める」ケースの扱い：\(\mathrm{dp}[i] = A_i + \max(0, \text{best})\) の \(\max(0, \cdot)\) を忘れないこと。\(\mathrm{dp}[j] + B_j B_i\) がすべて負なら、楽曲 \(i\) を新たな始点にした方が得です。

• 初期値と桁あふれ対策：直線が存在しないことを表す「空」の値として、十分小さい定数 NEG = LLONG_MIN/4 を切片に使っています。m*x で値が大きくなるため、LLONG_MIN をそのまま使うとオーバーフローする危険があるので余裕を持たせています。

• 64bit 整数の使用：\(A_i, B_i\) が最大 \(10^6\) 程度で積や総和を取るため、long long（64bit）で計算します。問題文でも答えが 64bit に収まることが保証されています。

• 座標圧縮：評価に使う \(x\) は必ず入力中の \(B_i\) のどれかなので、\(B_i\) をソート・重複除去して葉のインデックスに対応付けます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = LLONG_MIN/4;

int sz;
vector<ll> xs;
vector<ll> segm, segb; // line: m*x+b ; empty if b==NEG

inline ll evalLine(int node, ll x){
    if(segb[node]==NEG) return NEG;
    return segm[node]*x + segb[node];
}

void addLine(int node,int l,int r, ll m, ll b){
    while(true){
        int mid=(l+r)/2;
        ll cl = (segb[node]==NEG)?NEG:(segm[node]*xs[l]+segb[node]);
        ll cm = (segb[node]==NEG)?NEG:(segm[node]*xs[mid]+segb[node]);
        ll nl = m*xs[l]+b;
        ll nm = m*xs[mid]+b;
        bool left = nl > cl;
        bool midb = nm > cm;
        if(midb){
            swap(segm[node], m);
            swap(segb[node], b);
        }
        if(l==r) return;
        if(left != midb){
            node=2*node; r=mid;
        } else {
            node=2*node+1; l=mid+1;
        }
    }
}

ll query(int node,int l,int r,int pos){
    ll res = evalLine(node, xs[pos]);
    while(l!=r){
        int mid=(l+r)/2;
        if(pos<=mid){ node=2*node; r=mid; }
        else { node=2*node+1; l=mid+1; }
        res = max(res, evalLine(node, xs[pos]));
    }
    return res;
}

int main(){
    int N;
    scanf("%d",&N);
    vector<ll> A(N), B(N);
    for(int i=0;i<N;i++){
        scanf("%lld %lld",&A[i],&B[i]);
        xs.push_back(B[i]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sz = xs.size();
    segm.assign(4*sz, 0);
    segb.assign(4*sz, NEG);
    
    ll ans = NEG;
    for(int i=0;i<N;i++){
        int pos = lower_bound(xs.begin(), xs.end(), B[i]) - xs.begin();
        ll best = query(1,0,sz-1,pos);
        ll cur = A[i] + max(0LL, best);
        ans = max(ans, cur);
        addLine(1,0,sz-1, B[i], cur);
    }
    printf("%lld\n", ans);
    return 0;
}

---

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