210713 팀연습

대회 링크: https://codeforces.com/gym/102893

 

팀연습도 안하면 PS 절대 안 할 것 같아서 팀연습을 고등학생 시절에 대충 몇 번 했던 것 이후로 처음 해 봤다. 처음에는 정신 차리려고 매운맛 대회로 하려 했는데, 쫄아서 적당히 쉬워보이는 셋을 들고 왔다.

 

초반부: 09:00~10:30 (00:00~01:30)

 

ABCD/EFGH/IJKL로 문제를 분배해서 보기로 했다. retro3014가 ABCD, 내가 EFGH, gs18115가 IJKL을 맡았다.

 

F가 단순 조건문 문제임을 바로 발견했고, 00:04:52에 A AC가 나왔다. 그런데 내가 조건문 오타+복붙 실수까지 해 버리면서 브론즈 4따리 문제에 2틀을 박아버렸다.. 아무튼 00:07:12에 F AC를 받았다. 이후 EGH중 H는 정말 귀찮은 케이스 분석 문제로 보였고, G는 간단한 mcmf 문제로 보였다. 그래서 G를 잠시 고민해 봤는데 아니였다. 다시 보니 G는 그뭔씹 문제로 보였고, 그나마 E가 할만해 보여서 E를 잡았다.

 

이후 2틀을 또 적립하면서 00:19:28에 J AC가 나왔다. 그리고 30분 즈음에 내 E 풀이가 불완전하다는 것을 깨닫고 던졌다. 동시에 사용하면 안 되는 소파들끼리 간선을 이어 그래프를 만드는 풀이였는데, 결과적으로 접근 방식은 같지만 그래프의 형태에 대한 추측이 약간 틀렸었다. 나는 처음에 이분그래프라 생각했는데 코딩하면서 보니 생각하지 못했던 케이스가 있어서 던졌다. gs18115가 K를 해보라고 했는데, 문제를 읽어 보니 constructive라서 1초도 고민 안하고 걸렀고, I도 해보라 했는데 기하 인터렉티브라길래 또 걸렀다. 결국 귀찮아서 나중에 잡으려던 H로 넘어갔다. 대충 가능한 xx..x꼴 위치+x값을 잡고 경우의 수를 세면 될 것이라고 생각했다.

 

이후 00:34:03에 D AC가 나왔다. 48분 즈음에 gs18115가 L을 찍어봤지만 어림도 없었고, 이후 retro3014가 B를, gs18115가 C를 잡기로 했다. 나는 54분에 H 코딩을 끝냈지만 예제도 안나와서 디버깅해봤더니 정말 어림도 없는 풀이였다는 것을 깨달았다. 이후 BOJ 10802같은 DP를 이용해 주어진 범위 내의 수만 고려하는 식의 풀이가 가능해 보였고, 5차원 DP->4차원 DP->3차원 DP->4차원 DP로 무한으로 즐기면서 풀이를 만들어냈다. 그 사이에 각각 01:06:39에 B AC가, 01:08:07에 C AC가 나왔다. B는 3틀 하면서 조금 고통받은 것 같다.

 

이후 1시간 22분에 H를 냈지만 WA on test 3이 떴고, 풀이에 이어서 디버깅까지 무한으로 즐기기 시작했다. gs18115도 K에 적당히 믿음을 가지고 짠 코드를 계속 냈지만 계속 WA가 나왔다. 이후 함게 H 디버깅을 시작했다.

 

중반부: 10:30~11:30 (01:30~02:30)

 

retro3014가 L을 쭉 잡다가 던지고 G가 mcmf 아니냐고 했고, 내가 그럴 것 같았는데 잘 모르겠다고 했다. 11시 즈음에 내가 DP는 맞게 짜 놓고 멍청하게 테케 문제에서 초기화를 제대로 안 한 것을 깨달았다. 바로 고쳐서 내봤는데 TLE가 났다. DP 차원을 하나 줄여야 하나 생각했고, 꽤 당황했다. 비슷한 시점에 gs18115가 문제를 찾았는데, 이미 TLE를 받고 난 뒤였다. gs18115가 차원을 줄이는 대신 누적합+바텀업으로 짜라고 했는데, 누적합은 쓸 곳을 못 찾았고 바텀업으로 재귀를 없애고 낸 코드는 더 앞쪽 테케에서 TLE가 났다. 이후 long long을 int로 바꿨는데 같은 테케에서 TLE가 났다. 결국 차원을 줄여야겠다고 생각해 고민해봤는데, 생각보다 많이 어려웠다. 그러다 재귀 DP가 더 빨랐는데 바텀업 코드만 int로 바꿔서 냈다는 것이 생각이 났고, 혹시나 해서 재귀 DP 코드도 int로 바꿔서 내 봤는데 예상치 못한 AC가 나왔다. 02:17:25에 H AC.

 

gs18115가 I가 주어진 간선을 포함하는 triangulation을 찾으면 된다고 했는데, 그 시점에서는 잘 생각이 안 났다. 그런데 gs18115가 모든 triangulation의 간선 수가 같은 것 같다고 한 말을 보자 GCJ 2021 Round 3 문제가 불현듯 생각이 났다. 정확히 저 문구를 풀이에서 본 것이 기억이 났다. 대충 링크 던져주면서 3N-3-(컨벡스 헐 위 점 개수)임을 알려줬다. retro3014는 K를 잡기 시작했다.

 

