ONTAK 2015

https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2015/dashboard/

http://zimpha.github.io/2015/09/23/ontak-2015-translation/

풀 수 있는 거 다 풀어서 종결했습니다. 아인타가 paint 못푼다고 놀려서 올클 도전하기로 했습니다. 올클했습니다. 푼건 이 색깔로 표기합니다.

구현은 https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak15_ 로 시작하는 파일들입니다.

Day 1

cie

풀이 설명은 귀찮으니 생략. 요약하자면 왼쪽 오른쪽으로 슥슥 긁으면 풀리는데 구현은 조금 까다롭다. 굉장히 많이 틀렸었는데 이유를 알고 보니 0을 leading zero라고 무시하고 있었다 ㅋㅋ;;

fil

어딜 가든 항상 나오는 사이클 가지고 장난치는 문제. 이런 문제가 대부분 그렇듯 코딩이 약간 까다롭다. 풀이는 귀찮으니 생략.

ksi

재밌는 문제라고 생각한다. 삽입 정렬의 요령을 사용하는 것이 최적이다. (왜인지는 잘 모른다 ㅠ) 빈 집합에 A[0] ... A[n-1] 까지를 인덱스 순으로 삽입한다고 생각해보자. 몇가지 케이스가 있다 :

 * 1. 원소가 정렬된 수열의 맨 끝에 들어간다. 삽입의 개념 자체가 필요 없다. 0을 찍으면 된다.

 * 2. 그렇지 않다. 1번의 삽입으로 A[i] [x < A[i]] [x >= A[i]] 의 형태를 만들 수 있다. 큰 거는 이제 무시해도 되니, 작은 거에서 제대로 된 순서를 맞추는 데 필요한 이동 횟수를 세 보자.

현재 상황에서 수열을 나열해보면 A[i] [1인 원소 C1개] [2인 원소 C2개] ... [A[i] - 1인 원소 C(i-1) 개] 와 같은 형태일 것이다. 같은 값의 원소는 앞서처럼 블록으로 묶어서 같이 생각해보자. 하노이 탑처럼 점화식을 세워서 이동 횟수를 셀 수 있다. [1인 원소 C1개] ... [k인 원소 Ck개] Ai [k+1인 원소 C(k+1) ] ... 인 상태로 만드는 경우를 Mk라고 세우자. Mk = M(k-1) + Ck + Ck * M(k-1) 이라는 식이 나온다. 정리하면 Mk + 1 = (M(k-1) + 1) * (Ck + 1) 이 된다. M0 = 0이고, 우리가 구해야 할 것은 M(i-1) + 1이다. 고로, 답은 (C1 + 1) * (C2 + 1) .... (C(k-1) + 1) 의 형태이다.

위 식은 단순하게 O(Max(Ai)) 에 계산 가능하지만, N번 계산해야 하기 때문에 더 빠른 방법이 필요하다. 원소가 하나 추가될 때마다 Ci가 1씩 증가하기 때문에, 구간의 곱과 원소 갱신을 할 수 있는 Segment Tree를 구현하면 이를 O(lgAi) 에 할 수 있다. 좌표 압축을 해도 되지만 필요없다.

Day 2

bad

다이나믹으로 한번에 처리하려고 하면 잘 안된다. LCS를 앞뒤로 precompute해놓고, string 상의 위치 i에 대해서 [i, X-1] 의 subsequence 중 C가 있는 최소의 X를 precompute 해놓는 식으로, 그리디 + DP를 섞으면 쉽게 풀 수 있다.

baj

각각의 그래프를 유니온 파인드 같은 걸로 관리를 했다면, 두 정점 i, j가 연결되어 있다는 것이, 모든 그래프에서 find(i) == find(j) 라는 것을 의미한다. 즉 find() 값들을 벡터 형태로 가지고 다니면서 같은 원소의 개수를 세는 식의 질의들을 처리하면 되는데, 마음에 안 들지만 아무튼 해싱으로 어렵지 않게 할 수 있는 연산들이다.

한번의 union에 따라서 바뀌는 find 값이 제멋대로이기 때문에 이 값들을 벡터로 효율적으로 관리하기는 쉽지 않다. 경로 압축이나 랭크 압축을 전혀 사용하지 않은 nlgn union find를 사용하면 된다. parent[i] = i 라는 부모 값은 그대로 가지고 있고, is_parent[i] = (parent[i] == i인 원소의 집합) 이라는 벡터를 두자. i - j 정점이 union이 될 때, min(is_parent[i].size(), is_parent[j].size()) 의 시간에 저 값들을 관리해 줄 수 있다. 이렇게만 관리해 주면 nlgn이라는 사실이 잘 알려져 있다.

