ABC134 E - Sequence Decomposing - あっとのTECH LOG

問題原文

問題要旨

長さ $N$ の整数列を塗り分けることを考える。
同じ色で塗られたものからなる数列が狭義単調増加数列になっているようにするためには、最低何色で塗る必要があるか？

$1 \leq N \leq 10^{5}$

解法

例えば、すでに２種類の色を使っていて、それぞれの現状の最大値が2, 5 であるとする。
このとき、7という数を次にみたとして、明らかに5と同じ色で塗って損しない。（2と同じ色で塗ると、後から3とかで塗ったときに損してしまう）
よって前から貪欲に、最もその数に近くてその数より小さい数を探すように処理していけばいい。

実装１

どちらかというと実装の方が悩ましい。
「各色の現状の最大値」を管理 & 高速に更新していく必要がある。

これは、各色の現状の最大値を管理するリストを持っておくのがおすすめ。
ギリギリ小さい数を探すのは二分探索でできる。
どの色にも塗れないようなときは、リストの先頭に追加する。リストの先頭への追加は $O(N)$ かかってしまうので、 deque を使う。

ギリギリの値を探して更新するので、更新後のリストもソート済みの状態になる。

from collections import deque
from bisect import bisect_left
N = int(input())
A = [int(input()) for i in range(N)]

X = deque([])

for a in A:
    i = bisect_left(X, a)
    if i == 0:
        X.appendleft(a)
    else:
        X[i - 1] = a


print(len(X))

余談

競技プログラミング界隈を代表するゴリラであるところの、 prd_xxxさんによると、実は deque のランダムアクセスは相当に遅いらしい。
↑の実装は520msで通っているものの、あんまりいいとは言えなさそうです。

prd_xxxさんがランダムアクセスが $O(1)$ のdeque を作っておられました。（すごい）
prd_xxx 様の記事↓
prd-xxx.hateblo.jp

実装２

deque のランダムアクセスの遅さを狙い撃つようなケースがある場合、なんとか高速に更新する必要があるが、↑を即席で作るのは僕にはかなり厳しいです。
ただのリストを使えばランダムアクセスの遅さは解消できますが、先頭へのinsertが遅いという問題が残ってしまいます。
ということで要素の正負を逆転させて、「末尾が最も小さい値が入る」という実装に持っていけばOK。

from bisect import bisect_right
N = int(input())
A = [int(input()) for i in range(N)]
A = [-a for a in A]
 
X = []
for a in A:
    i = bisect_right(X, a)
    if i == len(X):
        X.append(a)
    else:
        X[i] = a
 
 
print(len(X))

これで 237ms。ちょっと速くなりましたね。

感想

考察ターンは 損しない→貪欲法 の流れですね。実装ターンでつまらないためには、「ある値の入る場所をにぶたんで探して更新したも、ソート済みの状態は保たれる（それはそう）」ということを頭の片隅い入れておくとよさそうです。（僕はソート崩れるくない？とかいらない心配をしたので）

あと最後の 正負反転させて嬉しい！ みたいなケース、どこかで役に立つかもしれません。