最長増加部分列（LIS）の問題に4日間かかった件について
本日、とあるしょうもない事情で解く羽目になっていた問題を4日間かけて解くことができました。
ということで、おそらく全国の競プロerから鼻で笑われるはずですが、格闘した結果をさらします。
※本記事では onlinejudge.org の「10131 - Is Bigger Smarter?」の解法について言及します。ネタバレが嫌いな方はご注意ください。
どんな問題？
回答したのは onlinejudge.org の「10131 - Is Bigger Smarter?」という問題です。
問題としては、競プロ界では基本的な最長増加部分列（LIS）問題の応用形といった形です。
オーソドックスな解法としては、elephantをIQで降順にソートし、その後IQやweightが等しくならないようにweightの最長増加部分列を求めるといった具合だと考えられます。
問題を解き始めた当初、私もこの構想まではたどり着けていました（自慢）。しかし、最長増加部分列問題のアルゴリズム実装で事件は起こりました。
最長増加部分列（LIS）ってどう解くの？
最長増加部分列（LIS）問題のアルゴリズムを知らなかった私は、もちろんgoogleや蟻本で調べたわけですが、悩み初めてから3日経つまで以下のことに気が付きませんでした。
最長増加部分列（LIS）の長さを求めるためには動的計画法が利用できるが、実装方針としては2通りある。
解法1. 「長さ i の増加部分列の末端要素をなるべく小さくする」方針
（例：最長増加部分列(LIS)の長さを求める - Qiita）
解法2. 「配列の j 番目の要素が増加部分列の末端であると仮定したとき、増加部分列が最も長いものを見つける」方針
（例：https://yukicoder.me/wiki/longest_increasing_subsequence）
そして、肝心の最長増加部分列は解法2でしか求められなかったということに・・・・
1つ目の解き方
先ほど紹介した解法1は、二分探索を用いることで計算量 O(nlogn) で計算できますが、最長増加部分列の「長さ」しか求めることができないということを理解できていませんでした。
例えば、｛1, 3, 5, 2｝という配列の最長増加部分列を1つ目の解き方で解くと、dpテーブルは
| i | 0 | 1 | 2 | 3 | 4 |
| dp[i] | 1 | 2 | 5 | INF | INF |
となり、最長増加部分列の長さである3は求まるものの、dpテーブルは｛1, 2, 5｝となっており、正しい最長増加部分列を求めることができません。
私は「10131 - Is Bigger Smarter?」を解く際に、こちらの方法で挑んでしまい時間を大幅ロスする結果になりました。
2つ目の解き方
解法2は、計算量 O(n*n) とやや低速になるものの、配列のi番目の要素を末端に持つ増加列の最大長を保存するテーブルmax_lengthと自分の要素の親を保存するテーブルparentを設けることで、最長増加部分列とその長さの両方を求めることができます。
例えば、a ＝｛1, 3, 5, 2｝という配列の最長増加部分列を2つ目の解き方で解くと、dpテーブルは
| i | 0 | 1 | 2 | 3 |
| a[i] | 1 | 3 | 5 | 2 |
| max_length[i] | 1 | 2 | 3 | 2 |
| parent[i] | null | 0 | 1 | 0 |
となり、max_lengthの最大の要素が3であることから、部分増加列の最大長は3であることが分かります。 また、parent[2] → parent[1] → parent[0] → null と後ろからたどることで最大増加部分列の具体例を求めることができます。
反省
貧弱な語彙力と文章力から成る雑記事でしたが、この記事が誰かの役に立つことを願っております。
皆様の競プロ人生に幸あれ。