결론적으로 O(ND * lg(ND) * map access) 시간에 풀 수 있다. map access는 unordered map을 통해서 빠르게 해야 하고, map을 쓰면 TLE가 난다. 마음에 안들어..

sad

3번 쿼리가 구간에 set하는 쿼리가 아니라, 구간에서 h 이하의 나무를 h로 만들어주는 거였다. (번역은 문제가 아닌데.. 아니 구간 maximize를 누가 저렇게 말을 하나 ㅡㅡ) 계속 0점이 나오기에 DM까지 돌렸는데 안 잡혀서 나이브를 짰더니, 0점이 나오더라;; 시간 너무 아깝다.

문제를 제대로 이해했다면 IOI 2014 wall하고 똑같이 풀면 된다.

Day 3

ilo

못 풀겠어서 ainta에게 물어봤다... 사전 지식같은게 많이 필요한 문제는 절대 아니고 그냥 내가 멍청 ㅠ

일단 원점에서 나오는 N개의 벡터에 대한 이야기니, 하나의 벡터 (첫번째라 하자) 의 방향을 (T, 0) (T > 0) 의 형태로 고정시킬 수 있다. 만약에 그렇지 않다면, 벡터 전체를 돌려서 그 벡터가 x축 증가 방향을 향하게 하면 되기 때문이다. 

또한, 이 벡터의 크기를 1로 고정시켜도 괜찮다. 모든 벡터의 X 성분에 1/T를 곱하고, Y 성분에 T를 곱하면 벡터의 크기가 보존되면서 첫번째 벡터의 크기가 1이 된다.

이제, 식을 쉽게 풀 수 있다. X1 = 1, Y1 = 0이고, 이에 따라 Y2 ... YN이 나온다. X2 ... XN간의 관계는 N^2개의 일차방정식으로 나타낼 수 있고, 이는 가우스 소거법으로 N^4에 임의의 해를 구할 수 있다. 

수가 생각보다 작아질 수 있고 오차도 꽤 있는것 같으니 long double 써서 풀고 소수점 20째자리 정도까지 출력해주자. 

pud

결국 순열을 입력으로 주어지지 않는 사이클로 쪼개는 문제이다. N^2 DP 솔루션은, 1번 정점을 포함하는 크기 i-j의 사이클을 하나 잡은 후, 경우의 수를 분석함으로 써 풀 수 있다. 식을 쓰자면 :

DP[i] = Sum(j < i, i - j가 입력으로 주어진 수가 아님) DP[j] * C(i-1, i-j-1) * (i-j-1) !

NK로 바꾸는 건 그렇게 어렵지 않다. 일단 10^9 + 33이 소수니까, 식을 조금 전개하면 :

DP[i] / (i-1)! = Sum(j < i, i - j가 입력으로 주어진 수가 아님) DP[j] / j!

여기서 DP[i] / i! 를 X[i] 라고 정의했을 때,

X[i] = Sum(j < i, i - j가 입력으로 주어진 수가 아님) X[j] / i

X[i] = (Sum(j <i) X[j] - Sum(j < i, i - j가 입력으로 주어진 수) X[j]) / i

답은 X[n] * n!이다. 이제 Sum(j < i) X[i]를 변수 하나에 관리해 주면 O(NK)에 풀린다.

zhb

LCA sparse table을 사용하면 풀 수 있다.

Day 4

bor

N^4 MCMF 이후 아무 진전이 없어서 인터넷을 뒤져봤는데, 플로우 그래프를 세그먼트 트리를 통해서 구성하면 N^3lgN이 나온다고 한다. 

플로우 그래프를 세그먼트 트리를 통해서 구성하는 것은 다음과 같다. 각각의 작업을 source라 하고 시간을 sink라 하면, N^4 방법에서는 모든 시간에 대해서 연속적으로 이어줘야 하기 때문에 N^2개의 간선을 사용한다. 하지만 시간을 세그먼트 트리의 모양으로 전처리해두면, 대응되는 노드 lgN개에 대해서만 이어주면 된다. 이렇게 하면 NlgN개의 간선만으로 플로우 그래프를 효율적으로 구성할 수 있다. V = N, E = NlgN, F = N 이므로 N^3lgN이다.

