ABC Small Large 풀었다. AB는 쉬웠고, C는 로직은 찾았는데 코딩도 까다로웠고 디버깅에 한참을 썼다. 원래는 D도 깔짝거릴 예정이었는데 C를 푸는데 너무 오래 걸리는 바람에 졸려서 그냥 잤다.
그나저나 이번 C는 디스크립션을 약 한 사발 마시고 쓴 듯 하다. Dijkstra의 ijk와 사원수를 이용한 너드스러운 말장난이 나왔는데 읽는 순간 감탄했다 ㅋㅋㅋ 알고리즘 시험에서 Dijijstra라고 썼는데 사원수로 ijij = ijk니까 맞게 해 달라고 우기는 식(…) 우길 수 있는지 없는지를 판단하는 프로그램을 짜는 문제였다.
이번에 반성할 점은 같은 로직을 좀 더 쉽고 빠르고 정확하게 코드로 표현하는 능력을 길러야겠다는 점. 다른 사람들의 C 풀이를 보니 착안한 아이디어는 똑같은데 내 코드가 지나치게 복잡하다고 느꼈다. 실제로 C에서 2번 오답을 제출했고, 푸는데 시간도 굉장히 오래 걸렸음.
오랜만에 코드포스를 쳤다. 그리고 오랜만에 블로그 업데이트도 한다. SNS에 글 올리기가 쉽다보니 SNS를 많이 쓰는데, 요즘 긴 글을 쓰는 연습을 하기 위해 블로그에 글을 쓸 필요성을 느낀다.
크리스마스날 새벽부터 코딩을 하고 있는데 아무 생각이 없다. 작년까지만 해도 뭔가 설레는 마음이 있었던 것 같은데 1년동안 무슨 일이 있었던 걸까.
이번에 레이팅이 Dynamic하게 매겨졌기 때문에 A부터 어려울 수 있겠다는 생각을 했고, 실제로 열어보고 ‘아 기하구나’라고 생각하고 던지고 B를 봤다. 하지만 B는 수학이었고 CDE를 읽기 전에 A로 회귀했다. 자세히 보니 기하는 기하인데 영역을 나누고 그래프를 만드는 대신 간단하게 직선으로 나눠진 영역에서 위치만 확인하면 풀 수 있어서 금방 코딩을 했다. #
그 다음에는 C를 잡았다. 처음에 이분 그래프 조건을 보고 이분 매칭을 위주로 생각을 시작했다. 수들을 이루고 있는 모든 소인수들을 독립적으로 분해해서 생각하는 아이디어를 기본으로 풀이를 진행시켰다. 처음에는 매칭으로 접근했는데 두 쌍 사이에 연결되는 매칭 수가 1이 아닐 수 있어서 플로우로 풀이를 변경해서 맞았다. 시간제한 있는 대회에서 플로우 써 보는건 처음인데 책을 참고해서 짰다. 스스로 좀 더 빨리 짤 수 있게 공부를 더 해야 할 듯. #
C를 풀었을 때 한 시간 정도 남았고 D를 잡았다. D에서 23456의 LCM을 계산해보니 60밖에 안 되서, 60 q log n이 얼마정도 되나 확인해봤더니 시간 내에 나올 것으로 예상되었다. 인덱스 트리를 이용해 코딩을 했는데 보통 bottom-up 방식으로 올라오면서 처리하는데 이건 순서가 중요하기 때문에 오른쪽에서는 올라올 수 없어서 쿼리문 처리를 독특하게 짰다. 대회 때는 못 풀었는데 끝나고 나서 디버깅 도움을 받아 바로 AC를 받았다. 코딩 다 했는데 알고보니 나머지 연산 처리를 한 번 빼먹었다 ㅠㅠ #
KOI 이후로 문제 풀이를 거의 손을 놓고 있었기 때문에 결과를 별로 기대하지 않고 본 시험이었다. 이번 시험을 계기로 문제 풀이를 다시 시작해 ACM-ICPC를 대비하는 계기가 되지 않을까 하는 마음을 가지고 대회를 시작했다. 문제를 보고 느낀 점은 다행히 생각하는 능력은 많이 줄어들지 않았다는 점이다. A, C, D 모두 보자마자 바로 감을 잡고 풀기 시작했다. 하지만 코딩을 한 지 오래되기도 했고 마지막으로 코딩하고 키보드도 바뀌어서 코딩 속도는 꽤나 줄어들었다.
고등학교 때 국대를 못했던 대신 ACM-ICPC 월파를 바라고 공부하고 있다. 실제로 열심히 준비할 수 있을지 어떨지는 학기가 시작해 봐야 확실해질 것으로 보이지만 우선은 할 수 있는 일을 하면서 최선을 다하자!
선발고사 때도 그랬듯이 당일날보다 그 다음날 후유증이 더 큰 듯 ㅠㅠ
어제 KOI 3번을 대회장에서 못 푼게 아쉬워서 같은 유형의 문제인 APIO Sequence를 짜 봤다. 몇 번 오답을 제출하기는 했는데 전부 다 0 원소 처리 제대로 안 해서 그랬으니까 모든 원소가 양수였던 대회장에서 짰던 CHT는 맞았을 것이고, 결국 점화식 부분에서 계산실수만 있었던 것 같다.
수학에서는 전체적인 과정을 찾아내면 단순한 계산 실수가 있어도 대부분의 점수를 받는데 정올에서는 과정을 다 알아도 단순한 계산 실수가 있으면 0점이다. 학문간의 성격이나 특징에 차이가 있고 참가자한테 일일이 코드가 무슨 의미를 가지는지 물어볼 수도 없으니 이해는 하지만 참 아쉬운 점이라고 생각한다.
어제 KOI를 마지막으로 대학생 전에 참가할 수 있는 프로그래밍 대회는 전부 끝났다. 경기과학고등학교에 입학할 당시에만 해도 국가대표나 KOI 금상 이상 둘 중 하나는 당연히 할 수 있을거라 생각했는데 KOI 은상 세 개라는 평범한 성적으로 고등학교 학창시절을 마감하게 되었다.
선발고사도 그렇고 KOI도 그렇고 지금 느끼는 아쉬움 중 가장 큰 부분은 내 실력만큼의 성과를 거두지 못했다는 점이다. 내가 풀 수 있는 문제를 다 풀고서 받은 결과가 은상이라면 결과에 만족했겠지만, 그렇지 않아서 안타깝다. 남들한테는 잘난척이나 부심이라고 보일 수도 있겠지만, 작년도 그렇고 이번도 그렇고 충분히 금상 이상의 성적을 거둘 수 있는 실력이었는데도 은상을 받았다.
뭐 남들한테 인정 받으려고 공부하는 것도 아니고, 상을 못 받았다고 해서 있던 내 지식이 없어지는 건 아니지만 역시 아쉽기는 하다. 선발고사도 1차 때 잘 봤는데 2차 때 망하고, APIO도 1점 차이로 세계 동탑을 받았고, 작년이랑 이번 KOI는 문제 다 풀어놓고 사소한 실수를 못 찾아서 은상을 받았다. 전부 한 걸음을 남기고 안타깝게 실패한 경험들이었다.
내 인생은 아직 반도 지나지 않았고 아직 기회들은 많이 남아 있다. 그리고 꾸준히 공부하면서 실력을 갈고 닦는다면 남아 있는 기회들 중 내가 잡을 수 있는 기회가 언젠가는 찾아올 것이다. 하지만 그것은 어른이 된 뒤의 경험이고, 학창시절의 경험과는 다른 의미를 지닌다고 생각한다. 그렇기 때문에 정말 마지막이었던 이번 결과에 평소보다 더 미련이 남는 것 같다.
지금까지 그래왔듯이 며칠 지나면 금방 또 셀프디스하고 웃고 떠드는 추억이 되겠지만, 아직까지는 안타까운 마음이 큰 것 같다. 이제 진짜 다 끝났으니까 입시공부나 해야지 헤헤.
최종적으로 200점을 받았다. 처음 목표가 2, 3번을 풀고 1번을 긁는 것이었는데 목표는 달성해서 만족스럽다.
처음에 3번을 잡았는데, 아무리 생각해도 인덱스 트리로 log N번 연산하는 방법밖에 떠오르지 않아서 말렸다. 다른 방법을 생각하려고 해도 너무 졸려서 아무런 생각이 안 나서 잠깐 자고 일어났다.
다행히 자고 일어나니까 컨디션이 괜찮아져서 다시 풀기 시작했다. 3번을 좀 더 잡고 있다가 2번으로 갈아탔다. 2번은 풀릴 것 같은 풀이가 금방 생각나기는 했는데 예외 케이스가 있을 것 같다는 생각 때문에 풀이 검증에 시간이 걸렸다. 의사 코드로 표현하면 다음과 같고, 실제로는 리넘버링 및 인덱스 트리를 써서 구현했다.
3번은 생각을 뒤집어서, ‘이런 연산 결과를 어떻게 구할 수 있을까’가 아니라 ‘쿼리에서 한 번만 연산을 할 수 있다고 할 때 어떻게 할 것인가’로 생각을 바꾸었더니 금방 떠올랐다. 기준점들을 잡아서 기준점 좌우의 연산값을 저장해 놓은 뒤, 쿼리가 들어오면 쿼리 구간에 포함되는 기준점을 찾아 저장된 값을 이용해 합치면 되겠다는 생각을 했다.
이제 이러한 기준점들을 어떻게 잡아야 효율적으로 Init 함수에서의 쿼리 횟수를 줄일 수 있을 것인지를 생각하면 되는데, 이진 탐색의 중심점들을 이용하면 된다. 코드는 다음과 같다.
2, 3번을 다 풀고 나니 30분쯤 남았는데 1번이 기하에 output only라 제대로 건드려보지 못하고 끝났다. 그래도 나쁘지는 않았다고 생각한다.
ps. Round 1 2위는 하츠네 미쿠(8tusne 39)였다. 나는 이 분의 정체를 안다 ㅋㅋㅋ
