Search on the blog

2013年6月18日火曜日

Convex Hull TrickでDequeからPop Backするときの条件

Convex Hull TrickでDequeからPop Backするときの条件についてちょっと気になったので、考えてみました。

まずConvex Hull Trickについてですが、ここに詳しい解説があります。

要は、「y_i = a_i * x + b_iという直線集合が与えられて、あるx(複数のxが与えられる)についてy_iが最小になるiを求めよ。というクエリーを効率よく求めるためのトリックで、その応用としてDPの計算を高速化する際にも利用できることがありますよ。」
というもの。



下の3問を解いてみると、どんな感じか感覚がつかめると思います。いずれもConvex Hull Trickに気づくとDequeを使って計算量を落とすことができます。

(K-Anonymous Sequenceは蟻本にも載ってます。恐るべし、蟻本。)

で、何が気になったかというと、Dequeから直線L2をpop_backする条件です。

L1 : y = a_1 * x + b_1
L2 : y = a_2 * x + b_2
L3 : y = a_3 * b + b_3

として、今L3をDequeに入れようとしているとします。
このときL2がもう不要だといえる条件は、「L1とL3の交点 <= L1とL2の交点」です。



L1とL2の交点は、(b_2 - b_1) / (a_1 - a_2)です。L1とL3の交点は、(b_3 - b_1) / (a_1 - a_3)です。よって、

(b_2 - b_1) * (a_1 - a_3) >= (b_3 - b_1) * (a_1 - a_2)

です。

気になったのは、a_1 - a_2 = 0のときとa_1 - a_3 = 0のとき。交点がない(または直線が完全に一致する)けど、上の条件で足りているのか?

場合分けして考えてみました。

i)  a_1 = a_2のとき
(b_2 - b_1) * (a_1 - a_3) >= 0ならL2は不要となります。
a_1 >= a_3なので、b_2 >= b_1のとき不要ということになります。これは直線L2が完全にL1より上の時不要ということなので、正しいです。

ii) a_1 = a_3のとき
a_1 >= a_2 >= a_3なので、a_1 = a_2 = a_3となります。
このときは、(b_2 - b_1) * 0 >= (b_3 - b_1) * 0のときL2が不要となりますが、この条件は常になりたつので、L2は常に不要となります。これは正しい条件でしょうか?

今すでにDequeに入っているL1とL2の状態について考えてみます。L2の方がL1より下にある(またはL1とL2が一致)とすれば、L2を入れる時点でL1は消去されているはずです。ということは、L2の方がL1より上にあるということになり、常にL2はDequeから取り除いて良いということになります。
よってii)の場合も条件(b_2 - b_1) * (a_1 - a_3) >= (b_3 - b_1) * (a_1 - a_2)で足りているということになります。

そういえば今旬の「今でしょっ!」の人が、
「日常生活で、『よし、今日は直線の交点求めるか!』なんていう人がいたらヤバい」みたいなこと言ってたけど、趣味で直線の交点求めて喜ぶ人は少なからずいると思います。

0 件のコメント:

コメントを投稿