2020 한국 정보 올림피아드 2차 결과 및 후기

내 인생 처음이자 마지막 KOI 본선... 준비를 좀 덜 했다고 하더라도, 실력이 좀 줄었다고 하더라도 안할 수는 없었다. 나름 역대 koi 2차 문제들을 3개 빼고 다 풀기도 하는 등, 열심히 준비를 했다. 긴장되는 마음가짐을 최대한 억누르려고 했고, 나에게 크게 중요한 대회는 아니라는 마인드 컨트롤을 하였다.

사전 준비

대회는 1시 30분에 시작이었고, 1시부터 준비할 수 있는 시간을 가졌다. 그런데 키보드가 너무 불편했다. 내 노트북 키보드가 굉장히 특이한 형태인데, 그 키보드에 익숙해져버려서, 다른 키보드에 손이 잘 안익게 되었다. 앞으로는 항상 키보드를 들고 다닐까 생각을 하고 있다. 아무튼 스페이스바가 아예 안되는 컴퓨터가 있어 옆 컴퓨터에서 시험을 보게 되었다. 
연습 문제는 예선 2교시 1번이었다. 15줄 정도의 짧은 코드를 짯는데, 아예 컴파일이 되지 않았다. 몇 번 다양한 코드로 시도를 해보니 bits 헤더가 작동을 안한다는 것을 깨달았다. 그렇게 30분이 다 지나갔고, 이에 대한 질문을 하였지만, 해결이 되지 않은 채로 대회가 시작되었다. 연습 제출도 해보지 못하고 굉장히 어수선한 상태로 bits 헤더도 못 쓰고 대회를 시작하였다. 시작하고 거의 바로 컴파일 환경을 c++14로 바꾸면 된다는 답변을 받았다. 다행히 작동하였다.

문제 1

일단 입력이 문자열이라서 순간적으로 숨이 턱막혔다. 하지만, 1번이었기 때문에 차라리 1번에 문자열이 나온것이 다행이라고 생각했다. 문제를 보니 lower_bound를 쓰면 가볍게 해결될 문제였다. 최근에 블로그에 헷갈려 했던 STL 문법을 싹 정리해놨기 때문에 무리 없이 문제를 풀 수 있었다. 하지만, 키보드가 안 익숙했기 때문에 평소만큼의 코딩속도는 나오지 않았다. 약 10분이 조금 넘어서 풀 수 있었다.

이후 Timeline

문제 2 고민

가벼운 마음으로 문제 2번을 열었다... 되게 간단하게 해결할 수 있는 관찰이 중요한 문제 같았다. ... ... ???? 왜? 도대체 왜? 풀이가 생각이 나지 않을까... 순간적으로 확 당황했다. koi 2번에서? 맨처음에는 증가 감소가 꺾이는 횟수/2 로 가볍게 풀 수 있는 문제인줄 알았다. 그런데 그렇게 짜니까 {1,2}와 {2,1}을 구분할 수 없었다. 그래서 맨 처음에 증가하는 것과 감소하는 것에 차이를 두어 보기도 했지만, 문제를 해결할 수 없었다. 여기서 꽤 당황을 했던 것 같다. 그래서 마구잡이로, 답이 2 이하일 것이다. 0또는 1일 것이다 등의 말도 안되는 추측을 하다가 결국 포기를 했다.

문제 3 구경

문제 3을 열었다... ... 좌표 평면. 점들. 눈 앞이 아찔해졌다. 3은 내가 풀기 보다는 긁을 곳이라고 생각했다. 화장실을 가면서 k=2에 대한 풀이를 생각해놓고, 파라메트릭을 염두에 두었고, 금광 세그 같은 스위핑 + 세그를 염두에 두었다. 염두에만 두고 넘어갔다.

문제 4 고민

