kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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も違ってくるんだな
ファイルが大きくなると場合によっては問題?