https://codeforces.com/contest/1732/problem/D1
Problem - D1 - Codeforces
codeforces.com
가장 느린 풀이는 문제에서 요구하는 대로 그냥 set만들고 거기에 숫자 넣고 ? 쿼리 들어오면 k-mex를 구하는 것이다.
여기서 들어오는 k에 대해 ans를 map 같은 자료구조를 이용해 전처리 해두고 나중에 다시 그 k에 대한 쿼리가 들어오면 그 때 set에서 ans + i * k가 없을때까지 i를 0부터 돌려주고 다시 ans를 저장하면 시간초과가 나지 않는다.
근데 사실 왜 시간초과가 나지 않는지는 정확히 모른다...
그냥 뇌피셜로는 최악의 경우가 k가 모두 다를 때고 set의 크기를 sz라고 하면 어떤 k에 대해 i의 반복 횟수는 sz / k가 될 것 같고 sz / k가 크기 위해선 k가 작아야 하니까 sz / 1 + sz / 2 + ... sz / q 만큼의 연산이 필요하다.
따라서 o(qlogq)의 시간복잡도(ans를 전처리 하기 위한 map은 제외)가 나오는게 아닐까 싶다.