4번 문제에 대한 첫인상은 꽤나 괜찮았다. 수, 관찰, ! 자료구조 같은 느낌이었다. 문제를 보면서 바로 소소한 이득도 보았다. 몇 가지 관찰을 했었다.
1. 내가 완벽히 지나가는 구간의 i번째 카메라의 위치는 대충 (2*i-1)*r 정도이다. 
이게 무슨 말이냐 하면 첫 카메라는 무조건 0~r 사이에 있어야 한다. 만약 로봇이 r 이상까지 가게 된다면 첫 카메라는 무조건 r에 위치하게 될 것이라는 것이다. 직관적으로 카메라는 0~r 사이중 r에 있을 때가 가장 이득이다. 따라서 r 이하에 첫 카메라가 있다면 r까지 옮기지 않을 이유가 없다. 또한 첫 카메라가 r이후에 위치해 있으면, r까지만 땡겨오는 것이 이득이다.
2. 1의 과정을 통해 현재 r에 있다면, 1개가 줄어든 새 문제를 푸는 것과 같다. 따랏 하나씩 점진적으로 해결해 나갈 수 있다.
3. 가장 오른쪽에 있는 현재 감시가 안된 위치가 존재하면, 거기까지만 이동하면 된다.

1번은 정말 확실했고, 이에 따른 풀이가 나와서 코딩을 시작했지만, 갑자기 싸한 느낌이 들었다. 지금까지 그냥 풀이를 빠르게 완성하고 검토도 안하다가 예제만 나오고 제출했더니 틀려서, 다시 돌아가기에는 이미 먼길을 걷고 대회를 말아먹은 적이 한두번이 아니었다. 또한, 4번치고는 너무 빠르게 관찰이 되었다. 그래서 내 풀이를 검토해보았다.

2번이 맞다는 소리는 무조건 앞에서부터 하나씩만 옮기면 끝나는 것인데, 그러면 한 번에 여러개를 가지고 돌아오는 경우에 반례가 생긴다. 이는 3번에도 비슷하게 해당하는 반례이다. 즉, 매순간 카메라 하나를 옮기고 다음 것을 볼지, 다음 것과 합쳐서 볼지 선택을 해야한다고 생각했다. 그래서 dp느낌이어야 한다고 생각했고, 원래의 풀이가 틀렸다고 생각했기 때문에 포기하였다. 

문제 2 복귀

다시 문제 2로 돌아왔다. 하지만 풀이의 아이디어가 떠오르지 않았고 초조해졌다. 그래서 문제를 다시 읽다보니 ai<=2 인 서브테스크가 존재했다. 그리고나서 바로 나의 주특기인 모든 경우를 손으로 적기 시작했다. 답이 꺽이는 횟수에 대해 0,1,2,2,3,3 과 같이 나오는 것을 보고, 맨 앞부분 처리와 +-1 처리를 제대로 안해줬기 때문에 틀렸다고 생각했다. 그리고 제출후 WA...
코드를 아무리 봐도 틀린 곳은 없었고, 멘탈을 붙잡고 더 해본결과 0,1,2,2,3,3,3,3이라는 것을 깨달았다. 거듭제곱꼴로 늘어나는 것을 알게되었고 바로 ac를 맞을 수 있었다.

문제 3 긁기

4번은 긁기에 좋은 문제는 아닌 것 같아 3번을 잡았다. 문제 3에 대해서 계속 생각해봤지만, 스위핑+세그를 어떻게 해야할 지 모르겠고, 파라메트릭이 계속해서 머릿속에 떠올랐다. 그래서 내가 생각한 풀이는 임의의 두 점을 이용해서 정사각형의 아랫변과 왼쪽변을 잡고, 정사각형의 한 변의 길이에 대해서 파라메트릭을 해서, 최솟값을 찾아내는 것이었다. 어렵지 않게 뚝딱 짜냈고, 내가 목표한 N<=600에 똑딱 떨어졌다... 왜? 애초에 상수도 1/a 의 느낌으로 굉장히 작게 붙기도 하고, 시간도 5초나 된다. 
나는 열이 받았고, 12점이 굉장히 중요하다고 생각했다. 그래서 커팅을 하기 시작했다. 굉장히 다양한 방법으로 제출을 20번 정도 더하였고, 모두 실패했다... 그제서야 정신을 차렸다. K=2를 고민하기 시작했고, 아까 생각했던 방법이 갑자기 떠오르지 않는다는 것을 깨달았다. 내 정신상태를 탓하며, 스위핑 + 세그를 쓰면 풀 수 있다는 것을 깨닫고, 구현을 시작했다. 많이 해본 구현이라 별로 어렵지 않게 맞을 수 있었다.
남은 시간은 20분. k=50 x,y<=2500 짜리 풀이는 k=2 풀이에서 조금만 바꿔서 세그 대신에 prefix sum을 쓰면 풀 수 있다는 것을 깨달았다. 구현을 했지만, 내가 구현한 코드는 예제에 대한 정답만을 내는 코드였고, 점수를 얻는 코드는 아니었다. 그렇게 내 처음이자 마지막 koi가 마무리 되었다.

