티스토리 뷰
2022.09.05:최초작성
2022.09.18:4등상 받았습니다!
전날까지 Suffix array등의 문자열 알고리즘들을 열심히 연습했는데 하나도 나오지 않았다. 온라인 대회에서는 이런 기조가 맞는 것 같다.
1번이 스위핑,2번이 dp였는데 내가 강한 유형의 문제가 나와서 어느정도 이득을 본 것 같다.
전날 9시에 잤는데 11시에 깨버렸다... 아침 8시에 겨우 다시 잠들었다가 11시 반에 일어나고 겨우 세팅을 했는데 컨디션이 굉장히 안 좋았다.
이런 대회에서 멘탈이 터져서 긁을 걸 다 못 긁고 망하는 경우가 꽤 많았어서 이번에는 문제를 모두 읽고 긁을 수 있는 걸 모두 다 긁기로 전략을 세웠다.
00:22 첫 문제부터 수식이 많아서 어질어질했다. 하지만 그다지 어려운 문제는 아니었고 누적합 비슷하게 생각한 뒤 변수분리를 잘 해서 풀면 된다. 실수문제이고 경계처리가 약간 까다로워서 코드를 제출할 때 조금 불안했는데 다행히 한 번에 맞았다. 1X번째로 맞았었고 괜찮은 출발이었다.
00:29 두 번째 문제를 읽어봤는데 $O(N^3)$은 골드급의 trivial한 dp였다. 빠르게 짜서 47점을 긁고 넘어갔다.
01:05 3번 문제는 내가 약한 constructive 문제였다... 일단은 패스하고 4번을 읽었다. 5번은 그냥 읽자마자 튀었다. 4번은 그냥 이렇게 하면 되지 않을까? 하고 적당한 가정을 한 $O(n \log n)$ 코드를 짜고 제출했지만 틀렸다. 조금 고쳐서 냈는데 또 틀렸다. 이 때 2번 만점자가 몇명씩 나오는 것을 확인하고 다시 2번을 보기로 했다.
01:26 2번은 왼쪽을 선택할지 오른쪽을 선택할지가 단조성을 띄기때문에 이분탐색등으로 나뉘는 위치를 찾고 prefix maximum등을 활용하면 적당한 $O(n^2 \log n)$ 풀이를 만들 수 있다. 제곱로그가 돌지 애매한 사이즈인데다가 경계처리도 헷갈렸지만 코드를 바로 제출했는데 다행히도 한 번에 맞았다. 이 때 2번 만점자가 10명대 초반이어서 최소 5등상은 받겠구나 생각했다. 그런데 이 때부터 긴장이 풀려서 그런지 몸이 너무 아파왔다... 두통도 심해지고 계속 기침이 나왔다.
01:58 다시 3번으로 돌아와 겨우 9점 풀이를 생각해내고 제출했는데 자꾸 0점이 나왔다. 혹시나 하고 if(x>100)return; 을 추가하니 9점이 나왔다...
02:16 4번 10점이라도 긁어야겠다 싶어서 비트마스크 dp를 열심히 짰다. 살짝 고생했지만 한 번에 10점이 나왔다.
03:07 다시 3번으로 돌아와 열심히 생각을 하고 코딩을 해서 38점을 받았다.
~04:00 이후로 3번과 4번을 계속 고민했지만 별 소득은 없었다. 섭태를 추가적으로 긁었으면 3등상도 노려볼만 했을 것 같은데 약간 아쉬웠다. 5번은 gradient descent 같은 걸로 비벼볼까 생각했는데 어떻게 할지도 잘 모르겠고 실수오차가 무서워서 시도조차 하지 않았다.
아마도 4등상을 받을 것 같은데 만족스러운 결과이다. 그동안 scpc수상을 계속 못해서 속상했었는데 정말 기쁘다 ㅎㅎ