結果
| 問題 | No.3188 K-th Lexmin |
| コンテスト | |
| ユーザー |
 navel_tos
|
| 提出日時 | 2025-12-10 19:08:57 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 603 ms / 3,500 ms |
| コード長 | 12,375 bytes |
| 記録 | |
| コンパイル時間 | 299 ms |
| コンパイル使用メモリ | 82,420 KB |
| 実行使用メモリ | 130,924 KB |
| 最終ジャッジ日時 | 2025-12-10 19:09:27 |
| 合計ジャッジ時間 | 26,242 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 47 |
ソースコード
#yukicoder3188 K-th Lexmin
#from: https://x.com/Not_Leonian/status/1998418802997112975
def main():
#string for codon, PyPy3
class string:
'''
string for codon, PyPy3
'''
def _suffix_array(A: list[int]) -> list[int]:
#Reference: https://qiita.com/flare/items/ac11972dbc590a91980d
#Reference: https://speakerdeck.com/flare/sa-is
if len(A) < 2:
return list(range(len(A)))
#Aを座標圧縮
min_Ai, max_Ai = min(A), max(A)
diff: int = max_Ai - min_Ai + 1
if diff <= 5 * len(A): #bucket sort
bucket: list[int] = [0] * max(diff, len(A) + 1)
for Ai in A:
bucket[Ai - min_Ai] = 1
mex: int = 1
for x in range(diff):
if bucket[x]:
bucket[x] = mex
mex += 1
for i, Ai in enumerate(A):
A[i] = bucket[Ai - min_Ai]
else: #O(NlogN) sort
bucket: list[int] = sorted(range(len(A)), key = A.__getitem__)
back: int = A[bucket[0]]
mex: int = 1
for i in bucket:
if back != A[i]:
back: int = A[i]
mex += 1
A[i] = mex
mex += 1
if mex > len(bucket):
bucket.append(0)
A.append(0)
#SA-IS
B: list[int] = [0] * len(A)
R: list[int] = [0] * max(mex, len(A) >> 1)
string._SAIS(A, B, bucket, R, mex)
B.pop()
return B
def _SAIS(A: list[int], B: list[int], L: list[int], R: list[int], mex: int) -> None:
#suffix-arrayの結果をB[-1:]に登録する
#1. L, S, LMS typeの分類 T[i]: (L / S / LMS) = (-2, -1, 0から出現順採番)
N: int = len(A)
T: list[int] = [-1] * N
LMS: list[int] = []
for i in range(N - 2, -1, -1):
T[i] = -2 if A[i] > A[i + 1] else T[i + 1] if A[i] == A[i + 1] else -1
for i in range(1, N):
if T[i - 1] == -2 and T[i] == -1:
T[i] = len(LMS)
LMS.append(i)
#2. 頻度分布の作成 F[Ai]: -1 - indexedの累積和
F: list[int] = [0] * (mex + 1)
F[0] = -1
for Ai in A:
F[Ai + 1] += 1
for Ai in range(mex):
F[Ai + 1] += F[Ai]
#3. induced sortを行い、LMS部分文字列を採番 C[i]: LMS[i]の採番結果
string._induced_sort(A, B, L, R, F, T, LMS, mex)
C: list[int] = [0] * len(LMS)
same: bool = False
if len(C) > 1:
#a) B[0]以降最小のLMSを探す -1 - indexedなので B[-1] = N - 1 に注意
for i in range(N - 1):
back: int = T[B[i]]
if back >= 0:
C[back] = c = 1
Lback, Rback = LMS[back], LMS[back + 1]
break
#b) LMS部分文字列を順に採番
for i in range(i + 1, N - 1):
now: int = T[B[i]]
if now >= 0: #A[Lback: Rback] == A[Lnow: Rnow] の判定
Lnow, Rnow = LMS[now], LMS[now + 1]
if (Rback - Lback == Rnow - Lnow and
all(A[Lback + d] == A[Lnow + d] for d in range(Rback - Lback))):
same: bool = True
c -= 1 #一旦減算して次の行で補正
C[now] = c = c + 1
Lback, Rback, back = Lnow, Rnow, now
#4. LMS orderを決め、再度induced sort
if same == True:
string._SAIS(C, B, L, R, c + 1)
for x in range(-1, len(LMS) - 1):
L[x + 1] = LMS[B[x]] #x + 1の補正で-1 - indexedを修正
else:
for i, Ci in enumerate(C):
L[Ci] = LMS[i]
for i in range(len(LMS)):
LMS[i] = L[i]
string._induced_sort(A, B, L, R, F, T, LMS, mex)
def _induced_sort(A: list[int], B: list[int], L: list[int], R: list[int],
F: list[int], T: list[int], LMS: list[int], mex: int) -> None:
#1. 使い回す配列の初期化 [L[Ai], R[Ai]): 値AiのBへの挿入区間
N: int = len(A)
for Ai in range(mex):
L[Ai], R[Ai] = F[Ai], F[Ai + 1]
for i in range(-1, N - 1):
B[i] = -1
#2. LMS typeをバケット末尾から挿入
for x in range(len(LMS) - 1, -1, -1):
i: int = LMS[x]
Ai: int = A[i]
j = R[Ai] = R[Ai] - 1 #LMS[x]の挿入位置 assert B[j] == -1
B[j] = i
#3. L typeを先頭から挿入し、LMS typeを除去
for x in range(-1, N - 1):
i: int = B[x]
if i > 0: #挿入済み かつ i != 0
if T[i - 1] == -2:
Aback: int = A[i - 1] #assert B[L[Aback]] == -1
B[L[Aback]] = i - 1
L[Aback] += 1
if T[i] >= 0: #自身がLMS type
R[A[i]] += 1
B[x] = -1
#4. S type, LMS typeを末尾から挿入
for x in range(N - 2, -1, -1):
i: int = B[x]
if i > 0 and T[i - 1] != -2:
Aback: int = A[i - 1]
j = R[Aback] = R[Aback] - 1 #assert B[j] == -1
B[j] = i - 1
B[-1] = N - 1
def _LCP(A, SA: list[int]) -> list[int]:
N: int = len(A)
LCP: list[int] = [0] * N
rank: list[int] = [0] * N #rank[i]: A[i:]のsuffix arrayの順位
d: int = 0
for x, SA_x in enumerate(SA):
rank[SA_x] = x
for i, rank_i in enumerate(rank):
j: int = SA[rank_i - 1]
while i + d < N > j + d and A[i + d] == A[j + d]:
d += 1
LCP[rank[j]] = d
d = max(0, d - 1)
if len(LCP) > 0:
LCP[-1] = 0
return LCP
def _Z_algo(A) -> list[int]:
#Reference: https://tjkendev.github.io/procon-library/python/string/z-algorithm.html
N: int = len(A)
B: list[int] = [0] * N
if N > 0:
B[0] = N
Rt: int = 0
same: int = 0
ok: int = 0
for i in range(1, N):
if Rt:
Rt -= 1
same += 1
if B[same] < Rt:
B[i] = B[same]
continue
while i + Rt < N and A[Rt] == A[i + Rt]:
Rt += 1
B[i] = Rt
same: int = 0
return B
#suffix array
def suffix_array(S: str) -> list[int]:
'N = len(S) として、O(N)でsuffix arrayを計算します。'
return string._suffix_array([ord(Si) for Si in S])
def suffix_array(S: list[str]) -> list[int]:
return string._suffix_array([ord(Si) for Si in S])
def suffix_array(A: list[int]) -> list[int]:
'''
N = len(A), d = max(A) - min(A) として、
O(min(N + d, NlogN))でsuffix arrayを計算します。
'''
if len(A) == 0:
return []
elif isinstance(A[0], int):
return string._suffix_array(A[:])
else: #Python・PyPy用分岐
return string._suffix_array([ord(Ai) for Ai in A])
#LCP array
def LCP_array(A, SA: list[int]) -> list[int]:
'''
N = len(A), A: str | list[str] | list[int], SA = suffix_array(A) として、
O(N)で長さNのLCP arrayを作成します。
LCP[i]: 0 <= i < N - 1 のとき、A[SA[i]:]とA[SA[i + 1]:]の最長共通接頭辞
i == N - 1 のとき、0
'''
assert len(A) == len(SA)
return string._LCP(A, SA)
#Z algorithm
def Z_algorithm(A) -> list[int]:
'すべての 0 <= i < N に対し、O(N)でAとA[i:]の最長共通接頭辞を求めます。'
return string._Z_algo(A)
#答案ここから
#note: 計算量評価について
#suffix array ･･･ 1 <= Ai <= N より O(N)
#while K > 0: ･･･ 以下の評価より O(NlogN)
# - A[Li + d] != A[Ri + d] の回数 → この分岐に入るたびに [Lt, Rt) が1減る
# 従ってループ回数はO(N) 二分探索を含めた計算量はO(NlogN)
# - A[Li + d] == A[Ri + d] の回数 → 文字列長は最大Nなので、ループ回数はO(N)
#合計で O(NlogN)time, O(N)space
def solve(N: int, K: int, A: list[int]) -> list[int]:
#1. Aのsuffix arrayを構築
SA: list[int] = string.suffix_array(A)
#2. 文字数の累積和を構築
C: list[int] = [0] * (N + 1)
for i, SA_i in enumerate(SA):
C[i + 1] = C[i] + (N - SA_i)
#3. suffix arrayを読みながら、whileループで1文字ずつ決定
#[Lt, Rt): 答えの範囲 特に SA[Lt, Rt)に該当する文字列は、[0, d)文字目まで一致する
#d: 区間内の文字列の一致数 ここで、d == len(ans) を満たす
#実装メモ: 事前に A[N] = -1 としておくと、配列外参照の分岐を減らせて楽
A.append(-1)
Lt: int = 0
Rt: int = N
ans: list[int] = []
d: int = 0
while K > 0:
#1. 区間内のd文字目が不一致の場合、「d文字目は答えになりうるか？」を判定
Li: int = SA[Lt]
Ri: int = SA[Rt - 1]
if A[Li + d] != A[Ri + d]:
#2. A[Li + d] == A[SA[x - 1] + d] を満たす最大のxを検索
ok, ng = Lt + 1, Rt
while abs(ok - ng) > 1:
mid: int = (ok + ng) >> 1
if A[Li + d] == A[SA[mid - 1] + d]:
ok = mid
else:
ng = mid
#3. d文字目は A[Li + d] で確定できるか？
#s := A[Li + d] として、d文字目をsにしない場合、
#SA[Lt, ok) := ans + s + 何か の数列群 の範囲の数列の個数分まとめて飛ばせる
offset: int = (C[ok] - C[Lt]) - d * (ok - Lt)
assert offset >= 0 #d文字目で終わるパターン A[Li + d] == A[N] == -1
if K <= offset:
Rt: int = ok
K -= Rt - Lt
ans.append(A[Li + d])
d += 1
else:
K -= offset
Lt: int = ok
else: #文字が一致している場合
K -= Rt - Lt
ans.append(A[Li + d])
d += 1
A.pop()
return ans
'''
#ランダムテスト
from random import randrange
def brute(N: int, K: int, A: list[int]) -> list[int]:
return sorted(A[i: j] for i in range(N) for j in range(i + 1, N + 1))[K - 1]
for _ in range(10 ** 5):
N: int = randrange(1, 20)
K: int = randrange(1, (N * (N + 1) // 2) + 1)
A: list[int] = [randrange(1, N + 1) for _ in range(N)]
assert brute(N, K, A) == solve(N, K, A)
else:
print('ランダムテスト OK')
'''
#実行
import sys
input = sys.stdin.readline
T: int = int(input())
B: list[str] = [''] * T
for t in range(T):
N, K = map(int, input().split())
A: list[int] = [int(Ai) for Ai in input().split()]
B[t] = ' '.join(str(Ai) for Ai in solve(N, K, A))
sys.stdout.write('\n'.join(B))
main()