서론
군인의 신분이지만 외출을 나가 UCPC 대회를 진행하고 왔다!
부대 안에서의 알고리즘 대회는 나가봤지만, 이렇게 전국적인 알고리즘 대회는 처음 나가는 거라 걱정을 많이했다.
같이 나간 사람들은 학과 동기(znfnfns0365)와 비슷한 학과를 다니는 지인(jnary)과 나갔다.
다들 최근에 알고리즘을 많이 하지 않았기에 진짜 경험만을 목적으로 나갔다.
과거 문제 유형을 살펴보니 평균 골드 상위에 다이아까지 난이도가 분포해있었다.
문제 유형도 DFS, BFS, 이분 탐색 이쪽보다는 수학, 애드혹, 기하 등이 더 자주 나오는 것 같았다.
세 명의 목표는 모두 1문제만 풀어보자였다.
대회중
jnary가 앞쪽
znfnfns0365가 가운데
내가 뒤쪽을 푸는 걸로 정하고 대회에 들어갔다.
난이도가 높은 문제들이 가득했기에 쉬운 문제를 찾는 게 더 중요하다고 생각이 들었다.
맡은 4개의 문제들을 쭉 살펴보고,
문제의 알고리즘과 난이도들을 임의로 정한 뒤에 문제 풀이에 들어갔다!
처음에 본 건 I. 민들레 문제였는데 간단한 구현문제 같길래 엥??? 이러다가 x의 범위가 -10^9 ~ 10^9 인걸 보고 아 역시나...라는 생각이 들었다.
메모리 제한을 어떻게 풀어나갈지 생각이 안 났기에 다음 문제로 넘어갔다.
그 다음으로 본 건 대회내내 1시간 반 정도를 투자한 J. 동전 쌍 뒤집기이다.
알고리즘만 파악하고 나면 쉽게 풀 것 같아서 계속 잡은 문제이다.
하지만, 계속해서 반례를 찾지 못했고 결국 znfnfns0365에게 토스하고 다음 문제로 넘어갔다.
후일담으로 들어보니 분할정복을 하면 됐을것 같다고...
마지막으로 본 건 C. 미어캣 문제이다.
방향별로 정렬한 뒤에 쉽게 푸는 문제인줄 알았는데 아니었다.
여러 번의 틀렸습니다를 제출하다 보니 결국 시간이 종료되었다.
결과를 보니 jnary가 푼 A 문제와 znfnfns0365가 푼 E까지 해서 총 2솔에 성공했다.
물론 난 0솔...
D와 J도 거의 다 풀었는데 아쉽게 AC는 받지 못했다.
알고리즘 실력을 반성하게 되는 하루였던 것 같다.
문제 간단 회고
A - AC(Bronze 4, jnary가 잘 풀어주었다!) - jnary
B - 손대지 않음(?)
C - WA(Platinum 4, 정렬로 접근하였으나 브루트포스 였던 거 같다) - chosehoon2
D - WA(Gold 2, 트리와 정렬을 쓰는 문제인거 같다고 한다) - jnary
E - AC(Silver 1, 브루트포스) - znfnfns0365
F - 손대지 않음(Platinum 1)
G - 손대지 않음(Gold 2, 기하 문제를 풀 줄 아는 사람이 없었다..)
H - 손대지 않음(Gold 2)
I - 손대지 않음(Diamond 4, 변수의 범위가 -10^9 ~ 10^9인 걸 보고 바로 도망쳤다. 이건 참 잘한 선택이었다고 생각한다.) - chosehon2
J - WA(Gold 2, 간단한 애드혹 문제라고 생각했으나 반례를 떠올리지 못했다.) - chosehoon2
K - 손대지 않음(Platinum 3, 난해한 BFS 혹은 DFS라고 생각했으나 좌표평면이 무한좌표였다(???))
느낀 점
3시간이라는 긴 시간동안 알고리즘을 잡고 있으려니 자꾸 집중력이 흐트러지고 머리가 멍해졌다.
다음번에 비슷한 대회를 한다면 초콜릿을 챙기면 좋을 것 같다.
내년 알고리즘 대회는 경험이 아닌 본선진출을 목표로 열심히 달려봐야겠다....
최근 알고리즘에 소홀했던 나날들을 반성하고, 꾸준히 풀어나갈 것이다!