SPFA가 실제로 대충 V+E에 도니까 (....) N^2lgN 정도라고 믿어보고 짜봤다. 이걸 짜면 모든 데이터에서 9초 안에 나오고 91점을 받을 수 있다. 이게 정해가 맞을까? .....

뭐한거야 ~_~ 너무 일찍 생각을 그만뒀다. 처음에 빈 해집합에서 시작해서, 가중치가 큰 순서대로 해집합에 넣고 이를 만족하는 매칭이 있는지를 찾는다. 존재한다면 해집합에 포함시키고, 아니면 제거 후 계속. 매칭이 존재하는지 그리디로 NlgN에 찾으면 N^2lgN 에 해결 가능하고 lgN은 뗄 수도 있을 것 같다. 해집합에 가중치가 큰 걸 안 넣고 다른 걸 넣어서 더 많은 이득을 볼 경우에 대해서 생각해 볼 수 있는데, 그러한 최적해가 존재한다면, 그 최적해에 가중치가 큰 걸 넣음으로써 개선시킬 수 있기 때문에 이 알고리즘은 정당하다. 그래도 저 세그먼트 트리 아이디어는 (?) 재밌는듯 ㅋㅋ

ofe

여름학교 처음반 수업때도 배우는 잘 알려진 알고리즘이 있다. 마치 토너먼트를 하듯이 N-1번에 걸쳐서 최솟값을 찍으면, 최솟값한테 직접적으로 밀린 후보가 대략 lgN개 존재한다. lgN개에 대해서만 일일히 비교하면 ok. 이해가 안가면 세그먼트 트리에서 원소 갱신을 어떻게 했는지를 생각해보자.

str

아는 문제임 풀이가 궁금하다면 링크 참고.

Day 5

lam

짠 것 중에서 코드가 제일 길다. 260 line / 5KB..

일단 M-N+1 = T라고 하자. dfs tree를 잡으면 back edge가 많아야 T개 나올텐데, back edge의 시작점(root에 가까운 쪽) 의 색깔을 결정하면, 나머지를 결정하는 것은 일반 트리와 비슷하게 dynamic programming을 통해서 할 수 있다. 

색깔을 결정하는 방법은 C(C, T)이기 때문에 그냥 하면 안되고, back edge의 시작점들을 다 모아서 조금 더 현명하게 해야 한다. 정확히는, back edge의 시작점이 {S1, S2, ..., SN} 형태로 놓여져 있을 때, S1 = 1로 해두고, S2부터는 1 혹은 2, Si는 1부터 max(S1 ... S(i-1)) + 1 중 하나... 이런 식으로 조합을 결정하고, 각각의 조합을 고르는 경우 * 해당 조합에서 채색의 경우의 수를 곱하면 된다. 해당 조합에서 채색의 경우는 전술했듯이 동적 계획법으로 구할 수 있다.

동적 계획법을 조금 더 서술하자면, DP[X, C] = 현재 정점 X를 C로 색칠했을 때의 경우의 수... 이런 식으로 하는 것이다. 하지만 이때 C가 너무 커질 수 있기 때문에, C > T인 경우를 하나의 케이스로 또 나눠서 현명하게 한번에 처리하면 O(NT) 정도에 해결이 가능하다.

이렇게 하면 T! * (TN) 이라서 52점이 나온다. 이를 줄이기 위해서 아이디어를 낼 수가 있는데, 실제로 대부분의 작업들이 반복된다는 점이다. 만약에 1 - 2 - 3 - 4 - N - 1 형태의 원형 그래프가 주어졌다고 하면, N - 1이라는 back edge 사이로 들어가는 N-1번의 path에서는 동일한 계산이 반복될 것이다. 이 계산을 줄여 줄 수가 있다.

정확히는, L+2 길이의 체인에서, 1번 정점과 L+2번 정점의 색이 결정되어 있을 때, 나머지 색을 결정하는 경우의 수를 구할 수가 있다. 이 경우의 수는 1번 정점과 L+2번 정점의 색이 다른지 / 같은지에만 종속되고 나머지와는 상관없다. 고로, 이 경우의 수를 초기에 전처리 해놓는다.

