ferinの競プロ帳

競プロについてのメモ

DP高速化

dp[i][j] = min(dp[i][k] + cost[k]) みたいなdpの遷移がうまくやると高速にできるみたいなテクのまとめ

ConvexHullTrick

以下の二つのクエリに答えられるというテク

  • 直線y=ax+bを追加する
  • x=iのときの最小(最大)のyを求める

追加する直線の傾きが単調、最小クエリのxが単調であると実装が楽になる。
O(n^2) → O(n) or O(nlogn) に高速化

詳しくは以下を見てください。
Convex-Hull Trick - sataniC++, Convex Hull Trick - 競技プログラミング+αなブログ, 蟻本p304

問題例

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君
Codeforces Round #189 (Div. 1) C. Kalila and Dimna in the Logging Industry 解説
Codeforces Round #185 (Div. 1) B. Cats Transport 解説

Knuth-Yao Speedup

X[i][j] = min_{i<=s<j} (X[i][s] + X[s+1][j]) + W[i][j] の形のDPを高速化するテク
WがQI(Quandrangle Inequality)かつ単調なときに使える
O(n^3) → O(n^2) に高速化

詳しくは以下を見てください。
Knuth-Yao speedup - 週刊 spaghetti_source - TopCoder部

問題例

KUPC2012 J - 刺身 解説
SPOJ BRKSTRNG - Breaking String 解説

Hu-Tucker Algorithm, Garsia-Wachs Algorithmといったより強いのもあるらしい。
最適二分探索木問題(KUPC 2012 問題J 「刺身」) - (iwi) { 反省します - TopCoder部

monotone minima

2変数関数f(i,j)で各行の最小値が右下へ単調に下がっていくとき、各行の最小値を高速に求められるテクf:id:ferin_tech:20180223072028p:plain O(n^2) → O(nlogn) に高速化

詳しくは以下を読んで下さい。
Totally Monotone Matrix Searching (SMAWK algorithm) - 週刊 spaghetti_source - TopCoder部

問題例

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君 解説

Divide and conquer

dp[i][j] = min_{0<=k<i} {dp[i-1][k] + w(k,j)} の形のDPを高速化するテク
wがQIなら最小値を達成するkに単調性が存在し高速化することができる
Knuth-Yao speedupとこれはargminの単調性を使ってdpテーブルを埋める順を変えてるイメージ

コードを見てもらうのが一番わかりやすいと思うのでコードをのせます。[l,r]の区間ではargminが[optl,optr]の区間に存在するようになっています。dp[i][mid]を区間[optl,optr]を線形に探索することで求めます。するとargminの単調性より[l,mid-1]ではargminが取りうる区間が[optl,optm]、[mid+1,r]ではargminが取りうる区間が[optm,optr]となります。argminが存在しうる範囲が狭まっていくので全てを計算する必要がなく計算量が落ちます。真面目に計算するとO(NKlogN)になるらしい。

function<void(int,int,int,int,int)>
func = [&](int i, int l, int r, int optl, int optr) {
  if(l > r) return;
  int mid = (l+r)/2, optm = -1;
  FOR(j, optl, min(mid+1, optr+1)) {
    if(dp[i][mid] > dp[i-1][j] + W[j+1][mid]) {
      dp[i][mid] = dp[i-1][j] + W[j+1][mid];  // [j+1, mid]
      optm = j;
    }
  }
  func(i, l, mid-1, optl, optm);
  func(i, mid+1, r, optm, optr);
};
// dpの初期値を設定
REP(i, n) dp[0][i] = W[0][i];
FOR(i, 1, n) REP(j, k) dp[i][j] = LLINF;
// DPする
FOR(i, 1, k) func(i, 0, n-1, 0, n-1);
cout << dp[k-1][n-1] << endl;

問題例

Codeforces Round #190 (Div. 1) E. Ciel and Gondolas 解説
Codeforces Round #438 F. Yet Another Minimization Problem 解説

あとはセグ木を使って高速化とかがありそう
とりあえずDPっぽかったら漸化式を書いて高速化できる形になっていたらQIとかを確認するとかするとよさそう

参考ページ
直前合宿 講義スライド