UCPC 2024 후기
2024 ucpc에 참가했다!
팀원 특징
Skile : PS 시작한지 제일 오래됐다. 한참 접었다가 최근에 다시 좀 하는중이다. 짬바에서 나오는 엄청난 든든함이 있다. 구현에 강하다. 그냥 전체적으로 다 잘한다.
Prime : 컴퓨터 관련 전공이 아닌데 비교적 최근에 나한테 영업당해서 PS를 시작했다. 고급 자료구조/알고리즘을 가장 많이 공부했다. 웰노운 문제에 강한 것 같다. 물리학 개고수라서 특정 주제의 고난이도 문제에 포텐셜을 가지고 있다. 단점: 코딩을 파이썬으로함
dongggle(나) : 코포식 능지문제 (애드혹, 그리디, 해구성하기..)에 비교적 강하다. 복잡한 자료구조/알고리즘 지식이 별로 없다. 기하문제 나오면 다른 팀원한테 던진다.
예선
예선은 나는 집에서, 나머지 두명은 카페에서 만나서 진행했다.
나는 A번(브론즈)랑 G번(꿀잼 그래프탐색) 풀고 J번 죽어라 고민하다가 못풀고 끝났다. 상당히 못했는데 팀원들 버스타서 27등으로 본선 진출에 성공했다. J번 어려웠는데 스코어보드 보니까 푼 팀이 너무 많아서 정말 충격적이었다...
본선
LG전자 서초r&d캠퍼스에서 오프라인으로 진행됐다.
도착하니까 모든 참가자 자리에 핑크빈 인형이 놓여있었다.
나는 A,D,G,J를 먼저 보기로 했다.
A를 좀 고민하다가 스코어보드를 보니 D가 가장 먼저 풀리기 시작하고 있었다. D가 쉬운 문제인걸로 추정이 됐는데 A를 풀고싶어서 Skile에게 D를 읽어보라고 떠넘겼다.
D를 읽더니 곧 코딩을 시작했고, 맞았다.
0:17:59 D AC
A를 풀었고, 맞았다.
0:44:53 A AC
팀원들이 L을 보면서 Hopcroft_Karp 팀노트에 안넣어서 인생 망했다, 디닉 안넣어서 인생 망했다, parity로 어쩌고저쩌고 하면 될것같다 등 얘기를 하더니 코드를 짜서 제출했고, 틀렸다.
0:58:32 L WA
문제가 좀 무섭게 생겼다는 코멘트와 함께 C를 넘겨받았다. 읽어보니 내가 자신있는 constructive 문제였다.
팀원들은 E를 같이 보면서 고민하고 있었다. "게임이론 문제니까 이거 동글 줘야된다" 이런 얘기가 들렸는데 못 들은척 하고 C를 계속 고민했다.
좀 헤맸는데 알고보니 별로 어려운 문제가 아니었고, 열심히 구현해서 맞았다.
1:49:07 C AC
C 코딩이 끝나갈때쯤 E 풀이도 나왔고, Prime이 컴퓨터를 넘겨받아 파이썬으로 E를 코딩했다. 파이썬이라서 살짝 불안했는데 다행히 맞았다.
2:06:13 E AC
M도 어느샌가 풀려있었다.
2:16:45 M WA
2:30:50 M AC
L 풀이를 전달받고 WA 코드를 보면서 내가 고민을 좀 하기로 했다. 이분매칭을 사용한 풀이는 아니었다. 판을 체스판처럼 칠한 다음 조각을 적당히 만들면 그 조각에서 흰색칸,검은색칸 중 적은 쪽의 개수 만큼 밤양갱을 만들 수 있다는 믿음을 가지고 만든 풀이였다. 그리고 그 믿음이 틀렸다는 사실을 발견했고, 이 문제는 이분매칭 문제가 맞다고 결론을 내렸다. 하지만 난 이분매칭을 못하기때문에 다시 Skile에게 문제를 떠넘겼다.
Skile이 L을 다시 풀었고, 시간초과가 안날지 반신반의 하면서 제출하더니 맞았다.
3:12:50 L AC
J번은 "대충 LCA같다" 까지만 생각하고 Prime에게 던졌다. 지금 생각해보니 초반에 두문제 푼 이후로는 내가 한 일이 문제 떠넘기기밖에 없는 것 같다.
Prime이 HLD아님? 이라는 말을 했고 팀노트에 HLD 안넣었는데 큰일났다고 생각했다. 근데 팀노트에 HLD도 없으면 대체 있는게 뭘까..
잠시 후에 Prime이 트리의 지름으로 어떻게 잘 하면 될 것 같다고 했고, 한참 고민하더니 대충 트리의 지름에다가 최대값세그트리를 올려서 정답 후보를 3개로 줄이는 식의 풀이를 만들어냈다. HLD나 LCA는 필요 없었다. 근데 구현할 자신이 없어서 Skile에게 풀이를 설명하고 구현을 떠넘겼다. Skile이 디버깅 코드 포함 4000B짜리 코드를 짰고 한번에 맞았다.
4:06:35 J AC
Skile이 J를 구현하는 동안 Prime과 둘이서 F를 고민했다. 평면그래프를 4가지 색으로 칠할 수 있다는 것은 매우 잘 알려진 사실이고, 문제 이름도 4색정리였다. 하지만 이 문제에는 엄청난 함정이 있는데, 문제에서 제시한 조건을 만족하는 평면그래프는 4색까지 필요 없고 3색이면 무조건 칠하는게 가능하다는 것이다. 아무튼 Prime이 대충 그리디하게 3가지 색으로 칠하는 풀이를 생각해냈다. 내가 구현을 열심히 했지만 구현 실수를 연발하다가 대회 시간이 끝났다...
22등으로 마무리했다.
스코어보드를 보니까 마지막에 내가 조금만 더 잘해서 F를 풀어냈다면 5등상 수상이 가능했다. 워낙 빡센 대회니까 수상 기대 없이 즐겜 하자는 마인드로 참가했는데 의외로 수상 코앞까지 갔다가 내 구현실력이 발목을 잡아서 놓치니까 아쉽다. 그래도 너무 너무 즐거웠다.
진짜 우리 팀원들이 너무 잘해서 무섭다.
저녁은 EN_SA님 팀과 함께 근처 중국집 가서 먹었다.