이제, 트리 압축을 사용해서 트리를 줄인다. 먼저 degree 1인 정점들을 queue에 넣어서, 모든 정점이 BCC 안에 속하거나 BCC를 잇는 path에 속하거나 둘 중 하나의 경우에만 속하게 트리를 변형시킨다. (저 경우에만 결정하면, 나머지는 자동으로 결정되어서 그냥 (C-1) ^ 제거한 정점을 답에 곱해주면 된다.) 이제 back edge의 시작 / 끝점에 속하는 정점들을 제외하고, 나머지 path들은 최대한 뭉치도록 트리를 압축해 준다. (이부분이 이해가 안간다면 JOI 2014 Factories 문제 풀이를 참고...) 

결론적으로 트리의 실제 정점은 O(T)개가 되며, 긴 path들을 뭉쳐서 관리할 수 있다. 위에 전처리해둔 경우의 수를 통해서 이렇게 축약된 트리에서의 경우의 수를 DP로 비슷하게 구할 수 있다. 이 때 시간 복잡도는 O(T^3) 정도이다. 고로, O(T! * T^3) 정도의 문제를 해결할 수 있다.

wie

모서리처럼 보이는 위치에서 외각을 재서 n각형인지를 유추하는 방법을 썼다. 이걸 하면 n이 작을 때 잘되고 이후에는 문제가 생긴다.

아인타는 도형의 무게중심을 유추한 후, 적당한 크기의 원을 그려서, 원 밖에 삐져나오는 삼각형의 개수를 flood fill로 구했다. 본인은 이걸로 100이 나왔다고 했는데 난 이걸 아무리 해도 잘 안됐다. 특히 n이 작을 때 잘 안되는 거 같아서, 두개를 섞어서 100. (.....)

xor

OR이라는 개념 때문에 DP도 안되고 좀 난해하다. 이럴 때 좋은 방법은 비트를 쪼개서 생각해 보는 것이다.

먼저 a|b >= a^b, 즉 OR을 넣으면 무조건 답이 커진다 라는 점을 알아두자. (이는 M개 이상의 연속구간으로 잘라도 상관없다는 것을 의미한다) 모든 수가 0이나 1이라고 했을 때, 만약의 1의 개수가 홀수이면 답은 무조건 1이다. 1의 개수가 짝수일 때, OR을 넣은 위치가 [1 홀수개] | [1 홀수개] 와 같은 형태로 수열을 가른다면, 답은 1이 되겠지만, 아닌 형태로 갈랐다면 답은 0이다. 즉, [1 짝수개] | [1 짝수개]의 형태로 갈라진 모든 위치에 OR을 넣으면 된다. 많이 자르면 많이 자를 수록 좋으니.

이를 일반화하는 것은 어렵지 않다. 가장 큰 비트부터 봐서, 가장 큰 비트에 0을 넣을 수 있는지를 체크한다. 만약에 0을 넣을 수 있다면, OR을 넣을 수 있는 위치가 한정되게 될 것이다. 작은 비트로 내려가면서, OR을 넣을 수 있는 위치가 M-1개 미만으로 줄어들지 않는 선에서 그리디하게 0을 넣으려고 시도하면 문제를 해결할 수 있다. 좋은 문제.

Day 6

pai

접근을 할 때, 일단 길을 뚫고 -> 그 다음에 나머지 잉여 정점들을 색칠해 준다는 식으로 생각해보자. 길을 뚫었기 때문에, 나머지 잉여 정점들의 서로 다른 색깔의 개수만 알아주면 된다는 점을 알 수 있다. DP로 상태 공간을 정의한다는 게 당연히 불가능할거라 생각하여, 여기서 그리디한 접근 방법을 사용했다. 그리고 못 풀었다..

여기서 잉여 정점에 대해서 조금 더 고찰해보자. 각각의 색깔에 대해서, 관심가져야 할 것은 "지도 가장 오른쪽에 있는 정점이 잉여한지" 만이 중요하다. 지도 가장 오른쪽에 있는 정점이 잉여하지 않은데, 그렇지 않은 정점이 잉여할 수는 없다. 지도 가장 오른쪽의 정점을 색칠해 주는 과정에서, 그 path 옆에 있는 왼쪽에 있는 정점들을 모두 색칠했기 때문이다. 고로, 지도 가장 오른쪽에 있는 정점이 잉여하다면 해당 색깔은 path를 뚫어준 후에 다시 색칠해야 한다는 결론이 나온다. 

