80. 二分探索ライブラリの使い方を間違えてWAを生やしまくった話

ここ最近、以下の最長増加部分列（LIS）問題にやたらと手こずっていました。

LIS自体はアルゴリズムも理解して、この問題も解法が分かったのでササッと書いたのですが、何故かサンプルは通るものの他のテストケースの大半が落ちてしまいます。二分探索を自作ライブラリで行っているため、これに問題があるのかとランダムテストを追加したりしましたが、問題なく通ります。

いよいよ最終手段ということで、落ちるテストケースを確認させてもらい、どういう挙動になっているのか調べました。すると、やはり二分探索が上手く行っていないことが分かりました。そして、ここでようやくバグの原因を理解しました。

初め、最長増加部分列（LIS）のDPテーブル更新で以下のようなコードを書いていました。SearchUtil.BinarySearchMin は、指定したラムダ式の条件を満たす、min ~ max のうち最小のインデックスを返すメソッド（自作）です。

for (int i = 0; i < N; i++)
{
    var idx = SearchUtil.BinarySearchMin(0, i, j => A[i] < lis[j] && (j == 0 || lis[j - 1] < A[i]));
    if (idx >= 0) lis[idx] = A[i];
}

LISのDPテーブルは狭義単調増加になっている必要があるため、条件がやや複雑になりますが、条件式自体は正しいです。問題があったのは、この条件を二分探索に用いてしまった点でした。

そもそも、今回のメソッドで二分探索が実行できるような条件 $F$ は、長さ $N$ の配列 $A_i$ （1-indexed）に対してある $j$ $(0 \le j \le N)$ が存在して、 $i \le j$ ならば $F(A_i)$ が偽、かつ、 $i \gt j$ ならば $F(A_i)$ が真になるものです。簡単に言えば、「条件を満たす区間」「条件を満たさない区間」が配列内で二分されるような条件でないと、二分探索は行えません（それが二分探索の前提なので）。

ところが、狭義単調増加の条件はこの性質を満たしません。高々1つの $i$ でしか条件は真になりません。そのため、誤った二分探索が行われてしまいます。

正しい挙動にするには、二分探索で「今見ている値以上の値を保持する」最小インデックスを見つけた後、そのインデックスで「狭義単調増加」になるかを確認する必要があります。

for (int i = 0; i < N; i++)
{
    var idx = SearchUtil.BinarySearchMin(0, i, j => A[i] < lis[j]);
    if (idx >= 0 && (idx == 0 || lis[idx - 1] < A[i])) lis[idx] = A[i];
}

この件から、二分探索の条件は配列内で真偽の区間が二分されるものか、ということをしっかり意識しよう…と思いました。