복기

그렇게 나쁘지는 않았지만, 굉장히 만족스럽지 못한 점수였다. 최소 235, 혹은 247 아니면 3xx를 받을만한 시험이었다. 여러가지 선택의 길이 있었고, 이를 되짚어보려고 한다. 

if I pick 4

이번 셋은 4번이 확실히 3번보다 쉬운 셋이었다. 심지어 4번이 3번보다 나한테 훨씬 더 잘 맞는 문제였다. 심지어 4번은 관찰도 좀 되었었다. 실제로 끝나고 다른 친구말로는 나라면 4번 풀이를 30분이면 충분히 떠올릴 것이라고 했다. 그래서 내가 생각했던것들을 말했더니 대충 맞다고 했다... 흠... 만약 4번을 잡았으면 진짜로 300+a 혹은 200 이었을 것이라고 생각한다. 

하지만 1,2 를 푼 시점에서 4를 바로 가는 것은 말도 안된다고 생각한다. 리스크가 좀 있었고, 3에서 어느정도 점수를 받아두고 있었다. 근데 그 3에서 만족스러운 점수를 얻지 못했고, 계속 몰두를 하게 되어 그 이후로 4를 보지 못했다. 이를 해결하기 위해서는 내가 이런것들을 했어야 한다. 
1. 2번을 뇌절을 덜하고 빨리 풀기.
2. N<=600의 테케를 버리고 빠르게 넘어가기.

이랬으면 적어도 나에게 4번을 고민할 시간 1시간 30분~2시간이 주어졌을 것 같다. 그렇게 생각하면 4를 못 풀 문제는 아닐 수도 있다.

이번에 문제점이 하나 나왔다고 생각한다. 감은 좋지만 풀이를 완성시키는 디테일이 없다. 문제를 어떻게 풀어야 할 것 같다는 추측. 뭐를 쓸 것 같다는 추측. 혹은 중요한 관찰. 이런것들을 얻는 능력은 꽤나 좋다고 생각한다. 하지만, 이 내용이 풀이로 완성되지가 않는다. 이를 무시하거나, 틀렸다고 생각하거나, 다른길로 빠진다. 이런 경우가 아니더라도 기본적으로 풀이를 깔끔하게 마무리시키는 능력이 부족한 것 같다. 내가 만약 4를 봤으면 어땠을지도 궁금하다. 

마인드

그리고 마인드 자체도, 굉장히 안정적으로 하려고 했다. 4번을 내가 풀 거라고는 생각을 안했고 애초에 2개를 푼 직후 긁겠다는 마음가짐이 굉장히 강했다. 주로 은 컷은 230 정도에서 결정이 났기 때문에 금상은 너무 적었고, 안정적으로 은상을 타고 싶었다. 그리고 4번은 긁기에는 좋은 문제가 아니었다.

내 목표는 3번에서 47을 맞아놓고 4로 넘어가는 것이었다. 내 계획을 생각해보면 그냥 23에서 시간이 전체적으로 많이 끌린 것이 문제였던 것 같다. 

결과

그래도 최악의 결과와 미친듯한 뇌절은 하지 않아 다행히 은상을 수상할 수 있었다. 최근에 실력이 좀 감소해서 걱정이었는데, 아무튼 다행이었다. 위에서 계속 아쉽다고 말했지만, 그것은 복기니까 내가 못한점을 집으려고 그런것이다. 사실 내 실력에 비해서는 잘 안나왔지만, 결국 은상을 탔다는 것은 변하지 않는다. 이제는 더 큰 무대를 향해 달려보자!