AtCoder ABC 134 E - Sequence Decomposing (Python) - あるエンジニアのAtCoder奮闘記

irisruneです。最近晴れることが多くなりましたが、週末を狙って台風が来るのは辛いですね。

問題

どのようなアプローチで解けばよいかが思いつきにくい問題だと思います。

import sys
import bisect
import collections


def input():
    return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    la = [int(input()) for _ in range(n)]
    result = collections.deque()
    for a in la:
        idx = bisect.bisect_left(result, a)
        if idx == 0:
            result.appendleft(a)
        else:
            result[idx - 1] = a
    print(len(result))


main()

公式解説では広義単調減少部分列の最大の長さを用いていたようですが（流し読みなので違うかもしれません）、今回の解法ではその真逆で狭義単調増加部分列の最少の個数を用います。

まず問題を読み替えると、数列 $A$ を狭義単調増加部分列に分解したときの最少となる個数を求めればよいことになります。これを求めるアルゴリズムは、

部分列の末尾（つまり部分列の最大値）のソート済みリストを用意する。
以下を $i=1,2,\ldots,N$ について繰り返す。
1.のリストに $A_i$ より小さい要素が存在するかを二分探索を用いてチェックする。
存在するならば、その中で最大の要素を $A_i$ に置き換える。
存在しないならば、リストの先頭に追加する。

このように示すことができ、最終的にリストの要素数が出力すべき値となります。

計算量についてですが、愚直に実装すると最悪計算量は $O(N^2)$ となります。理由としては、通常のリストの先頭に要素を追加する際にはリストの要素数分の計算量が必要になるためです。

そこで上記コードではdequeを用いることで要素の追加に必要な計算量を $O(1)$ に抑えています…が、要素の更新にかかる最悪計算量が要素数（の半分）となるため、結局 $O(N^2)$ となってしまうことに後で気付きました。

実際には実行時間が410msと余裕で間に合っているので、厳密に解析すれば計算量は $O(N\log N)$ に抑えられているのかもしれません。例えば要素の更新回数が多い場合は要素の追加が少ないため要素数が少なく、計算量はそれほど大きくならないといった推測ができます。

雑記

通常のリストに対する末尾への要素の追加が計算量であることを用いれば、上記の解法でも計算量をに明確に抑えることができます。
- 例えば、降順のリストに対する二分探索を実装する、 $A_i$ の符号をすべて反転させるといった方法が考えられます。