2022 KOI 2차 대회 후기

7월 16일에 봤었던 대회인데 대회 끝나고 노느라 지금 후기를 올린다..

고3이라서 이번이 마지막 KOI였는데 실력은 크게 늘진 않은 것 같아서 1, 2번 풀고 3, 4에서 부분점수 50점정도 긁어 은상 턱걸이를 하자는게 목표였다.
하지만 대회가 시작되고, 1번을 보니 어려웠다. 문제를 읽고 대충 생각나는 풀이를 짜서 내보니 시간초과가 나서 망했구나 싶었다. 그게 내 최선의 풀이라고 생각했었기 때문이다.
혹시 몰라서 '난이도순이 아닌가'라는 희망을 품고 문제들을 다 읽어보기로 했다. 2번도 어려워보였다. 3번은 조금 쉬워보였는데 막상 풀이를 생각하려니 어렵구나 싶었다. 4번은 문제가 뭔 소리인지 도무지 이해할 수 없었다. 그래서 난이도순이 맞는 것 같다고 생각하고 1번으로 돌아와 풀이를 다시 생각해 보았다.

1번은 방향을 완전히 잘못 잡았었던 것 같다. 다시 차분히 생각해보니 쉽게 만점 풀이가 떠올랐고, 구현해서 1시간 조금 넘었을 때 100점을 받았다. 트리가 주어진다는 것을 충분히 활용하지 않고 생각을 해서 이런 일이 벌어진 것 같다. 임의의 노드(1로 했다.)를 루트로 잡고 트리를 그려서 어느 번호가 연속하는지, 불연속하는지를 파악하기 위해 가장 아래에 있는 노드부터 자신의 부모노드와의 연결만 확인하는 방법으로 해결해줬다. 아마 시간복잡도는 O(Q * k log k) 정도인 것 같다. (쿼리마다 주어지는 노드들을 높이순으로 정렬해야 함)

2번도 처음엔 어려워 보였지만 사전순으로 가장 빠른 것을 출력해야 한다는 것을 이용하면 쉽게 풀 수 있었다. 앞에서부터 수를 배열한 뒤, 그 배열이 가능한지를 판단해주면 그리디하게 풀 수 있다. 판단하는 방법은 같은 음식을 파는 식당끼리 묶어 그룹을 만들었을 때, 가장 크기가 큰 그룹 사이사이에 다른 그룹을 끼어넣어 배열을 할 수 있을지를 판단하면 된다. 따라서 가장 크기가 큰 그룹의 크기가 나머지 그룹의 크기의 합보다 2이상 크면 배열이 불가능한 것이다. 이 관찰을 하면 이를 빠르게 계산해주기만 하면 된다. 나는 세그먼트 트리를 이용해 그룹의 크기를 관리해주었다. 그리고 같은 그룹이 연속하지 않도록 잘 처리해줘야 하는데, 처음에는 우선순위 큐를 이용해 관리해주려고 했지만 단순히 포인터를 하나 더 쓰는 것으로 시간도 단축할 수 있었다. 2번도 한시간 정도 걸렸던 것 같다. 구현이 조금 빡세서 중간에 한번 날리고 정리해서 다시짜긴 했는데 그러길 잘한것 같다.

3번은 평소 3번과 비교했을 때 쉽게 나온 것 같다. 아니면 내 풀이가 정해가 아니거나..
문제를 읽었을 때부터 결정문제로 풀 수 있을 것 같은 느낌이 들었다. 그래서 '목표값'을 설정하고, 문제의 규칙을 만족하는 내에서 그 목표값에 최대한 근접하기 위해 필요한 값을 계산해 합한 값이 음수가 아니면서 0에 최대한 가까워지도록 하는 목표값을 이분탐색으로 찾았다. 마지막으로, 찾은 목표값을 이용해 배열의 최종 형태를 계산해 출력했다. 이게 될까하면서 짠거라 100점이 나왔을 때는 뭔가 잘못된게 아닐까, 이게 코포인가, 꿈을 꾸고 있나, 플래 플래 플래 루비로 냈나 등등 온갖 생각이 들었다(그리고 그 우려는 현실이 되었다! 2022.09.16 기준 P5 P4 P1 R5). 300점이라니..이미 목표를 넘어가 있었고 부분점수에 따라 대상~은상이 갈리는 지점에 도달한 것이었다. 3번은 30분 조금 넘게 걸려서 대회는 1시간 40분 가량이 남아있었다.

