220520 팀 연습 (2018 Pacific Northwest Region Programming Contest)

셋은 https://www.acmicpc.net/category/detail/1976를 사용하였으며, 4시간 동안 진행하였다.

 

내가 A~D, slah007 선배가 E~I, qjatn0120 선배가 J~M을 잡고 시작했다.

 

~0:17

브~실 총 4문제를 1트만에 모두 밀었다.

 

~0:22

B는 깡수학이길래 넘겼고, C를 봤는데 Simple DP로 되길래 짜서 AC.

 

~0:57

B를 우리 중 이런 문제에 가장 강한 slah007 선배에게 넘기고 나는 D를 봤는데, D도 못 풀겠어서 선배들이 보던 문제중 F를 잡았다. F는 보자마자 그냥 XOR 세그+스위핑이란걸 깨달았다. 좌표 압축+누적합 등 처리해야 하는 부분이 꽤 있어 코딩 컴퓨터에서 나와있는 동안 구현을 대충 해놓았고, B AC가 뜨자마자 컴퓨터에 들어갔다.

 

~1:27

F를 열심히 구현해서 냈지만 WA가 떴고, 좌표압축 중 x와 y를 바꿔 쓴 부분이 있길래 고쳐서 AC를 맞았다.

 

~1:48

사실 B와 F보다 qjatn0120 선배의 K의 코딩이 먼저 시작되었는데, 왔다갔다 하다보니 AC는 가장 늦게 떴다. 문제는 더러운 DP인 것 같았다.

 

~1:55

D의 풀이를 생각한 slah007 선배가 AC를 띄웠다.

 

~1:59

K 코딩이 이루어지는 동안 H는 DP가 적당히 적게 돌 것이라는 믿음을 가지고 코딩하면 될 수도 있겠다는 사실을 알아냈고, 짜서 냈더니 AC를 받을 수 있었다.

 

~2:57

풀이는 보자마자 모두가 안 E의 코딩을 H AC 직후부터 시작했는데, 구현을 뭔가 잘못한 것인지 slah007 -> qjatn0120으로 코딩을 바꾼 후에야 맞을 수 있었다. 알고 보니, slah007 선배의 코딩은 n과 m만 바꾸면 맞는 코드였다.

 

~3:35

I와 M 풀이가 모두 있었지만 더 간단하다고 생각된 I를 먼저 코딩했는데, 틀렸다는 것을 깨닫고 바로 M으로 갈아탔다. M은 팀 노트라 생각하고 가져온 Convex Hull 코드를 변형시켜 쉽게 AC. 이 때 중간에 치킨을 받으러 가느라 10분 정도를 비웠다.

 

문제별 요약

A (B1, solved by leo020630) - 코포 A식 그리디 문제이다.

B (P1, solved by slah007) - slah007 선배가 비슷한 문제를 풀어보셨다 해서 드렸는데, 심지어 연습 끝나고 보니 선배 계정에 풀려있는 문제라고 하시더라. 문제 자체는 뫼비우스 반전 공식 기초 문제인 것 같다.

C (G4, solved by leo020630) - 주어진 배열을 개수로 묶은 후, \(DP[n][k]\)를 \(n\)번째 카드까지 \(k\)개 고른 경우의 수로 정의하면 쉽게 문제를 풀 수 있다.

D (P5, solved by slah007) - 애드혹 문제인 것 같은데..  모르겠다. 업솔빙 예정

E (P2, solved by qjatn0120) - 노잼 Flow 문제이다. 정점에 가중치가 들어간 그래프에서 Min Cut을 잘 구하면 되는데, 제한이 좀 커서 디닉을 써야 하는 것 같다. 

F (P2, solved by leo020630) - 스위핑+레이지로 직사각형의 합집합 면적을 구하는 기초 유형 문제이다. 이 문제는 XOR 세그트리를 사용해야 하는데, 구현이 크게 어렵지는 않다.

G (B2, solved by slah007) - 안 읽었다.

H (S2, solved by leo020630) - 적당히 빠르게 돌 것이라는 믿음을 가지고 풀면 되는데, 이게 실버인지는 잘 모르겠다. 아니면 다른 정해가 있나?

I (D4, Not solved) - \(O(nk)\) DP일 거라 생각하고 식을 세웠는데, 예제가 안나와서 포기했다. 티어를 보니 더 어려운 것 같다.

J (B3, solved by qjatn0120) - 안 읽었다.

K (P4, solved by qjatn0120) - 안 읽었다.

L (S5, solved by leo020630) - 스코어보드에서 다른 팀이 풀었길래 후다닥 가서 풀었다. \(O(N^2)\)에 주어진 조건을 확인해주면 된다.

M (D4, solved by leo020630) - 문제에서 주어지는 식을 잘 변형하면, Convex Hull 내부의 좌표들에 대해 \(xy\)의 값을 최대화하는 문제임을 알 수 있다. 이는 각 선분에 대해서 경우를 잘 나누어 확인하면 된다. 기여를 하러 들어갔는데 구사과님의 D5 기여가 딱 하나 있길래, D4로 기여했다. 이게 기하 문제임을 아는 과정이 쉽지만은 않은 것 같다.

 

느낀 점

컴퓨터 관리를 하는 규칙이 있어야 할 것 같다.

더 어려운 셋으로 연습해도 될 것 같다.