Day 055-Q3 — Convex Hull Trick + DAG DP

2026-06-08 赤色 Master / Phase 8+ ★★★★★★★★★ Li Chao Tree / DAG DP / 傾き最適化 / 最長重み付きパス

問題

$N$ 個の都市が有向辺で接続されている（DAG、$i < j$ 形式）。辺のコストは $w_{ij} = a_i \times b_j$（各頂点に属性 $a_i, b_j$ が付与）。都市 $1$ から都市 $N$ への最大重み経路を求めよ。

制約

パラメータ範囲
$N$$2 \le N \le 2 \times 10^5$
$M$$1 \le M \le 3 \times 10^5$
$a_i, b_i$$1 \le a_i, b_i \le 10^9$
グラフ形状DAG（トポロジカル順 = 頂点番号順）

入出力例

入力例 1

4 4
3 1 4 1
5 9 2 6
1 2
1 3
2 4
3 4

出力例 1

33

経路 $1 \to 2 \to 4$: $a_1 b_2 + a_2 b_4 = 3 \times 9 + 1 \times 6 = 27 + 6 = 33$ が最大。

概念図: Li Chao Tree による傾き最適化

DP の遷移を Li Chao Tree（上凸包最大値クエリ）で高速化 x = b_v y y=3x+0 (u=1, a=3, dp=0) y=1x+27 (u=2, a=1, dp=27) x=b₄=6 18 (line1) 33 (line2) ← MAX Li Chao Tree 各ノードに「優位な直線」を管理 add(slope=a_u, intercept=dp[u]) query(x=b_v) → max value 各ノードで midpoint 比較 「優位でない直線」を子に委譲 add: O(log C) query: O(log C) dp[v] = max over predecessors u of { dp[u] + a_u × b_v } = Li Chao Tree query at x = b_v

ヒント（段階的開示）

ヒント1: 方向性
DP で $dp[v]$ = 頂点 $1$ から $v$ への最大重み経路長。遷移: $dp[v] = \max_{(u,v) \in E} \{dp[u] + a_u \times b_v\}$。 これは $b_v$ を固定したとき $\max_u \{a_u \cdot b_v + dp[u]\}$ という「直線 $y = a_u \cdot x + dp[u]$ の $x = b_v$ での最大値」問題。 Li Chao Tree で $O(\log N)$ per クエリ。
ヒント2: アプローチ
  • DAG のトポロジカル順（= 頂点番号順）に処理
  • 頂点 $u$ が確定したら直線 $(a_u, dp[u])$ を Li Chao Tree に追加
  • 頂点 $v$ を処理するとき: $x = b_v$ でクエリ → $dp[v]$ を更新
  • 全 $b$ 値を座標圧縮して Li Chao Tree を構築
ヒント3: コード骨格 
# Li Chao Tree（最大値版）
class LiChaoTree:
    def __init__(self, xs):
        self.xs = sorted(set(xs))
        self.n = len(self.xs)
        self.idx = {x: i for i, x in enumerate(self.xs)}
        self.seg = [None] * (4 * self.n)  # (slope, intercept)

    def add(self, a, b):  # y = a*x + b
        self._add(1, 0, self.n, (a, b))

    def query(self, x):
        return self._query(1, 0, self.n, self.idx[x])

# トポロジカル順に処理
lct = LiChaoTree(b_values)
dp = [-INF] * N
dp[0] = 0
lct.add(a[0], 0)
for v in range(1, N):
    val = lct.query(b[v])
    if val > -INF: dp[v] = max(dp[v], val)
    if dp[v] > -INF: lct.add(a[v], dp[v])

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    graph_rev = [[] for _ in range(N)]

    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        graph_rev[v].append(u)

    INF = float('inf')

    # Li Chao Tree (max)
    xs = sorted(set(b))
    n = len(xs)
    idx = {x: i for i, x in enumerate(xs)}
    seg = [None] * (4 * n)

    def _add(node, l, r, line):
        if l >= r: return
        mid = (l + r) // 2
        if seg[node] is None:
            seg[node] = line; return
        cur = seg[node]
        line_mid = line[0] * xs[mid] + line[1]
        cur_mid = cur[0] * xs[mid] + cur[1]
        if line_mid > cur_mid:
            seg[node], line = line, cur
        if r - l == 1: return
        if line[0] > cur[0]:
            _add(2*node, l, mid, line)
        else:
            _add(2*node+1, mid, r, line)

    def _query(node, l, r, i):
        if seg[node] is None: val = -INF
        else: val = seg[node][0] * xs[i] + seg[node][1]
        if r - l == 1: return val
        mid = (l + r) // 2
        if i < mid: return max(val, _query(2*node, l, mid, i))
        else: return max(val, _query(2*node+1, mid, r, i))

    def add(slope, intercept):
        _add(1, 0, n, (slope, intercept))

    def query(x):
        return _query(1, 0, n, idx[x])

    dp = [-INF] * N
    dp[0] = 0
    add(a[0], 0)

    for v in range(1, N):
        val = query(b[v])
        if val != -INF:
            dp[v] = max(dp[v], val)
        if dp[v] != -INF:
            add(a[v], dp[v])

    print(dp[N-1] if dp[N-1] != -INF else -1)

solve()

Step-by-Step 解説

1DP 遷移式の変形
$dp[v] = \max_{(u,v)} \{dp[u] + a_u \cdot b_v\}$。$b_v$ を固定すると、これは直線 $f_u(x) = a_u \cdot x + dp[u]$ の $x = b_v$ での最大値問題。「最大値クエリ」なので上凸包（Li Chao Tree の最大化版）を使う。
2Li Chao Tree の構築
$b$ の全値を座標圧縮。Li Chao Tree は各ノードで「中点で優位な直線」を保持。追加時、中点で負けた直線を子ノードに渡す再帰的実装で $O(\log N)$ per add。
3トポロジカル順での処理
$i < j$ の DAG なので頂点番号順 = トポロジカル順。頂点 $u$ が確定 → 直線追加。頂点 $v$ → クエリ。順序が保証されているため、常に前辺の情報が Li Chao Tree に存在する。
4到達不可能の処理
$dp[u] = -\infty$ の頂点の直線は追加しない。クエリ結果が $-\infty$ なら先行辺から到達不可能。最終的に $dp[N-1] = -\infty$ なら $-1$ を出力。

計算量

Li Chao Tree 構築: $O(N \log N)$（座標圧縮 + 初期化）
各辺の追加・クエリ: $O((N+M) \log N)$
全体: $O((N+M) \log N)$
空間: $O(N)$（Li Chao Tree）

よくあるミス

ミス原因正しい書き方
最小化と最大化の混同Li Chao Tree の不等号の向き最大化: line_mid > cur_mid のとき入れ替え
座標圧縮の漏れクエリ値が登録リストにないxs = sorted(set(b)) で全 b を事前登録
到達不可能頂点の直線追加$dp[u]=-\infty$ の直線が他クエリに影響if dp[v] != -INF: add(...)
Li Chao Tree の子方向ミス傾きで左右を決める最大化では傾きが大きい方が左(小x)で有利

次のステップ

  • 発展問題: $w_{ij} = a_i + b_j$（傾き固定、切片が異なる CHT）
  • 関連: Kinetic Heap との比較（動的最小値追跡）
  • 応用: 3次元の場合（$w_{ijk} = a_i b_j c_k$ の多段 CHT / 分割統治）

自己評価