2020. 9. 27. 16:04ㆍProblem Solving/대회
문제 난이도는 솔브드 기준으로 1,2,3,4번 순서대로 브론즈 / 실버 / 골드 / 플레로 잘 배분된 것 같았습니다.
1번은 정사각형의 변 길이를 2 ~ $ min(N, M) $ 잡고 삼중 for 돌리면 됩니다.
시간 복잡도는 $ O(N^3) $ 가 됩니다.
2번은 투포인터 또는 분할 정복을 사용하면 됩니다.
비슷한 문제: https://www.acmicpc.net/problem/2003
3번은 $ M $번째 쓰레기가 어디서 태워지는지 알아야하는데, 대부분 최소 공배수로 접근한 것 같습나다.
그리고 대부분이 못 푼 것 같습니다.
TMI로 최소공배수를 사용한 접근 방법은 잘 모르겠으나 최소 공배수로 하면 소수(prime number)로 구성된 저격 테케를 만들면, 최소 공배수의 범위가 $ unsigned\ long\ long $ 을 넘을 수 있습니다.
$ M $번째 쓰레기가 태워진 시간을 알면, 그 시간에 대해서 완전 탐색을 하면 소각장의 위치와 태워진 갯수 모두를 알 수 있으니, $ M $번째 쓰레기가 태워진 시간을 먼저 알아야 합니다.
임의의 시간에 대해서 쓰레기의 갯수가 $ M $보다 크거나 작은지에 대한 결정 문제로 잡고 파라메트릭 서치를 사용합시다. (또한, $ t $가 증가할 수록 태운 쓰레기의 갯수도 높아지니 단조롭습니다.)
파라메트릭 서치를 돌려서 처음으로 쓰레기가 $ M $을 넘는 시간을 찾고 이 때 시간을 t라고 놓았을 때, $ t - 1 $일 때 쓰레기의 갯수가 $ M $ 미만임이 자명함으로 $ t - 1 $의 쓰레기 갯수부터 시작하여 시간이 $ t $일 때 직접 계산해서 $ M $번째 쓰레기를 구할 수 있습니다.
파라메트릭 서치의 시간복잡도가 $ O(NlogM) $ 이고, 직접 계산할 때의 시간복잡도는 $ O(N) $ 이므로 전체 시간 복잡도는 $ O(NlogM) $ 가 됩니다.
4번은 KOI 2016 2번 (고등부) 트리와 상당히 유사한 문제입니다.
Union Find의 경우 집합을 분리하는 경우가 어려운데 들어오는 query를 역순으로 처리하면 합쳐주는 것으로 쉽게 풀 수 있습니다.
이 풀이를 떠올리기는 쉽지 않았습니다. (저도 트리 문제는 그냥 풀이를 보고 풀었습니다.)
쿼리의 갯수가 $ M $개고 각 쿼리를 처리할 때 $ O(logN) $ 이 소요되므로 전체 시간 복잡도는 $ O(MlogN) $ 이 됩니다. (당연히 경로 압축 또는 Union by rank를 사용할 때)
다만, 한 번 풀면 접근하기도 상당히 쉬워지고 응용한 문제들이 꽤나 여러개 있는데 다 재밌으니 한번씩 풀어보는걸 추천합니다. (응용/변형한 문제 중에 가장 재밌는 문제라고 생각합니다: www.acmicpc.net/problem/17469)
비슷한 문제: www.acmicpc.net/problem/2843
3번 문제가 가장 재밌었던 것 같습니다.
4번은 비슷한 문제를 여러번 풀어봤던 것이 빠르게 솔브하는데 도움을 준 것 같습니다.