핵심 관찰은 끝났고, 이제 동적 계획법으로 문제를 접근할 수 있다. 동적 계획법은 path를 뚫어주는 것과 잉여 정점의 개수를 세주는 것을 동시에 하는 형태로 설계할 수 있다. 동적계획법을 하는 과정은, 마치 실제로 flood-fill을 진행하듯이 1번 정점에서 시작하여 색깔을 흘려주는 방식으로 진행한다. DP[X][Y] = [1, X] 까지를 채웠고, Y = 0일때는 윗 줄만, 1일 때는 아랫 줄만, 2일 때는 위 아래 모두 1번 정점과 연결되어 있다 - 고 생각하자. path를 뚫는 데 드는 비용은 그냥 X와 X+1의 두 숫자가 얼마나 다른지를 계산해 주면 된다. 잉여 정점의 수를 세는 것은, Y = 0이거나 1일 때 선택하지 않은 정점이 해당 색깔 가장 오른쪽에 있는 지를 확인하고, 이를 세어 주면 된다. 고로 O(N) 동적 계획법에 문제가 해결된다. 

tas

머지 소트 하듯이 합치는데, 가져갈 수 있는 스트링 중 lexicographically small한 스트링을 가져가는 탐욕법을 사용. O(N) 풀이하고 O(NlgN) 풀이를 둘 다 생각했지만 O(N)은 코딩이 문제인지 알고리즘이 문제인지 제대로 작동하지 않음 (ㅠㅠ) suffix array 사용해서 O(NlgN)에 풀었음.

tur

k가 상당히 작으므로 2^k 정도의 지수 풀이를 생각해 볼 수 있다. 문제 조건 상 K에 속한 모든 원소를 토너먼트에서 제외해버리면 항상 좋은 경기를 만들 수 있다. 여기서 사용할 접근은, K에 속한 원소 중 몇개를 골라 토너먼트에서 제외하고, 몇개는 토너먼트에 무조건 넣으며, 그 상황에서 N-|K|개의 원소들을 최대한 넣는 방법이다. 무조건 넣기로 한 이러한 원소를 집합 S1라고 하고, N에서 K를 뺀 여집합을 S2라고 하자. 

일단 토너먼트에 넣기로 한 원소끼리는 좋은 경기를 이뤄야 하기 때문에 이걸 k^2 위상 정렬로 검사하자. 이제 S1과 S2는 각각은 좋은 경기를 이룬다. S1의 순서를 해치지 않고 S2의 원소를 넣으려면, 일단 그 원소들을 넣었을 때 사이클이 생기면 안된다. 이는, S2의 순서에서, S1은 낮은 순서에 있는 애들은 모조리 이기다가, 어느 시점에서 갑자기 모조리 지게 되는 시점이 생겨야만 넣을 수 있다는 것을 뜻한다. 만약에 지다가 이기는 경우가 생기면 사이클이 생긴거니 그 원소는 넣을 수 있는 가능성이 없고, 그 외에는 S1의 어떤 원소 뒤, 어떤 원소 앞에 넣을 수 있는 가능성이 생긴다.

각각의 원소를 넣는 것에서 사이클이 생기는 경우는 모두 제거했으니, 이제 원소들을 넣었을 때 사이클이 생기는 경우를 막아야 한다. S1의 각각의 원소에서 지고 이기는 것에 따라서 K+1개의 연속한 그룹이 생긴다. [s11한테 짐] s11 [s12한테 짐] s12 ... [전부 이김] 과 같이. 각각의 그룹에서는 모순이 생길 일이 없고, 중요한 것은 S1의 순서에서는 이기는데, 저러한 그룹 관계에서는 지는 형태의 사이클이 생기면 안된다는 것이다. 각각의 그룹의 인덱스를 매기면, G(i)를 i번이 속한 그룹이라 할때, i, j가 모두 속하고, i < j이며 G(i) > G(j) 인 경우가 없어야 한다. 즉 증가 수열을 찾아야 한다. 길이는 최대여야 한다. 바로 LIS!

