A
c를 max로 두고 확인
B
정렬하고 하나하나 확인
C
ans[q[i]] = q[p[i]];
D
각각마다 cnt 배열 저장하고 하나 고정하고 다른거 보면서 자기 내부만 훑으면 되는데 처음에 map으로 cnt 관리해서 TLE+1
E
떨어진 컴포넌트끼리 합쳐주면 되는데 반드시 남는 간선이 있는 컴포넌트가 존재하므로 그 간선이랑 연결 안된 다른 정점 아무거나 이어주면 된다. 이 후보를 잘 관리하면 되는데 small to large 쓰면 끝. 구현 미스로 WA+1
F
거꾸로 보면서 위치를 맞춰나간다고 생각하면 세그 + 이분탐색 국밥. O(Nlog^2N)인데 펜윅쓰면 개빠름
여기까지 패널티 2개 먹긴 했지만 30분 안에 풀어서 기분이 좋았다. 그런데 슼보에 G를 너무 많이 풀었길래 봤다.
G
누가봐도 FFT 기본문제다;;;
굳이 G에 이런 문제를 냈어야 했나? 잘 모르겠다.
G가 이렇게 많이 풀린 것도 (나는) 처음 보는 것 같다. 근데 웰노운인 것 치고도 너무 많이 풀렸는데..
암튼 딴소리로 이걸 늦게 푼 이유에 대해 설명하겠다. 나는 기본 include랑 macro 빼고는 최대한 코드 복붙을 하지 않으려고 노력하는 편이다. 어차피 오프라인이나 중요한 대회에서는 내가 직접 짜야하기 때문이다. 그래서 코포나 앳코더에서도 코드 복붙은 거의 하지 않았다. 그런데 FFT인걸 알았는데 나는 FFT를 짜본 적이 없다.. 그럼 템플릿을 써야 하는데 이걸 진짜 써도 되는 걸까에 5분 정도 고민했다.
그리고 내린 결론은, "앳코더니까 ACL만 쓰자" 였다. 뭐 이건 대놓고 사이트 내에서 쓰라고 있는거니까..
그래서 대충 convolution 구현체 보고 컴파일 없이 구현했더니 CE가 떴고, 좀 고쳐서 내니까 WA가 떴다.
detail을 누르니까 예제도 틀렸다. 그 이유를 모르겠어서 그냥 ACL을 깔기로 했다.
그렇게 앳코더 라이브러리 까는법 찾는데에 10분 정도, 깔고 컴파일하려는데 오류생겨서 조금 더 쓰고 결국 고쳐서 30분 정도만에 AC를 받았다.
이럴 줄 알았으면 ACL 한번 깔아둘걸..
아니 아무리 생각해봐도 이걸 왜 냈는지 잘 모르겠다. 진짜 그냥 사전지식 문제인데..? 평소 G 정도 난이도였으면 2300 후반~2400은 나왔을 것 같은데 좀 아쉽다. 하지만 코포에서 당하는 억까에 비하면 이정도는 뭐.. 넘어가자.
