SCPC 2022 1차예선 후기

다 풀었다.

총평

예년과 비슷한 정도의 난이도인 듯 하다. 사실 작년 1차예선이 유독 쉬웠던 거 같긴 하다..

올해 예선 문제는 예년에 비해 관찰과 아이디어 비중이 좀 컸던 것 같다. 보통 3~4번에 무지성 세그트리 문제가 하나쯤 있던데.. 풀면서 가장 재미있었던 문제는 4번인듯.

본선에는 제출 횟수 제한이 100번으로 사실상 없는데, 예선에는 왠지 모르게 10번이라는 조금 빡센 제한이 걸려 있다. 정신 놓고 몇 번 틀리다 보면 어느 순간 위험해질 정도. 예전에야 뭐 휴리스틱 부분점수 문제도 있고 했으니 제한이 빡센 편이 좋았겠지만, 이젠 좀 풀어줘도 될 듯 하다.

문제별 풀이

Github repository (https://github.com/kdh9949/snups-scpc2020/tree/master/code/8) 에 문제별 코드를 첨부하였다. ~2020년 예선 기출 풀이도 다 있으니 참고하면 좋다. 2021년 예선도 (1문제 빼고) 코드는 있는데 안 올려놨다. 안 귀찮을 때 올릴듯

1번

단조증가하도록 정렬을 일단 해야 하니, 같은 값을 들고 있는 개미들을 어떤 순서로 놓을지만 생각을 해주면 충분하다. 같은 값을 가진 개미들끼리는 원래 위치 순서 그대로 놓는 것이 최적이다. 아래 그림을 보자. 

참고로 위와 같은 형태(꼬인 것이 있으면 풀어주는 것이 좋다)의 Greedy는 정말 다양한 문제에서 사용되니 잘 기억해두면 좋다.

코드 : https://github.com/kdh9949/snups-scpc2020/blob/master/code/8/8_pre1_1.cpp

2번

배열의 모든 값의 합을 \( T \) 라고 하자. \( K \)개의 부분으로 나누어야 하니, 각 부분의 합은 정확히 \( T/K \) 가 되어야 함을 일단 알 수 있다. (\(M = T/K \) 라고 하자)

이제 \( S[i] = A[1]+A[2]+ \cdots +A[i] \) 라고 정의하면 앞에서부터 순서대로 \( S[i] = 1M, 2M, \cdots, (K-1)M \)이 되는 부분 바로 뒤에서 각각 한 번씩 잘라주어야 함을 알 수 있다. 이것은 간단하게 DP로 해결할 수 있는데, 크기가 \(K\)인 DP 배열을 잡고 초기에 \(D[0]=1\)로 놓은 다음, \(S[i]\)를 앞에서부터 보면서 그 값이 어떤 \(a\)에 대해 \(S[i]=aM\)을 만족할 경우 \(D[a]+=D[a-1]\)을 수행해주면 된다. 배열 전체를 다 본 뒤의 \(D[K-1]\)의 값이 답이 된다.

이제 이걸 짜서 내면 아마 Runtime Error를 받을 것이다. 왜냐하면 \( M=0 \)일 수 있기 때문이다. 그 경우에는 위의 논리가 성립하지 않아서 따로 처리를 해 주어야 한다. 이 때는 \( S[i]=0 \)인 모든 부분(단, i=N은 제외)이 똑같이 절단 부분이 될 수 있으므로 그런 부분이 \(X\)개 있다고 하면 \( \binom{X}{K-1} \) 이 답이 된다.

코드 : https://github.com/kdh9949/snups-scpc2020/blob/master/code/8/8_pre1_2.cpp

3번

문제를 딱 처음 보면 "아니 너무 어려운데;;" 라는 생각이 들 수 있다. 하지만, 이 문제가 1차예선 3번에 있는 이유가 분명 있을 것이다 하고 차근차근 생각을 해 보면 어렵지 않게 발상을 할 수 있다.

일단 핵심 아이디어는 "꼭짓점에는 무조건 가로선 1개와 세로선 1개가 연결되어 있어야 한다"라는 사실로부터, 가로선과 세로선을 분리해 생각하는 것이다.

생각을 편하게 하기 위해 우선 "에러 점"이 없다고 해 보자. 가로선은 같은 y좌표인 점들끼리만 그을 수 있으므로 특정 \(y=k\) 직선 위에 있는 점들을 가져와서 생각해 보자. 모든 점에 가로선이 딱 1개만 있으려면 어떻게 되어야 할까? 가로선 2개가 겹칠 수 없으므로, 아래 그림과 같이 무조건 앞에서부터 2개씩 짝지은 꼴로만 선을 그을 수 있음을 알 수 있다. 세로선도 마찬가지이다.

또 다른 중요한 사실은 점이 무조건 짝수 개여야 한다는 것이다. 그러면 이제 에러 점이 최대 1개 있을 때에 그 점의 위치를 무조건 알아낼 수 있는데, 점이 홀수 개 있는 x좌표와 y좌표를 각각 구하면 그 곳이 바로 에러 점의 좌표이기 때문이다. 즉 아래 그림과 같이 에러 점의 위치를 알아낸 뒤, 모든 가로선과 세로선을 위에서 말한 방식대로 쉽게 구할 수 있다.

생긴 것에 비해 풀이와 코드가 매우 간결하다. 신기한 문제인 듯.

코드 : https://github.com/kdh9949/snups-scpc2020/blob/master/code/8/8_pre1_3.cpp

4번

우선 \(s\)에서 만들 수 있는 문자열이 어떤 꼴인지 생각을 해 보자. 다음과 같이 표현하는 것이 가장 깔끔할 듯 하다.

- 두 개의 구간 \(L_a = [s_a, e_a], L_b = [s_b, e_b]\)를 선택한다. 그리고 \(L_a\) 밖에 있는 'a'와 \(L_b\) 밖에 있는 'b'를 모두 지운다. 남은 문자들을 따닥따닥 붙인다.

첫 번째로 관찰할 것은, \(t\)에서 'a'와 'b'가 각각 몇 개 등장하는지에 따라 가능한 \(P_a\)와 \(P_b\)의 후보를 O(N)개로 줄일 수 있다는 사실이다. \(P_a[i]\)를 \(s\)에서 왼쪽에서 \(i\)번째 'a'의 인덱스 (각각 0-based) 라고 정의하고, \(s\)와 \(t\) 에서 'a'가 각각 \(A_s\), \(A_t\)번 등장한다고 하면 \(L_a\)로 고려해야 할 것은 \(0 \le i \le A_s - A_t + 1\)에 대해 \( [P_a[i], P_a[i + A_t -1]] \) 들 뿐이다. 'b'에 대해서도 \(P_b\), \(B_s\), \(B_t\) 등을 유사하게 정의할 수 있다. \(L_a\)와 \(L_b\)를 정하는 가짓수가 O(N^2)이고, 두 구간을 정하면 실제로 답이 되는지 판별은 O(N)에 되므로 O(N^3) 풀이를 일단 얻는다.

두 번째로 관찰할 것은 각각의 \(L_a\)에 대해 답이 될 수 있는 \(L_b\)가 유일하다는 것이다. 우선 논의의 편의를 위해 \(t\)의 첫 번째 글자는 항상 'a'라고 하자. (아니라면 입력에서 모든 'a'를 'b'로, 'b'를 'a'로 바꿔주면 된다)

이제 \(t\)에서 가장 처음으로 연속하게 등장하는 "aaaaabbbba..." 부분을 주목하자. 앞에서부터 'a'가 연속해서 \(X\)개, 그 바로 다음에 있는 'b'가 연속해서 \(Y\)개 있다고 하자. (\(t\)에 'b'가 없거나, \(t\)가 "aa..abb..b" 와 같은 꼴이라면 따로 예외처리를 해주자.) 그렇다면, \(L_a\)를 정했을 때 \(L_b\)의 시작점, 즉 첫 번째 'b'는 정확히 \(X\)개의 'a' 다음에 와야 하며, 또 그 다음번 'a'가 나오기 전에 'b'가 정확히 \(Y\)개 나와야 한다. 즉, \(L_a = [P_a[i], P_a[i + A_t - 1]]\)일 경우 거기에 대한 유일한 \(L_b\)는 \(P_a[i + X] - Y = P_b[j]\)인 \(j\)에 대해 \([P_b[j], P_b[j + B_t - 1]]\)이 된다. (단, \(P_a[i + X - 1] - P_a[i + X] - 1 < Y\)일 경우 해당 \(L_a\)는 답이 되지 못함)

이제 가능한 구간 쌍의 후보 수가 O(N)개로 줄었으므로 O(N^2) 풀이를 얻는다.

제한이 꽤 크기 때문에, 전체 문제를 해결하기 위해서는 O(N) 정도로 매우 빠른 풀이가 필요하다. 우선, 각 \(L_a\)에 대해 \(L_b\)를 구하는 것은 \(L_a\)의 시작점이 증가함에 따라 \(L_b\)의 시작점 역시 증가하므로 two pointer를 사용해 간단히 O(N)에 가능하다. 이제 각 구간 쌍에 대해 그것이 실제로 답이 되는지를 빠르게 체크해야 하는데, 이것은 아래 그림과 같이 두 구간의 교구간(intersection)을 구한 다음 왼쪽/오른쪽으로 삐져나온 부분과 교구간을 각각 check해주면 된다.

삐져나온 부분은 'a' 또는 'b'만 등장하므로 \(s\)에서 해당 부분에 등장하는 문자 개수를 세서 \(t\)의 앞/뒤 부분과 일치하는지를 판별하면 된다. 이는 누적합으로 O(1)에 쉽게 가능하다. 그리고 이를 통해 앞서 구한 교구간에 해당하는 부분이 \(t\)의 어느 부분에 match되어야 할지 역시 구할 수 있다.

교구간에 대해서는 \(s\)와 \(t\)의 해당 부분이 정확히 일치하는지, 즉 substring match를 빠르게 판별해야 한다. 이는 Hash로 O(1)에 할 수 있다.

+ 나는 Hash를 제외한 나머지 부분을 모두 짜고, 혹시 hash가 틀릴까봐 교구간 비교하는 부분만 for문 돌려서 naive로 짰는데 내니까 통과했다.. 근데 솔직히 막기 좀 어려울듯 ㅎ

코드 : https://github.com/kdh9949/snups-scpc2020/blob/master/code/8/8_pre1_4.cpp

5번

"독립이 아닌 쌍"의 수를 세서 전체 쌍의 수에서 빼는 접근을 취하자. 그러면 이제 각 칸에 대해 자기 오른쪽/아래에 있는 칸들 중 도달 가능한 칸의 개수를 다 세면 되는 것으로 문제가 바뀐다.

문제에서 가장 중요한 조건은 역시 "임의의 막히지 않은 칸에 대해 그 칸을 지나는 경로가 존재한다" 이다. 이 조건을 통해 다음과 같은 사실이 성립함을 증명할 수 있다.

2가지의 그리디 전략을 정의하자.
- 전략 R : 오른쪽으로 갈 수 있으면 간다. 못 가면 아래로 간다.
- 전략 D : 아래로 갈 수 있으면 간다. 못 가면 오른쪽으로 간다.
임의의 막히지 않은 칸 \( (r, c) \)에 대해, 두 전략 모두 \((N, N)\)에 반드시 도달한다. 또한, 그 칸에서 시작해 도달 가능한 칸은 오직 "전략 R의 경로"와 "전략 D의 경로" 사이에 끼어 있는 (경로상의 칸 포함) 막히지 않은 칸들이다.

(증명, 디테일 약간 생략)
"막히지 않은 모든 칸에 대해 경로가 존재한다"라는 조건 때문에, 어떤 상황에서든 오른쪽이나 아래쪽 둘 중 하나는 무조건 갈 수 있다. (그렇지 않다면 조건에 모순) 따라서 두 전략 모두 \((N, N)\)에 반드시 도달한다.
한편, 경로를 역행한다고 생각하면 막히지 않은 모든 칸에 대해 왼쪽/위쪽 둘 중 하나 역시 무조건 갈 수 있다. 만약 어떤 칸이 전략 R과 D의 경로 사이에 끼어있다면, 왼쪽/위쪽 중 가능한 칸으로 아무렇게나 가다가 언젠가는 분명 두 경로 중 하나와 만날 것이고, 그 때부터 그냥 그 경로를 쭉 따라가면 \((r, c)\)까지 도달 가능, 즉 \((r, c)\)에서 그 칸으로 도달 가능하다.
반면, 그렇지 않은 칸에서 출발했는데 \((r, c)\)까지 도달 가능하다면 그 경로를 거꾸로 했을 때 전략 R (또는 D)의 경로를 "뚫고 지나가야" 되는데 그러면 애초에 전략 R (또는 D) 가 최대한 그리디하게 한쪽 우선으로 움직이는 전략이었는데 그것에 모순이 되므로 말이 안 된다. 즉 전략 R/D에 의해 "가려진" 칸에는 도달이 불가능.

전략 R과 전략 D가 "가리는" 칸은 완전히 별개이므로, 각각에 대해 가리는 칸의 개수를 빠르게 세어 주면 된다. 이는 매우 간단한 DP로 구할 수 있다. \( R[r][c] \) 를 \((r, c)\)에서 R 전략을 시작했을 때 경로 오른쪽으로 가려지는 막히지 않은 칸의 개수라고 정의하면, \((r, c+1)\)에 갈 수 있을 경우 \( R[r][c] = R[r][c+1] \) 이고 갈 수 없을 경우 \( R[r][c] = R[r+1][c] + \) (\(c+1 < i \le N\)에 대해 막히지 않은 칸 \((r, i)\)의 개수) 이다. (둘 중 한 칸은 무조건 갈 수 있음에 주목하라) 전략 D에 대해서도 비슷한 DP를 설계할 수 있을 것이다. 아니면 그냥 입력을 transpose해서 한 번 더 돌려도 된다. DP의 계산은 누적합을 이용해 O(N^2)에 쉽게 된다.

+ 처음에 O(N^3)짜리 코드를 냈는데 시간 초과가 났다. N <= 400이 의도한 게 O(N^3)이 아니고 O(N^2logN) 이런 거였나..

코드 : https://github.com/kdh9949/snups-scpc2020/blob/master/code/8/8_pre1_5.cpp