(Virtual) Codeforces Round #574 (Div. 2) 후기

https://codeforces.com/contest/1195

Dashboard - Codeforces Round #574 (Div. 2) - Codeforces

스코어보드에 대조해 보니 대략 2070점 정도의 퍼포먼스로 보인다. 오늘 라운드도 어김없이 뇌절이 넘쳐났다. 전체적으로 실수가 좀 적었으면 좋겠다..

 

A: 처음부터 알고리즘은 맞았는데 n과 k헷갈려서 AC가 32분 늦어졌다. 그리고 33분 제출에서 test 17에 틀렸는데 이건 pretest에 없었기 때문에 내가 실제로 대회에 이대로 나갔으면 시스페일이였을 것이다...

 

B: 곱셈 오버플로우때문에 한번 틀리고 시간복잡도 문제인줄 알고 binary search로 다시 써서 맞췄다.

 

C: 간단한 DP.

 

D: 길이 X와 길이 Y의 숫자를 f에 넣을때 각 자릿수가 결과값에 얼마만큼을 공헌하는지를 쉽게 알 수 있다. 먼저 숫자들을 길이별로 모아놓고, 모든 길이 pair에 대해 상응하는 길이의 숫자를 넣었을 때 공헌하는 값을 구하면 된다. 종이에 노가다를 적당히 하면 나온다. 여기서는 모듈러가 998244353인데 1e9+7을 써놓고 20분동안 맞왜틀 시전..

 

E: 길이 n짜리 배열에서 모든 길이 k의 구간마다 최소값을 구하는 것은 deque로는 O(n), heap으로는 O(nlogk). 이걸 2차원에서 하면 된다. 나는 deque로 하는게 문제 풀 당시에 생각이 안나서 그냥 priority_queue를 썼는데, 로그를 얹었더니 시간초과가 난다고 한 사람도 있더라. 그리고 여기서도 (g_i*x+y)%z를 계산할 때 int로 계산해서 오버플로우가 나 한번 틀렸다..

 

F: 버추얼 도중엔 특별한 아이디어가 떠오르지 않았다. 기하 무서워..

 

풀이의 기본 아이디어 자체는 위키피디아에서 다 얻을 수 있는데, 이걸 쉽게 구현하는 방식이 꽤나 인상적이다. 우선 https://en.wikipedia.org/wiki/Minkowski_addition#Two_convex_polygons_in_the_plane  이걸 읽자. 요약하자면, 다각형의 Minkowski sum을 구할려면 변들을 polar angle순으로 merge하면 된다고 한다.

 

나는 저걸 읽고 다각형의 세그트리를 만들어 구간의 Minkowski sum을 저장해 놓고 쿼리마다 구간을 합치면 될 듯 하다! 라는 결론을 내고, 정직하게 polar angle을 계산하고 다각형의 변 중에 처음으로 polar angle이 0을 넘어서는 점을 찾고 두 다각형이 주어지면 그러한 점을 각각 찾은 후 거기서부터 변을 merge하는 식으로 constructive하게 Minkowski sum을 찾고 그걸 세그트리에 비벼넣는 코드를 작성하기 시작했다.

나는 내가 기하를 왜 싫어하는지 기억해냈고, 이런 코드를 쓸 수는 없다.. 고 생각했고, 다른 사람의 코드를 구경해 훨씬 간단한 풀이를 알아냈다. 

 

핵심은 실제로 Minkowski sum을 construct할 필요가 없고, Minkowski sum의 vertex개수만 적어내면 된다는 것이였다. 변 하나당 vertex하나가 될 것이며, 위에 말한 merge하는 과정에서 같은 방향의 변이 여러개 있다면 합쳐져서 vertex하나만 만들 것이다. 즉, 구간 내의 변의 distinct한 방향의 개수를 계산하면 되는 것이다. 길이 n짜리 array에서 q번 [l, r]구간의 distinct element count query는 웰노운(?) qlogn 오프라인 풀이가 존재한다.  https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/ 여기를 참고. 결국 기하 문제인데 기하적인 부분 거의 없이 AC 코드를 쓸 수 있었다. 그럼에도 불구하고 index헷갈려서 RTE한번 받았다

 

F번 요약: 정직하면 손해본다(??)