結果

問題 No.3780 Erase and Mex
コンテスト
ユーザー masasu
提出日時 2026-10-31 12:40:40
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 102 ms / 2,000 ms
+ 980µs
コード長 1,045 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 97 ms
コンパイル使用メモリ 64,392 KB
実行使用メモリ 89,552 KB
最終ジャッジ日時 2026-10-31 12:40:49
合計ジャッジ時間 7,400 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://github.com/robe2222555/atcoder-lib/blob/main/template/python/main.py
import sys
input = lambda: sys.stdin.readline().rstrip()
def LI(): return list(map(int, input().split()))
def II(): return int(input())
INF = 1<<60


def solve():
	N = II()
	A = LI()
	if N==1:
		print(max(1, A[0]))
		return
	
	init = [0]*(N+1)
	for a in A:
		if a>=N+1:
			a = 0
		init[a] += 1

	cnt = [0]*(N+1)
	need = [0]*(N+1)
	ok = 0
	ng = N+2
	while ng-ok>1:
		mid = (ok+ng)//2
		for i in range(mid):
			cnt[i] = init[i]
			need[i] = 1
		for i in range(mid, N+1):
			cnt[0] += init[i]
			cnt[i] = 0

		tmp = 0
		for i in range(1, mid)[::-1]:
			need[i] += tmp
			if need[i] > N:
				need[0] += N+10
				break

			if cnt[i] >= need[i]:
				cnt[i] -= need[i]
				
				cnt[0] += cnt[i]
				cnt[i] = 0
				continue
			else:
				tmp += need[i]-cnt[i]
				continue

		need[0] += tmp
		if cnt[0] >= need[0]:
			ok = mid
		else:
			ng = mid
		continue
	print(ok)
	return


def main():
	T = II()
	for _ in range(T):
		solve()
	return


if __name__ == '__main__':
	main()
0