2024 ICPC Seoul Regional First Round 후기

이번에 KimsaiAn 팀명으로 ICPC에 참여해보았습니다.

저희 팀은 E,F,H 이렇게 총 3 문제를 풀었는데, 어떻게 풀었는지 풀어본 순서대로 복기해보려 합니다.

E : 행렬 게임
처음에 어떤 문제가 쉬울지 감이 안 오다가 스코어보드에서 E번을 다들 풀기에 저희도 풀어보았습니다.
서두르느라 수식이 안 보였지만, a와 b 행렬의 값 차이의 절댓값은 칸 별로 미리 계산할 수 있어보였습니다.
그러면, 각 열 별로 a와 b 행렬의 값 차이가 제일 큰 값들도 미리 찾을 수 있겠죠?

미리 각 열 j 별로 |a[i][j] - b[i][j]| 가 제일 큰 i 위치들을 구하던지 아니면 |a[i][j] - b[i][j]| 값들을 저장해둡시다.
그리고 M개에 대해서 미리 계산을 해둔 값들로 더해주면 됩니다.

총 시간복잡도 : O(N^2 + M)

H : 숫자 할당 (2 WA)
이 문제는 13! 가지의 경우에 수가 있을 텐데 어떻게 0.1초 내로 풀어야 할 지 감이 안 왔습니다.
13! = 6,227,020,800 이니깐 적어도 1분은 걸릴 것이라고 예측되니 이에 따른 경우의 수를 줄여야 합니다.

처음에는 13! 전부 계산 시켜보았습니다. 당연히 TLE가 나왔습니다.
조금 경우의 수를 줄여보니, a,b,c,e,f,g,i,j만 있으면 l,m,k,d,h 값은 A,B,C,D,E,F,G,H 값들을 통해서 정할 수 있음을 파악했습니다.
그런데 이래도 13P8 = 51,891,840가지의 경우의 수가 생겨서 TLE를 받았습니다.

좀 더 생각해보니, a,b,c,e,f,i 6개를 미리 구하면 다음과 같이 나머지 수들을 구할 수 있습니다.

d = E - (a+b+c)
l = A - (a+e+i)
h = D - d
m = H - l
g = F - (e+f+h)
j = B - (b+f+m)
k = C - (c+g) = G - (i+j)

그래서 13P6 = 1,235,520 가지의 경우의 수로 줄일 수 있었고 각 경우의 수 별로 d,l,h,m,g,j,k 들이 양수이며 서로 겹치는 값이 없는지 확인해주면 되었습니다.
또한, C - (c+g) == G - (i+j) 도 고려해주기도 했었습니다.
아이디어도 아이디어지만, 구현도 상당히 귀찮았던 문제였습니다.

총 시간복잡도 : 사실상 O(13^6) // 중간에 continue 같은 걸로 커팅도 하긴 했지만, 매우 크게는 이렇게 볼 수 있을 것 같아요.

F : 채굴권 분할 (5 WA)
다음으로 많이들 푼 문제가 F번인데... 사실 기하 문제는 너무 싫어서 포기할 까 생각했었습니다.

중간에 수식을 잘못세운 경우들과 생각을 좀 잘못해서 여러번 틀렸는데, 저희 팀 최종 아이디어는 두 점을 가로지르는 직선의 개수가 짝수면 YES 아니면 NO를 출력하기로 하였습니다.

이후에 직선 수식을 cos, sin을 활용해서 세웠어야 했는데, 거기서 계속 틀렸었고... 직선 위에 있는지 아래 있는지 판단하는 기준도 잘못 짜서 틀렸고... 그러다가 맞았습니다.

총 시간복잡도 : O(N)

총평 : 이번에 ICPC 예선 난이도는 작년에 비해 훨씬 어려웠던 것 같습니다. 
A, K번이 비교적 쉬웠다는 후기를 듣긴 했는데... K번은 4장을 읽을 시간과 마음의 여유가 없었고, A번은 거의 많이들 안 풀어서 읽을 여유가 없었습니다.
좀 더 여유를 가지고 대회에 임했었으면 성적이 더 좋았을 것 같은데 아쉬움이 들면서도 재밌었습니다.