PAST2L
from 第二回 アルゴリズム実技検定
PAST2L
考えたこと
最初の文字として選ぶことが可能な範囲が一つ定まる
最初の文字はその中の最小のものだ
最小が複数あったら？
最も早いものを選べば良い
それ以外を先頭として辞書順最小のがもし存在するなら、先頭を最も早いものに入れ替えても辞書順最小なので。
先頭1文字を決めると、2文字目として選べる範囲が決まる
これを繰り返せば良い
公式解説
具体的な実装に関して上記だとTLEの可能性がある
改めて考えたこと
一旦TLEになってみる
それから高速化の方法を考える
範囲に対するargminを効率よく計算できるといい
sample AC
pythondef solve(N, K, D, AS):
end = N - D * (K - 1)
start = 0
ret = []
for _i in range(K):
subseq = AS[start:end]
if not subseq:
return [-1]
v = min(subseq)
ret.append(v)
start = AS.index(v, start) + D
end += D
return ret8 TLE
ここから高速化するとなると、やっぱりDisjoint Sparse Tableかなー
範囲が後ろにずれていくだけなので優先度キューでよい
無効になった値を読み飛ばすスタイル
AC
pythondef solve(N, K, D, AS):
from heapq import heappush, heappop, heapify
end = N - D * (K - 1)
start = 0
ret = []
queue = [(AS[i], i) for i in range(start, end)]
heapify(queue)
for _i in range(K):
if start >= end:
return [-1]
while True:
v, i = heappop(queue)
if start <= i < end:
break
ret.append(v)
start = i + D
for i in range(end, min(end + D, N)):
heappush(queue, (AS[i], i))
end += D
return ret"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]