티스토리 뷰
국가대표가 된 기념으로 선발고사 후기를 써봅니다.
최종 성적: 1차 1위, 2차 3위, 종합 1위로 국가대표에 선발이 되었습니다.
이 글이 선발고사 전략을 세우는 데 도움이 되기를 바랍니다.
문제의 자세한 풀이는 나와있지 않지만, 약간의 스포는 있습니다.
전략: 시작 후 한 시간까지 문제를 읽으면서 긁을 수 있는 섭테나 풀 수 있는 문제를 파악한 뒤에, 이를 얻을 수 있는 점수가 큰 순서대로 짜는 것
1차 선발고사:
시작 후 1시간 정도: 모든 문제를 읽어 보았다.
1번: 최댓값이라 되어 있는 부분을 합으로 잘못 읽어서, 루트질로 뚫지 않으면 어렵다고 생각했다.
2번: 문제를 보자마자 구현이 쉽지 않다는 생각이 들었지만, 39점 풀이는 생각을 할 수 있었다.
3번: 여러 가지 경우의 수를 따져야 하는 매우 어려운 문제인 것 같았다.
4번: 슬로프 트릭으로 풀 수 있을 것 같았다.
그 뒤 30분:
이를 생각해 보니 4번을 푼 뒤 문제를 다시 한 번 읽어보고 1번이나 2번을 잡아야겠다는 전략을 세울 수 있었다. 그래서 4번을 풀었다. 구현은 그리 오래 걸리지 않았고, 1시간 반 정도에 AC를 맞을 수 있었다.
시작 후 2시간:
문제를 다시 읽어 보았고, 1번 문제가 합이 아니라 최댓값을 구하는 문제였다는 것을 발견했다. 답이 logN 이하라는 관찰을 한 후 풀이가 생각났고, 이거를 짜보기로 결정했다.
시작 후 3시간:
1번을 짰다. 짜는 데는 오래 걸리지 않았지만, 10번 정도를 틀리게 되었다. 너무 화나서 assert문과 비슷한 최적화를 했는데, 걸려서 오류 부분을 찾을 수 있었다. 오류를 찾은 뒤에는 오래 걸리지 않았고, AC를 받을 수 있었다.
시작 후 4시간:
2번과 3번을 다시 봤는데, 긁을 수 있는 최대 점수가 2번은 39점, 3번은 17점으로 보였다. 2번이 더 오래 걸릴 것 같았지만 2번을 긁기로 했다. 4시간 지점에서 2번 코드는 다 완성되지 않은 상황이였다.
끝나기 30분 전:
200점으로 끝나는 게 무서워서, 3번에서 10점을 미리 긁어두기로 했다. dnc 최적화를 사용한 풀이를 미리 생각해두고 있었고, 10분 내로 짤 수 있었다.
그 뒤에는 2번을 다시 짜게 되었다. 끝나기 30분 지점에서 2번 코드는 완성되었고, 디버깅도 후반부에 다다랐다.
마지막 30분:
2번 39점은 20분 정도 남기고 완성을 할 수 있었고, 그 뒤로는 3번 문제를 긁었다. 히스토그램에서 가장 큰 직사각형과 같은 1점 섭테를 긁었고, 비슷하게 풀 수 있는 3점 섭테를 긁다가 시간이 끝났다.
2차 선발고사:
시작 후 1시간 정도: 역시나 모든 문제를 읽어 보았다.
1번: 77점을 받을 수 있어 보였고, 100점도 좀만 생각하면 받을 수 있을 것 같았다.
2번: dp 식을 잘 세우면 76점을 받을 수 있지만, 못 세우면 5점밖에 받을 수 없어 보였다.
3번: 그리디 같아 보였지만, 아직 생각이 나지 않았다.
4번: 선분 교차가 있어서 싫어 보였고, 다항 시간 내에 풀기도 어려울 것 같았다.
그 뒤 30분:
국대가 되려면 1번과 3번을 풀어야 한다고 생각했고, 1번을 생각하는데 잡혀 있었다.
시작 후 2시간:
0점인 상황이 너무 오래 지속되서, 3번을 보기로 결정했다. 다행히도 그리디 풀이가 바로 생각이 났고, 100점을 맞을 수 있었다
시작 후 3시간 반:
1번을 1시간 동안 생각했는데 아이디어가 안 떠오르고 있었으면, 이제는 다른 문제를 봐야 할 것 같아서 2번을 봤다. 2번은 dp식을 세울 수 있냐에 따라서 70점이 결정나는 문제였고, 다행히 중복을 피하는 dp식을 세울 수 있었다. 구현이 꽤 복잡한 편이여서 40분 가까이 걸렸고, 3시간 반 시점에 76점을 맞을 수 있었다.
시작 후 4시간:
1번을 다시 생각해봤지만, 100점은 커녕 77점도 못 풀 것 같았다. 그래서 쉽게 긁을 수 있어 보였던 18점부터 받기로 결정했고, 금방 풀 수 있었다.
끝나기 40분 전:
18점을 긁은 후 1번을 또 다시 생각해봤지만, 생각이 나지 않아 포기하고 4번을 보러 갔다. 4번에서는 5점은 쉽게 긁을 수 있어 보였고, 13점도 가능해 보였다.
마지막 40분:
4번을 긁었다. 20분을 남겨두고 다 짤 수 있었고, 백트래킹의 최적화가 잘 돼서 N=36인 서브태스크(13점)까지 긁을 수 있었다. 그 뒤로는 N=100짜리를 긁으려다 실패했고, 그대로 끝났다.
예상 난이도:
1차 1번:플레 상위
1차 2번:39점은 플레 상위, 만점은 다이아 상위
1차 3번:11점은 플레 하위, 만점은 루비 하위
1차 4번:플레 중위
2차 1번:18점은 골드 상위, 만점은 다이아 중위
2차 2번:76점은 플레 상위, 만점은 다이아 중하위
2차 3번:플레 하위
2차 4번:13점은 플레 중위, 만점은 루비
교훈
이번 선발에서 알게 된 점은 다이아를 풀려고 한 문제만 잡는 것보다, 플래티넘 수준의 모든 문제를 풀면 안정적으로 국대가 될 수 있다는 것이였다. 앞으로도 이를 잊지 않고 실천하겠다.