DPL_1_D: Longest Increasing Subsequence (続き3)
二分探索を自分で書いてみた版
ドンピシャの値じゃなくて、含まれる区間を求めるわけだけど
どうも二分探索苦手
配列の範囲を飛び出ちゃったりとかする
あっちこっちで1足したり引いたりしてるうちにごちゃごちゃしてしまう
エラーもWAも出なくなったバージョンがこれ
def interval(l, e):
if e <= l[0]:
return 0
elif l[-1] < e:
return len(l)
left = 1
right = len(l) - 1
while left < right:
mid = (left + right + 1) // 2
if l[mid - 1] < e <= l[mid]:
return mid
elif l[mid] < e:
left = mid + 1
else:
right = mid - 1
return left
いろいろ考えなおしてこれで動くじゃんってなったときには拍子抜けですよ
def interval(l, e):
left = 0
right = len(l)
while left < right:
mid = (left + right) // 2
if l[mid] < e:
left = mid + 1
else:
right = mid
return left
あとはそれを呼び出してAC
def LIS(n, a):
l = [a[0]]
for e in a[1:]:
if l[-1] < e:
l.append(e)
else:
l[interval(l, e)] = e
return len(l)
実際問題としてはライブラリのbisect
を使う
from sys import stdin
from bisect import bisect_left
def LIS(n, a):
l = [a[0]]
for e in a[1:]:
if l[-1] < e:
l.append(e)
else:
l[bisect_left(l, e)] = e
return len(l)
def main():
n = int(input())
a = list(map(int, stdin.readlines()))
print(LIS(n, a))
main()
自分で書いた版は 00.26s 16676KB で
bisect版は 00.08s 16628KB だからさすがに速い
そうそう今回はループを回すのではなくてreadlines()
で一気に読むというのをやってみた
単純に読むだけでいいならその方が速いかなと思って
a = list(map(int, stdin.readlines()))
を
a = []
for _ in range(n):
a.append(int(stdin.readline()))
に変えたら 00.16s 11136KB
readlines()
だと速いけどメモリは余分に使う
今回は1MB程度のファイルを読んでるだけだけど5MBも違ってくるんだな
ファイルが大きくなると場合によっては問題?