221003 팀 연습 (2022 KAIST ICPC Mock Competition)

공휴일에 좋은 대회가 있길래 팀 연습을 했다.

 

내가 뒤, slah007 선배가 앞, qjatn0120 선배가 가운데를 보고 시작했다. 세팅 문제 때문에 5분쯤 늦게 시작했다.

 

~0:32

slah007 선배는 D, 나는 J, qjatn0120 선배는 H를 봤다. 가장 먼저 코딩에 들어간 H를 27분에 AC받고, 쉬운 문제였던 D 역시 32분에 AC가 나왔다. 나는 J를 보다 어려워서 던진 후 많이 풀린 B로 넘어갔다. 

 

~1:08

B에서 끙끙대다 qjatn0120 선배가 핵심적인 관찰을 해 주셔서 바로 코딩에 들어갔다. 무지성으로 세그를 짠 뒤 mod 이슈로 한 번 틀린 후 B를 맞았다.

 

~2:27

이후 A, J, E의 코딩이 번갈아서 진행되었다. J는 사풀인걸 알지만 코딩이 짧아 qjatn0120 선배가 사풀을 몇 번 냈고, A는 맞는 풀이지만 구체화가 덜 되어 시간이 오래 걸렸다. E는 사풀이었지만 모른 채로 qjatn0120 선배가 코딩을 다 했고, 틀린 후에야 사풀임을 아셨다고 한다. 결국 A가 가장 먼저 맞으며 3솔에서 해방되었다.

 

~3:36

위의 과정 동안 난 혼자 M을 풀고 있었다. MCMF임은 자명하고, 모델링을 대충 해놓은 후 컴퓨터를 잡았는데 잡은 후에야 모델링이 틀렸다는 사실을 알았다. 모델링을 바꾸는 동안 선배 두 분은 J에 관한 토론을 하고 계셨고, 결국 J를 M보다 먼저 맞았다.

 

~5:00

M의 제대로 된 모델링을 찾았지만, 다 짜서 낸 결과 TLE를 받았다. MCMF가 잘못된 줄 알았지만 그건 아니었고, 내 구데기 모델링은 정점 개수가 \(7NM\)개 정도였는데 조금만 머리를 더 썼으면 이를 \(3NM\)까지 줄일 수 있었고, 이를 그대로 내 대회 후 AC를 받았다.

 

 

문제별 요약

A (D5, solved by slah007) : DP를 세그로 관리해주는 유형이라고 한다.

B (P5, solved by leo020630) : x좌표와 y좌표를 나눈 후, 스위핑해주면서 합을 구하면 된다. 나는 무지성으로 펜윅 두 개 썼는데, 없어도 된다는 것 같다.

C (R4, Not solved) : 문제를 읽지 않았다.

D (S1, solved by slah007) : 큰 수 처리에만 주의하며 경우를 잘 나누어주면 된다.

E (D4, Not solved) : 자세히 읽지 않았다.

F (D4, Not solved) : 문제를 읽지 않았다.

G (P3, Not solved) : 문제를 읽지 않았다. 업솔빙 예정

H (P5, solved by qjatn0120) : 잘 구현해주면 된다고 한다.

I (R3, Not solved) : 문제를 읽지 않았다.

J (D5, solved by qjatn0120) : 관찰이 중요한 게임 이론 문제이다. 나도 좀 오래 잡았었는데, 하나도 모르겠다. 업솔빙 예정

K (R4, Not solved) : 문제를 본 후 5분정도 생각하다 놓아주었다.

L (R5, Not solved) : 자세히 읽지 않았다.

M (P1, Upsolved by leo020630, slah007) : 전형적인 MCMF 문제이다. 각 칸별로 정점을 만든 후, 이어질 수 있는 정점에서 싱크로 가는 간선을 두 개 만들어주면 된다. 

 

느낀 점

맵다