ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

早稲田大学プログラミングコンテスト2019 I - Ramen

AtCoder プログラミング競技プログラミング

解説を見て通したけど、実装にけっこう手こずったので記録。

解法

距離の2乗をコストに持つDP、といえばCHTです（？）。CHT（Convex-Hull Trick）が使えるように、価格 $p_{i}$ の計算式を

$p_{i}^{\prime} = d_{i}^{2} + \min_{j} (-2d_{j} \times d_{i} + p_{j} + d_{j}^2)$
$p_{i} = \min(p_{i}^{\prime}, x_{i})$

と変形します。 $p_{i}^{\prime}$ が $d_{j}$ についての一次式群から最小値を求める形式になっていて、CHTが使えそうです。

ただしこの問題の場合、CHTで解くには2つの課題があります。

店が開店する順番に価格を決定していく必要があるため $d_{i}$ の値を事前にソートできず、値を取得する点 $d_{i}$ にも追加する直線の傾き $-2d_{j}$ にも単調性がない。
店が閉まるという事象を扱わなければいけない。CHTの「直線を消す」という操作に相当するが、これは無理。

1.の課題に対しては「Li Chao Tree」と呼ばれるものを利用することで解決できます。これはセグメント木を用いて直線群とその直線が最小値をとり得る区間を管理するもので、クエリの単調性を必要としません。

傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog

Li Chao Treeのメモ - 日々ｄｒｄｒする人のメモ

Li Chao Treeの追加/取得クエリの計算量は、長さを $D$ として $O(\log D)$ です。 $D$ は取得クエリの値、すなわち $d_{i}$ の範囲に対応するので $10^{6}$ まで確保しておけばよいです。

そして2.ですが、こちらは日数の区間をセグメント木で管理することで解決できます。必要な操作は「ある日数区間に対してだけ直線を追加する」ことと「ある1日における直線群に対するある点の最小値を求める」ことなので、これらを実現します。

セグメント木の各ノードが日数の区間に対応し、それぞれがLi Chao Treeであるようなデータ構造を考えます。区間 $\lbrack l, r)$ を担当するノードは、「区間 $\lbrack l, r)$ 全体において営業している店（の直線）だけを追加したLi Chao Tree」として動作します。

このようにすると、

ある日数区間への直線追加：その区間に完全に含まれるノードに対して、直線の追加クエリを発行する。
ある1日における直線群に対するある点の最小値：その1日を含む全てのノードに対して最小値取得クエリを発行し、さらにその最小値を取る。

という方法で必要な操作を実現することができます。

f:id:betrue12:20190312212025p:plain

いずれの操作も、1回の扱うノード数は日数管理のセグメント木の長さを $L$ として $O(\log L)$ 個です。 $L$ は日数なので $10^{5}$ まで確保しておけばよいです。

以上より全体計算量 $O(N \log L \log D)$ で解くことが出来ます。座標圧縮で $N$ だけに依存するようにも出来ますが、これで十分でしょう。

注意点として、図のようにLi Chao Treeをセグメント木のノード数だけ作ることになるので、配列ベースで実装すると合計で $O(DL)$ 個の要素を作ってしまいます。ポインタベースで実装しましょう。

ACコード

Submission #4553775 - 早稲田大学プログラミングコンテスト2019

今回の問題で初めてLi Chao Treeを書きました。