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 なら、 を返す。
解説
を deque とする。
を順番に追加するか判定していく。
を追加する場合を考える。
とおく。
ここで、 は昇順で並んでいることを仮定する。
1. 内で より小さい最大の値のインデックスを求める。
python っぽくいうと、
のこと。
2. 場合分け
- そのようなインデックスが存在しない場合(pythonの0):
deque の先頭に を追加する。
- 存在する場合:
そのインデックスの値を に置換する。
この操作で、 が昇順であることは保たれる。
1 の操作は、python だと直接求められないので、bisect_right と bisect_left を組み合わせて使った。
順番を保つだけなら、bisect_right だけで十分なように感じられるが、
問題の条件に があるので、置換するには より真に小さい値のインデックスを選ぶ必要があるため、
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 は前方にも行っているだけなので、使えてほしいという気持ちはあった。