2023 SCPC 2차 예선 후기 + 본선 진출 컷 분석

총점 : 100/200/90/180/60 = 630 [본선 진출]

 

<세 줄 요약>

1. 동아리의 아주 중요한 일정과 겹쳐 대회를 정상적으로 치지 못했다.

2. 1/2번이 쉬웠고 4/5번의 최대 서브태스크가 자명이었는데, 3번과 4번의 점수에 따라 갈릴 것 같다.

3. 본선 진출 컷은 630점 또는 585점의 상위권 어딘가 될 확률이 높다. [실제로 585에서도 본선 진출 소식이 들려왔다]

 

이 블로그에 게시글이 올라오는 빈도가 줄어든 것으로도 알 수 있듯이, 대학 진학 후 PS를 거의 손에서 놨다. 친구들과 많이 놀러다니기도 하고, 동아리 활동도 열심히 하면서 세상에서 제일 한가하다는 새내기의 삶을 맘껏 체험했다. 그럼에도 PS는 앞으로 과외를 위해서라도 아예 놓을 수는 없었고, SCPC와 같이 상금이 큰 대회를 위해서라도 놓지 않는 것이 이득이었다. 하지만 안타깝게도, 동아리 필수 일정이 15시-21시로 잡혀서 대회에 제대로 참여할 수 있는 시간은 절반 남짓이었다. 본선은 당연히 갈거라고 생각했는데, 자칫하면 본선 진출이 위험해진 상황이 된 것이다. 그래도 주어진 환경에서는 최선을 다해 풀었다고 자부할 수 있고, 컷 분석을 해본 결과 본선에 진출할 확률이 진출하지 못할 확률보다는 높은 것 같다. 우선 컷 분석을 하기 전, 문제 요약 및 나의 접근 과정, 풀이를 소개하자면 다음과 같다.

 

1. 타이젠 윷놀이 : 보자마자 한숨을 내쉬었다. 더 쉽게 접근했으면 좋았을텐데 이 문제에서 1시간이나 허비했다.

우선 이동과 관련해서 변수가 너무 많기 때문에, 각 시점에서 말이 새로 출발했을 때 1바퀴를 도는 시점을 찾아 모두 저장했다. 말 하나가 1바퀴를 도는 데에는 최대 19번이 걸리기 때문에 시간복잡도도 안전했는데, 문제는 그 다음이었다. 이를 가지고 시간복잡도에 로그를 붙여, 스파스테이블 느낌으로 내리려고 했는데 log(N*M)이 33이었고 TC가 87개여서 33*87*10만이 TLE가 났다. 도대체 어떤 대회에서 TC 개수를 시간복잡도에 고려해야하는지는 모르겠으나 아무튼 그렇게 됐다... 결국 N*M이 1e10이니 이 값의 루트가 1e5라는 점을 이용해 스파스테이블을 절반만 만들었고, 1e5번 전진하는 동안 N*M의 이동횟수를 모두 사용했다면, 그 범위 안에서 파라메트릭을 실행하는 것을 1<<16번 반복했더니 풀렸다. 즉, 1번 문제를 스파스 + 루트질 + 파라메트릭으로 풀었고 제출횟수도 6번이었어서 이미 멘탈이 어느 정도 갈린 상태였다.

** 당연히 이 문제의 의도 풀이는 이렇게 더럽지 않다. 그냥 이동에 관련된 큰 배열을 하나 노가다로 만들어서 푸는게 제일 깔끔한 풀이였던 것 같다. 백도가 없었던 것을 감사하게 생각하고 있다.

 

2. 괄호 문자열 : 문자열 혐오증이 있지만, 그래도 SCPC에서 자주 출제되는 문자열이 3번이 아닌 2번에 나온 것에 안심했다.

실제로 문제 자체는 어렵지 않았고, 1번보다 빨리 푼 것 같다. 가장 중요한 관찰은 열린괄호와 닫힌 괄호의 쌍이 정해져있다는 점이었고, 이를 stack을 이용해서 O(N)에 구해준다음 이웃해있는 괄호들끼리만 경우의 수를 늘려주면 되는 문제였다. 저 관찰이 마냥 쉽지는 않아서 생각보다 100솔이 나오는 데에 오래 걸렸고, 나도 구현에서 이상한 짓을 많이 해서 7번이나 제출하였다.

 

3. 루머 : 본선 진출에 갈림길이 되었던 문제이다. 81솔이 나왔는데, 난이도에 빗대어 생각하면 상당히 많이 풀렸다고 말할 수 있다.