LIS는 N^2에 동적 계획법으로 구할 수 있지만 느리다. 그리디 LIS를 쓸 수도 있을 텐데 난 익숙치 않아서 다르게 풀었다. 결국 G(i)의 경우의 수가 많아야 K+1개이니, 각각의 DP 값을 채울때 CurMax[i] = {G(i) == K인 dp[i] 중 최댓값} 을 O(K)에 lookup해서 O(NK)에 DP를 구할 수 있다. 세그트리 써서 LIS 푸는 것과 거의 똑같다. 구한 DP값을 역추적하면 문제를 풀 수 있고, 시간 복잡도는 최종적으로 2^K * NK + N^2 이다. 

Day 7

wsz

directed이면 min cut 문제이기 때문에 Dinic's Algorithm을 쓰면 되는... 줄 알았는데, 알고 보니 undirected였다. 이 때는 p를 연결하는 에지를 전부 지우면 포레스트가 되고, 트리 dp를 통해 여기서의 문제를 해결 가능하다. 귀찮으니 자세한 설명은 생략함.

트리 dp를 짰고 틀렸었다. 이유를 도저히 모르겠어서 보류했었는데, 알고보니 번역본에 있던 "no multiple edges"가 틀린 말이었다. multiple edges 들어오니 꼭 처리해주자.

zas

못 푸는 문제라고 생각하고 제꼈는데 pai보다 먼저 풀었다. 어렵게 생각하면 망하는 문제다...

다각형으로 접근하는 게 골때린다는 건 명확하니 다각형을 다루기 편한 형태로 쪼개서 따로 계산해야 한다. 여기서 쉽게 떠올릴 수 있는 것은 삼각분할이다. nlgn에 삼각분할을 하고 원 - 삼각형 교집합 크기를 계산하면 되는데... 둘 다 어렵다.

그런데, 삼각분할까지 해야지 꼭 다각형을 삼각형으로 쪼갤 수 있을까? 다각형의 넓이를 계산할 때를 생각해보면, 아무 점이나 잡고 단순히 ccw 값을 더하는 것만으로도 쉽게 전체 넓이를 계산할 수 있었다. 여기서도 똑같이 할 수 있다. 편의상 원의 중심을 (0, 0)이라고 할때, CCW(P_i, P_{i+1}) 이 0 이상이면 (0, 0) - P_i - P_{i+1} 을 잇는 삼각형과, 원의 교집합을 더하고, 0 이하면 빼면 된다. 

이제 원점을 포함하는 삼각형에서, 원점과의 거리가 R 이하인 점의 넓이를 세면 된다. 원점이라는 말이 잔뜩 붙은 덕에 계산이 그렇게 까다롭지 않다. P_i - P_{i+1} 을 잇는 선분과 원은 많아야 두번 교차한다. 이 교점을 구하고 (직선과 원의 교점) 각도에 따라서 삼각형의 넓이를 더하거나 원의 넓이를 더하면 된다. 

zoo

풀긴 풀었는데 조금 찝찝한 문제. 일단 평면 그래프에서 사용할 수 있는 몇가지 identity를 돌아보면

 * 평면 그래프에서는 E <= 3V

 * V - E + F = 컴포넌트 개수 (오일러 공식)

V는 입력으로 들어오니까 자명하고, E와 컴포넌트 수를 구해야 하는데, induced subgraph 역시 E <= 3V를 만족할 것이니 그냥 모든 간선들을 다 추려도 시간 초과가 나지 않는다. 간선을 전부 구할 수 있으면 F를 구할 수 있다.

간선을 전부 구하는 것이 문제인데 나는 조금 느린 방법을 사용했다. AC는 난다. 전체 정점의 합을 S라고 표현한다. 

 * 쿼리로 들어오는 정점 개수가 T개 이상이면, O(M) 루프를 돌려서 에지가 구해야 하는 집합 안에 있는지 판단한다. 이러한 쿼리는 많아야 S / T개니  (S / T) * M

 * 쿼리로 들어오는 정점 개수가 T개 미만이면, O(T^2) 루프를 돌려서, 집합 안에 있는 에지가 입력으로 주어졌는지 판단한다. 그냥 이진 탐색 하면 느려서... 놀랍게도 unordered set을 사용한다. 각각의 쿼리의 수행 시간을 합치면 S * T

SM/T + ST >= Ssqrt(M) 이다. T = 500으로 잡으면 AC가 뜬다. 시간 제한이 맥스 데이터만 10초고 나머지는 1~4초인데 도대체 뭐가 의도인지 잘 모르겠다. 이것보다 빠른 솔루션이 있는데 데이터가 약한 거일수도 있음.