sortされたlistを維持したいならbisectをつかう！ -AtCoder学習日記 #6

概要

今回はABC217-Dについてです。TLEから抜け出せずに終わってしまいました．．．
なかなかTLEにならないコードを書くのは難しいですね。
今回はレートが下がりました悲しいです。

ACらないコード

l, q = map(int, input().split())
cut = []

for _ in range(q):
  c, x = map(int, input().split())
  if c == 1:
    cut.append(x)
  else:
    cut_p = list(filter(lambda s: s <= x, cut))
    cut_n = list(filter(lambda s: s > x, cut))
    if len(cut_p) == 0:
      if len(cut_n) == 0:
        print(l)
      else:
        print(min(cut_n))
    else:
      if len(cut_n) == 0:
        print(l - max(cut_p))
      else:
        print(min(cut_n) - max(cut_p))

切断部分を記録しておいて、長さを取得する際は含まれていて欲しい部分より「大きい最小値」と「小さい最大値」の差を出力する。
と言った考え方です。
解説読んだ感じだと、考え方自体は間違っていなかったみたいですね．．．

解決策について

どうやら、解き方は間違っていない模様ですが、Listに挿入するときに少し工夫をすることでTLEを脱出できそうです。
今回はPythonのbisectを使ってみようと思います。

bisectライブラリとは

Pythonの二分探索を用いた標準ライブラリです。少ない計算量でListをソートされた状態を保つことができます。
詳しいことは参考文献に書いてあります。今回はbisect_leftを使うことになりそうです。
bisect_leftはソートされた状態を保ったまま挿入する場合のindexを返してくれるメソッドです。

ACれるコード

from bisect import bisect_left
from array import array

l, q = map(int, input().split())
cut = array('i', [0, l])

for _ in range(q):
  c, x = map(int, input().split())
  index = bisect_left(cut, x)
  if c == 1:
    cut.insert(index, x)
  else:
    print(cut[index] - cut[index-1])

listではTLEのままだったので、arrayを使用してみたらうまくいきました。
もしかしてarrayの方が早い...?

まとめ

• 順序を保ったまま挿入したい場合はbisectを使おう！
• listよりもarrayを使った方が高速みたいです。
• 今回はレートが下がりました悲しいです。

参考文献

qiita.com

docs.python.org