서브태스크의 점수 분포는 45점/90점/180점/300점이었다. 순서대로 나이브 / N^3 / N^2logN / N^2을 요구하는 서브태스크인데, 누군가가 N^3, N^4으로도 풀태를 뚫었다는 소문도 들었다. 솔직하게 말하면 3번을 풀고 나머지 문제에서 자명한 서브태스크를 긁으면 진출할 수 있을 것이라고 생각해서 풀태를 시도했고, 풀태가 어렵지 않게 떠올랐다. 우선 어떤 사람이 감염자면 그 사람이 T초 후에 어디까지 영향을 미칠 수 있는지는 정해져있었다. 귀가 얇지 않은 사람, 즉 A[i]=2인 점들이 마치 벽처럼 작용하기 때문이었다. 따라서 사람이 아니라 구간으로 접근했고, dp[i][j]를 j번째 구간까지 i개의 구간을 사용하여 덮을 수 있는 부분의 최대 길이로 놓은 후 O(1)에 갱신해주면 되는 문제였다. dp[i][j]를 갱신할 때에는 총 3가지를 갱신해주면 되었는데, 1번째는 앞선 구간과 벽을 끼고 벽까지 감염시키는 경우였다. 이는 dp2[i][j]를 i개의 구간을 사용하여 j번째 위치를 끝으로 하며 벽을 잠재적으로 감염시킬 수 있는 상황에서 덮을 수 있는 부분의 최대 길이로 놓은 후 스위핑해주면 시간복잡도의 소모 없이 구할 수 있었다. 2번째는 벽과 관계없이 현재 관찰하는 구간과 겹치지 않게 앞 구간을 선택하는 경우였고, 이는 dp3[i][j]를 dp[i][1]~dp[i][j]의 최댓값으로 저장하면 쉽게 해결되었다. 3번째는 현재 관찰하는 구간과 겹치게 앞 구간을 선택하는 경우였는데, 이 경우는 덱dp를 사용해주면 구할 수 있다고 한다. 나는 boj.kr/11003과 같은 덱dp 문제들을 풀어본 적이 없어서 여기서 세그를 썼고, 180점을 노리는 풀이를 작성했다. 동아리 일정 중간중간에 틈틈이 코드를 작성하여 완성했으나 당연히 집중 안되는 환경에서 작성한 코드가 한 번에 돌아갈리가 없었고, 디버깅을 하는 도중 시간이 끝날 것 같아서 갱신을 O(N)에 하는 dp로 안전하게 수정하여 90점만을 획득하였다. 동아리 활동 없이 편한 환경에서 코딩했다면 180점 이상은 받았을 것 같다. 이 문제도 제출을 8번이나 하였다.

 

4. 막대기 연결 : 전체 풀이는 모르겠고 최대 서브태스크인 180점 풀이는 자명했다.

B[i][j]를 i번째 막대기와 j번째 막대기로 만들 수 있는 사다리꼴의 넓이의 2배로 저장해놓고, C[i][j]를 B[i][i] ~ B[j][j] 사각형에 있는 최솟값으로 저장해둔 다음에 풀면 O(N^2)에 안전하게 해결할 수 있다.

 

5. 스마트 아파트 건설 : 문제가 기억도 안나는데 시간복잡도 O(N!)에 next_permutation을 이용해 나이브를 구현하면 최대 서브태스크인 60점을 얻을 수 있었던 것으로 기억한다.

 

< 컷 분석 >

모든 컷 분석의 근거는 이 통계이다. 우선 1번과 2번은 만점을 받아야 본선 진출이 가능한 것이 당연하고, 나머지 3문제에서 사람들이 평균적으로 어느 정도의 서브태스크를 긁었는지가 중요하다.

 

우선 4번은 0점을 x명, 40점을 y명, 180점을 z명, 400점을 9명으로 놓고 방정식을 세우면 x+y+z=180, 2y+9z=1191이 된다. 2y+9z=1191의 디오판토스 방정식을 풀면 아래와 같이 나온다. 가장 윗줄은 입력이고 왼쪽이 y, 오른쪽이 z인데 y+z<=180이기 때문에 적어도 119명 이상은 180점을 받은 것으로 추측된다. 아마 0점이 1명 밖에 없지는 않을 것이기 때문에 180점을 받은 사람은 120명 대일 것 같다. 만점자까지 합치면 130~140명 사이인데, 본선 진출 인원이 130명 정도인 것으로 예측했을 때 여기서 180점을 받았다면 진출 확률이 매우 높아진다. 180점의 하위 섭테가 40점이기 때문에 3번에서 받은 점수보다 4번에서 받은 점수가 더 크게 작용할 것으로 생각된다.

5번은 점수가 0점 60점 400점 뿐이라 계산하기 쉽다. 60점을 받은 사람은 154명이고, 워낙 쉬웠기 때문에 당락에는 영향을 미치지 못했을 것으로 보인다.

 

마지막으로 3번은 점수가 너무 다양해서 방정식을 풀기보다는, 만점을 제외한 평균을 구하는 것이 더 의미가 있을 것이다. 만점을 제외하면 평균이 51점 정도로, 90점을 받았다면 진출하기 쉽다. 아마 180점을 받았다면 300점도 받았을 확률이 높아서 3번 90점 + 4번 180점이면 안전하게 붙을 것 같다. 약간 문제가 되는 것은 3번 45점 + 4번 180점인데, 이 점수도 상위권까지는 잘하면 붙을 것 같다.

 

그런데 이번 본선이 온라인이라는 소문도 있고 애초에 인원이 유동적이라서 내가 운영진이라면 제출 페널티를 가지고 컷을 자를 것 같지는 않아서, 깔끔하게 630점 또는 585점이 컷이 될 것 같다. 아직 결과가 나온 것은 아니니 본선에 가기를 기도해야겠다.