4번은 문제가 길고 중간에 무슨 관찰을 하면 좋다같은 의도를 알기 어려운 말도 있어서 문제 읽는 데 시간을 많이 썼다. 처음에 시간에 쫓기며 문제를 읽었을 때는 내용이 머리에서 정리가 전혀 안돼서 아예 이해를 못했었지만 3번까지를 다 맞고 나니 마음이 편해져서 차분히 읽을 수 있었다. 예제에 있는 그림을 보니 이해가 쉬웠다. 아마 3번까지 중에 하나라도 만점이 아니었으면 4번 문제를 이해할 수 없었을 것 같다. 문제를 이해못해서 4번을 버린 사람들도 꽤 있지 않을까 싶다.
4번은 부분점수만 긁어야겠다고 생각했기 때문에 처음부터 부분점수를 꼼꼼히 봤다. 출제자도 300점이 많이 나올것이라고 예상했는지 4번 부분점수가 세세히 나눠져 있었다.
점수가 낮은 5점부터 봤는데 그냥 트리에서 두 점 연결하는 최단경로 구해달라는 거라서 LCA를 짰다. 버그를 많이 만들어서 printf 디버깅하고 하느라 좀 오래걸렸던 것 같다. 맞고 나니 30분 좀 넘게 남았던 것 같다.
그 다음으로는 이런저런 생각하다 15점짜리 부분점수가 5점이랑 비슷해서 풀이가 떠올랐다. 아까 5점 코드에 각 노드에서 말단노드로 가는 최솟값도 구해서 u->LCA + v->LCA인 경로와 u->말단 + v->말단 경로를 비교해주면 끝났다. 이게 한 20분정도 남았을 때 생각나서 살짝 급하게 구현하고 점수 뜨는거 보고나니 7분정도 남아서 그냥 조금 더 생각하다가 제출기록이나 구경하고 다녔다.

이렇게 320점으로 마쳤는데, 이번 문제가 쉬웠던 건지 잘 풀려서 다행이었고, 고등부에서도 300점을 넘어봐서 행복했다. 고등학교 올라오고 나서는 예전만큼 점수가 안 나왔었는데 마지막 대회에서 목표를 달성하고 초, 중, 고 다 300점을 넘어보는 버킷리스트를 해내서 만족스럽다. 문제가 쉬웠던 것 같아 아마 은상을 받을 것 같긴 하다.

---

가채점 결과가 나왔다.

만족스럽다.

---

다른 사람들 후기보니 4번 20점이 자랑은 아니라는 생각이 든다. 비유하자면 수능에서 수학 98점 받는 짓한것 같다.
6점 풀이는 다익스트라로 쉽게 풀리고 8점 풀이도 6점 풀이에 외곽선으로 도는 것만 추가하면 되는데...
8점 풀이가 6점+외곽선인거야 알고 있었지만 6점짜리가 생각이 안나서 못풀었었다. 근데 이게 너무 어이없다. 왜 다익스트라를 생각을 못했지??ㅋㅋㅋㅋ 5점 풀이에 너무 갇혀있었던 것 같다. 원래 부분점수 긁을 때는 부분점수 하나하나 다 새로운 문제라고 생각해야 되는데 300점을 맞고 긴장이 풀렸던 건지 충분히 잘했다고 생각한건지 끝까지 집중하지 못한 것 같다. 근데 뭐 334점이었어도 어차피 시간 밀려서 금상은 못 받았을 것 같다. 시간 부족해서 구현을 다 못했을지도 모르고.
근데 생각해보니 8점 풀이가 만점 풀이의 핵심 아이디어를 주는게 아닐까 싶다. 아직 정확한 만점 풀이도 모르고, 험난한 과정 후에 만점에 도달할 수 있겠지만 8점이 1번 노드를 거치는 것과 안 거치는 것으로 문제를 나눠 푼다는 것에서 센트로이드를 떠올릴 수 있지 않을까 싶다.

