Competitive Programming (1) Advent Calendar 2018の20日目の記事です。この記事では、最近流行り（？）のConvexHullTrickを少し別の角度から見て行こうと思います。
では、まずこの問題を見て見ましょう
CF189DIV1C Kalila and Dimna in the Logging Industry
問題概要をきわめてざっくり説明すると、長さn(<=10^5)の2つの数列a,bが与えられて、dp[i]=min(j<i)dp[j]+a[i]*b[j]というDPを解けばいいです。ただし、aは狭義単調増加でbは狭義単調減少です。</ppp>
この問題は、2次元平面上に直線がどんどん追加されていき、あるx座標においてy座標が最も小さくなる直線を求めるということを繰り返すという問題ということができます。そして、「追加クエリにおける直線の傾きが単調」「最小値クエリにおけるxが単調」の2つを満たしているので、ConvexHullTrick（最近はCHTと略されることが多いらしいですね･･･最初に見たときは何のことか全く分かりませんでした）を用いてO(n)で解くことができます。ConvexHullTrickの詳しいことは例えばこちらの記事をご覧ください。ConvexHullTrickを用いた解答コードは以下のようになります。
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint a[100010],b[100010],dp[100010];
int deq[100010];
lint cal(int i,int j){return dp[j]+b[j]*a[i];}
double cro(int i,int j){return (0.0+dp[j]-dp[i])/(b[i]-b[j]);}
int main()
{
int s=0,t=1,n;
cin>>n;
rep(i,n) scanf("%I64d",&a[i]);
rep(i,n) scanf("%I64d",&b[i]);
dp[0]=0;deq[0]=0;
REP(i,1,n){
while(s+1<t && cal(i,deq[s])>cal(i,deq[s+1])) s++;
dp[i]=cal(i,deq[s]);
while(s+1<t && cro(deq[t-1],i)<=cro(deq[t-1],deq[t-2])) t--;
deq[t++]=i;
}
cout<<dp[n-1]<<endl;
}
これ、コードの行数は少なくて極めてシンプルなコードに見えますよね？でも自分はこのコードを書く時に意外と苦労した記憶があります。配列を使ってdequeの中身を操作するのですが、どのタイミングでiteratorの値を動かせばいいのか、中身が十分に入ってなくて値の比較ができないというのはどこで判定すればいいのか･･･などなど、コードにも-1や-2をどこで入れるのかなど細かいことに気を使う印象です。
さて、今の問題はいったん置いといて次の問題について考えてみましょう
n×nの2次元配列cが与えられる。各行ごとに最小値をとる列を全て求めよ。ただし、各行ごとに最小値をとる列の場所は広義単調増加になっている
つまり各行ごとに最小値をとる列を赤く塗るとこのようになっているということですね。
これはもちろん愚直にやればO(n^2)ですが、この性質を利用してより効率的に求めることができます。
まず、真ん中の行の最小値をとる列の場所を調べます。そうすると単調性より、その場所の（図の上での）右上と左下には最小値をとる場所は存在しないことが分かります。
次に、左上と右下のブロックそれぞれにおいて同様に真ん中の行の最小値をとる場所を調べて･･･ということを再帰的に繰り返すと、全体でO(nlogn)で求めることができます。より詳しい解説はこちらの記事をご覧下さい。
これを使うと、例えば2次元DPで、配列dp[i]の各値が配列dp[i-1]の各値から遷移され、かつその遷移元の位置が遷移先の位置に対して広義単調であることが分かる場合（図で表すと下のようになります。これを私は勝手に「遷移が交差しない」状態と呼んでいます。）、dp[i-1]からdp[i]への遷移は愚直にやればO(n^2)のところを上に述べたテクニックを使うことでO(nlogn)で全て行うことができます。
で、この分割統治法がConvexHullTrickとどういう関係があるのかというと、「追加クエリにおける直線の傾きが単調」「最小値クエリにおけるxが単調」の2つを満たしている場合、クエリに対して最小値をとる直線が追加された順番は単調になるという性質が成り立つからです。実際にdequeに直線が追加されたり捨てられたりする順番を考えれば成り立つのが分かると思います。また今回の問題に関しても、dp[j]+a[i]*b[j]が最小となるjがiに対して広義単調増加になる(あるi=i1に対して最小となるjをj1とした時、i=i2>i1に対して最小となるjがj1より小さいはずがない)のは、aが狭義単調増加でbが狭義単調減少なことから分かります。よって、前の節で述べた「遷移が交差しない」という条件を満たします。
しかし、今回の問題では遷移前の状態というのがまさに遷移によって求まるものなので、前節のような方法で求めることはできません。では駄目かというと、ここでもまた分割統治法を使うことで解決できます。
結論から言うと、1次元DPで「遷移が交差しない」という条件が満たされている場合、以下のアルゴリズムを用いれば範囲[0,n)の全ての値の最適解を求めることができます。
１．範囲[0,m)の最適解を求める
２．範囲[m,n)の範囲[0,m)から遷移される部分に関する最適解を求める
３．範囲[m,n)の最適解を求める
ここでm=n/2とします。手順1,3に関しては再帰的に行い、手順2に関しては上に述べた分割統治法を行います。このアルゴリズムの詳しい解説に関してはこちらの記事をご覧下さい。手順2の計算量がO(nlogn)である場合、全体でO(nlog^2n)で全ての値の最適解を求めることができます。このアルゴリズムを用いた最初の問題の解答コードは以下のようになります。
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint inf=1e18;
lint a[100010],b[100010],dp[100010];
lint cal(int i,int j){return dp[j]+b[j]*a[i];}
void cal2(int l1,int h1,int l2,int h2){
if(l1>=h1) return;
int mi=(l1+h1)/2,it=l2;
REP(i,l2,h2){
if(cal(mi,i)<cal(mi,it)) it=i;
}
dp[mi]=min(dp[mi],cal(mi,it));
cal2(l1,mi,l2,it+1);
cal2(mi+1,h1,it,h2);
}
void rec(int lo,int hi){
if(lo+2>hi) return;
int mi=(lo+hi)/2;
rec(lo,mi);
cal2(mi,hi,lo,mi);
rec(mi,hi);
}
int main()
{
int s=0,t=1,n;
cin>>n;
rep(i,n) scanf("%I64d",&a[i]);
rep(i,n) scanf("%I64d",&b[i]);
dp[0]=0;
REP(i,1,n+10) dp[i]=inf;
rec(0,n);
cout<<dp[n-1]<<endl;
}
解答の長さ自体は最初のより長いですが、本当に値を渡して、その範囲の探索を行うだけなので少なくとも個人的にはこちらのコードの方が頭を使わずに書けました。また計算量もO(n)からO(nlog^2n)へと増えているのですが、感覚としてこのアルゴリズムは定数倍が極めて早く、O(nlogn)と同等か下手したらそれより早いイメージがあります。実際、実行時間も最初のコードが78msなのに対しこのコードは108msで済んでいます。
もちろん、この方法はConvexHullTrickが使える場合に限らず、遷移元と遷移先の関係に関して単調性が満たされてさえいれば使えるのですが、そのような単調性を満たす自然な設定にしようとすると大体ConvexHullTrickも使える形になってる場合が多いと思います。なので、単調性を利用した解法を思いついたがそれだとTLEするといった場合は、式変形などを経る事でConvexHullTrickが使える形に帰着できないか考えてみるといいと思います。
結局話としては想定解よりも計算量の大きい解法を説明しただけで、この話は知らなくても解ける問題というのが減るわけではないと思います。でも実装のアプローチを複数持っておくこと自体は悪くないと思いますし、問題の背景にこういう性質が隠れてるのを知るのもそれはそれで面白いんじゃないかと思います。この記事が少しでも皆さんの競プロ人生の役に立てば幸いです。
Dynamic Programming Optimizations