AtCoder Beginner Contest 134 E Sequence Decomposing

ABC 134 E Sequence Decomposing を解いたので。
pythonだからか、少し違うコードなので記しておく。
問題はこれ
E - Sequence Decomposing

Remark

bisect_left や bisect_right は順序を保ったまま挿入する場合のインデックスを示している。
bisect_left は最も左のものを、bisect_right は最も右のものを返す。
例えば、

bisect_left([1,1,1,2,2,2,3,3,3], 3) 

3

を返す。
同様に、bisect_right なら、6 を返す。

解説

 d を deque とする。
 \{A_1, \ldots, A_N\} を順番に追加するか判定していく。

 A_i を追加する場合を考える。
 a = A_i とおく。
ここで、d は昇順で並んでいることを仮定する。

1. d 内で a より小さい最大の値のインデックスを求める。
python っぽくいうと、
 \mbox{(挿入する場合のインデックス)} -1
のこと。
2. 場合分け

  • そのようなインデックスが存在しない場合(pythonの0):

deque d の先頭に a を追加する。

  • 存在する場合:

そのインデックスの値を  a に置換する。

この操作で、 d が昇順であることは保たれる。
1 の操作は、python だと直接求められないので、bisect_right と bisect_left を組み合わせて使った。
順番を保つだけなら、bisect_right だけで十分なように感じられるが、
問題の条件に  A_i < A_j があるので、置換するには  a より真に小さい値のインデックスを選ぶ必要があるため、
bisect_left も必要である。

解答

解答

import sys
input = sys.stdin.readline
from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.appendleft(a)
        else:
            d[t-1] = a
    print(len(d))

if __name__ == '__main__':
    main()


おまけ

deque にも、bisect って使えるんですね。
確かに、list が後方のみにメモリ領域の確保を行うのに対して、
deque は前方にも行っているだけなので、使えてほしいという気持ちはあった。