근데 1시간 40분동안 대체 뭘했길래 20점밖에 못 긁은걸까? 앞서 말한것처럼 긴장풀리고 어쩌고저쩌고해서 조금 느긋하게 문제를 풀었던 것 같긴 하다. 그리고 문제 이해하는게 너무 어려웠다. 한 10분~20분 정도??는 문제 이해에 쓰지 않았을까 싶다.
그 다음으로는 LCA에서 구현이 망해버렸다. 코드를 실컷 짜놨는데 답이 안나와서 LCA 테이블부터 출력해가면서 체크하고 응애응애했는데 거리 더하는 거에서 순서 잘못해서 답이 이상하게 나오는 거였더라..
5점 받고나서는 부분점수를 조금 생각하다가 잘 모르겠어서 2번 풀이에 대한 증명으로 돌아갔다. 이게 대회중에 할짓인가 싶긴 하지만 예전부터 크고작은 사건들을 터트려왔던 KOI였기에 혹시 시스템이 잘못됐거나 데이터가 잘못돼서 나중에 더 추가한다거나 하는게 아닐까라는 생각이 들었기 때문에 불안했다. 2번이 포인터 하나 더 쓰는 부분이 별 생각없이 일단 이렇게 해보고 안되면 pq써야지 했던거라 의심쩍은 부분이 있었다. 그래서 증명을 마치고 4번으로 돌아왔고, 거의 바로 15점 섭태 풀이가 생각나서 후다닥 구현했던 것이다. 물론 버그는 언제나 우리와 함께한다.
사실 대회보기 전부터 세웠던 계획에는 집중이 끊기는 순간이 1~2번쯤 올 것이라는 것이 고려되어 있었다. 이게 대회 짬밥인지 뭔진 몰라도 4시간 반이라는 긴 시간동안 계속 집중하고 있기는 아무래도 힘들고, 문제를 풀다보면 멘탈이 나가는 것도 충분히 가능한 일이기 때문이다. 과거의 나를 떠올려보면 집중이 끊기는 순간에 딴생각을 하거나 대회 끝나면 뭐뭐해야지라거나 후기쓸때 뭐뭐 써야겠다 등의 시간이 길어지는 망상으로 빠지는 경우가 꽤 있었다. 그래서 이번에는 이것을 방지하기 위해 집중이 끊기면 제출기록이나 보면서 머리를 비워야겠다는 계획을 세웠었다. 0점인 상태면 오히려 멘탈이 나가겠지만...그럼 뭐 문제라도 읽든가 해야겠지 뭐... 4번에서 집중이 끊기는 순간이 왔고, 이 방법을 사용해봤는데 확실이 다시 집중상태로 돌아오는 데 시간은 적게 걸렸던 것 같지만 이게 KOI에 대한 불신을 키운 것 같기도 하다. 실행시간도 0.2초 막 이래서 큰 데이터가 없나싶은 생각도 많이 들었고 3번은 평소보다 너무 쉬웠던 것 같아 중등부로 잘못 들어온게 아닌지 확인까지 했을 정도다. 그치만 풀이에 대한 증명을 하는게 정상이니까 순서가 바뀌었을 뿐이지 쓸데없는 데에다가 시간을 썼다고는 생각하지 않는다. 결과가 좋아서 그런지 모든 행위가 긍정적으로 보이는 것 같긴 하다.

아 처음에 대회가 시작했을때 새로고침했더니 로그인 화면으로 돌아가서 로그인부터 하고 돌아왔다. 수험번호야 외우고 있었고 비번은 적어놔서 다행이었다. 나는 이제 KOI에 참가하는 일이 없겠지만...새로고침을 할때 조심하도록 하자. 이게 아니라 비번이랑 줌 회의실이랑 비상연락처 다 잘 적어두자. 줌 튕긴다거나 문제가 안뜬다거나 하는 일들이 좀 있는 모양이다. 온라인...아무래도 걱정이 많이 될 수밖에 없는 것 같다.

그리고 이번에도 어김없이 대회가 끝난 후 머리가 아팠다. 자세 조심하자. 다음부터는 집중이 끊겼을 땐 스트레칭이나 해야되나 싶다.

풀이와 상관없는 얘기로 글이 꽤 길어졌는데 누가 읽긴 할지, 읽어도 도움이 되는 글인지 잘 모르겠다. 그냥 기대이상의 결과와 시험 끝+KOI 끝이 만들어낸 조금 한가한 삶이 자꾸 이 글에 뭔가를 덧붙이게 만드는 것 같다.