이제 I는 그냥 계속 가능한 간선을 찾으면 된다는 결론이 나왔고, 내가 코딩을 하려 했는데 뇌정지가 와서 풀이를 O(N^4)에서 줄일 수가 없었다. K는 dfs tree와 bfs tree 얘기가 나왔는데, 문제만 읽고 전혀 고민을 안 해서 그 얘기가 왜 나오나 싶었다. 그리고 gs18115와 함께 I를 고민했는데, 둘 다 뇌정지를 벗어나지 못하고 O(N^4)에서 줄이질 못했다. 그러다 내가 O(N^3) 풀이가 생각이 났는데, 확실히 맞나 고민하다 뇌 속에서 O(N^4)라는 결론을 내려버렸다. 결과적으로는 O(N^3) 풀이가 맞았고, 다행히 2분 쯤 지난 2시간 27분 즈음에 K를 한 번 틀리고 온 gs18115가 같은 풀이를 뇌정지 없이 생각해내서 코딩을 시작했다. 나는 다시 E와 G를 고민해보기로 했다.

 

후반부: 11:30~12:38 (02:30~03:38)

 

I는 코딩은 복잡한 문제는 아니였고, 02:44:07에 I AC가 나왔다. 이후 gs18115와 retro3014는 L을 토론했는데, retro3014가 자신이 한 관찰들을 말해줬다. W/2 기준으로 물건을 나누는 것과, 가치/무게 순으로 정렬해서 그리디하게 하는 관찰을 말했는데, 풀이를 보면 알겠지만 여기까지 오면 다 온거다ㅋㅋㅋ 그 사실을 깨달은 gs18115가 L을 풀기로 했다.

 

나는 별개로 G를 잡고 있었는데, 온갖 플로우 그래프를 만들어보는 뇌정지 끝에 마음속에서 정해로 풀 수 없는 문제라고 결정하고 무지성 simplex 코드를 내 봤지만 어림도 없었다. 나중에 보니 simplex를 돌리되 integer 조건을 강제하기 위해 잘 재귀함수를 짜서 여러번 simplex를 돌리는 식으로 푼 팀들이 있었는데, 공부가 필요할 것 같다.

 

내 제출 후 약 1분 뒤인 02:55:13에 gs18115가 L AC를 받았다. 이후 E에 대해 잠시 토론을 했는데, retro3014가 플로우 아니냐고 했는데, 내가 n, m이 너무 크다고 했고, 내가 그래프를 만드는 식의 접근을 했다고 했다. 그런데 gs18115가 갑자기 풀이가 생각났다고 했다. 그런데 결과 출력을 위해 값을 바꾸는 방법을 처음에 생각하지 못했는데, 왼쪽 위부터 그냥 채우는 방식이 되냐고 물었는데 내가 된다고 했다. E 풀이가 완성됐고, gs18115는 E를 짜기 시작했다.

 

정신 차리고 보니 G는 모든 a_i값이 1이면 general weighted matching 문제랑 다를 게 없단 것을 깨달았다. 이 시점에서 플로우 쪽의 풀이는 아닐 것이라고 생각했다. 그리고 조금 더 고민해보니, 그냥 각 i마다 a_i 만큼의 정점을 만들어 주면 general weighted matching 문제가 된다는 것을 깨달았다. 더불어민규당 팀노트에서 열심히 베꼈고, 예제를 돌려봤는데 답이 나오지 않았다. minimum이 아닌 maximum을 구한 것이다. 그리고 무지성으로 모든 weight를 음수로 바꿨고, 당연히 0이 나왔다. 이후 뇌정지가 잠시 왔는데, matching의 크기가 항상 고정이라 모든 weight를 inf-weight로 바꾸면 된다는 것을 깨달았다. 이 부분까지 수정을 해서 제출했고, 03:16:57에 G AC를 받았다.

 

나는 E와 K 중 E는 풀이가 확실히 나온 것 같아서 K를 잡기로 했다. retro3014는 이미 K를 짜고 있는 중이었고, 나는 첫 WA 코드부터 보기 시작했다. 그러다 03:37:24에 E AC가 나왔다. 이제 K만 남았다고 생각하고 E 풀이에 대해 잠시 얘기하고 있었는데, retro3014가 K를 맞아왔다! 03:38:01에 K AC. 3컴의 힘으로 굉장히 빠른 시간에 올솔브를 할 수 있었다.

 

후기

 

예상보다는 뒷쪽 문제가 많이 어려웠다. 중반부에 고통을 굉장히 많이 받았는데, 중후반부에 어려운 문제들을 빠르게 해결해서 결과적으로는 올솔브를 할 수 있었다. 3컴 아니었으면 못했을지도 모르겠다. 또 올솔해서 기분은 좋지만 패널티 관리가 심각하게 안 됐다. 그것도 3컴으로.. 아무 생각 없이 제출하지 말자.

 

그와는 별개로 다 잘하는데 특히 자료구조를 매우 잘 하는 팀원(gs18115), 아이디어성 문제에 강한 팀원(Retro3014), 자료구조를 적당히 잘 하고 문자열/기하를 할 수 있고 이상한 사전지식들을 많이 아는 팀원(moonrabbit2)로 어느 정도 역할을 분배했었는데, 이상적으로 풀린다면 굉장히 안정적인 팀이라고 생각했다. 그리고 이번 대회에서는 이 분배에 굉장히 충실하게 따른 것 같고, 각자의 역할을 잘 해준 것 같아서 패널티와는 별개로 굉장히 기분이 좋다ㅎㅎ

 

다만 나는 F와 H에서 심각하게 트롤을 했고, G도 결국은 나는 G 풀이를 팀노트 없이는 짤 수 없는 굉장한 날먹 풀이로 짰고 팀원들이 충분히 생각할 만한 풀이라고 느껴서 개인적으론 못했다고 생각한다.

 

여담으로, G의 경우 공식 풀이는 지수 항이 들어가지만 mcmf만으로 해결했는데 풀이가 굉장히 재밌다. 한 번씩 읽어보는 것을 추천한다.