SCPC 2023 1차 예선 후기

1번

 브루트포스로 최댓값 찾으면 된다.

2번

 방향 전환을 여러 번 하는 것은 의미가 없다. 어차피 가장 먼 곳까지 가는 길 중간에 다 수확 가능하기 때문이다. 따라서 한 방향으로 맥시멈까지 갔다가 반대방향으로 전환해서 남은 이동거리만큼 최대한 가면 된다. 맥시멈 정하기는 O(N)에 할 수 있고, 맥시멈까지 가면서 수확할 수 있는 양은 정렬 후 이분탐색으로 O(logN)에 구할 수 있으므로 총 시간복잡도 O(NlogN)에 해결가능하다.

1. 왼쪽 먼저 가기 → -(lmax)까지 갔다가 +(D-2*lmax)까지 가기
2. 오른쪽 먼저 가기 → +(rmax)까지 갔다가 -(D-2*rmax)까지 가기

3번

 시뮬레이션할수록 빈 바구니가 줄어들게 된다. 따라서 '총 구슬 개수의 합'이 '바구니 개수'보다 크거나 같은 경우에는 빈 바구니가 하나도 남지 않게 된다. 빈 바구니가 하나도 없으므로 모든 바구니가 이전 바구니에서 한 개를 받고(+1) 다음 바구니로 한 개를 넘겨주게 되는데(-1) 이러면 전과 똑같은 상태가 된다. 따라서 이 경우에는 상태가 1가지로 고정된다.

 그럼 '총 구슬 개수의 합'이 '바구니 개수'보다 작은 경우를 살펴보자. 이 경우에는 시뮬레이션을 반복해도 빈 바구니가 무조건 존재하고, 비어있지 않은 바구니는 무조건 1개의 구슬이 들어있게 된다. 이렇게 0과 1만 남게 되었을 때 상태를 문자열 S로 표현하면, 반복되는 상태의 개수는 'S+S에서 S의 (0이 아닌) 시작 인덱스'와 같다. 이는 KMP로 O(N)에 구할 수 있다.

 이제 0과 1만 남기면 해결된다. 시뮬레이션을 그대로 구현하는 방법은 O(N^2)이 필요하다. O(N)에 해결할 수 있는 방법을 생각해야 한다. (여기서부터는 비정석적인 풀이이니 참고하지 마세요ㅠ) 그냥 손으로 시뮬레이션을 몇 번 하다보니까 0의 오른쪽(시계방향) 칸이 2 이상인 경우 해당 0이 다음 턴에 메워진다는 규칙을 발견했다. 반대로 생각하면 2 이상인 칸에 있는 구슬을 왼쪽(반시계방향)으로 밀어 0인 칸을 메우면 된다는 뜻이다. 시뮬레이션 원리를 이해해서 규칙을 만들어야 하는데 규칙을 때려 맞춰 풀어버린 문제였다..

4번

 문자열 P의 prefix들을 이어 붙여 문자열 R을 만드는데 사용되는 prefix 개수를 최소로 해야 하는 문제이다. R의 맨 뒤에서부터 최대한 길게 매칭을 해야 사용되는 prefix의 수를 최소화시킬 수 있다.

 아래 그림을 보자. 맨 뒤(노랑)에서 3글자를 매칭할 수도 있고 1글자만 매칭할 수도 있다고 하자. 3글자 매칭시킨 경우를 A, 1글자만 매칭시킨 경우를 B라 하자. 만약 B가 맨 앞까지 전체 매칭이 가능하다면, A도 무조건 전체 매칭이 가능하다. 그 다음 매칭(회색)의 뒷부분만 자르면 되기 때문이다. prefix와 매칭하고 있기 때문에 뒷부분을 잘라도 아무 문제가 없다.

 아래와 같이 그 다음 매칭을 통째로 잘라버릴 수도 있다. 이 경우에는 사용되는 prefix 개수가 B보다 1개 줄어들게 될 것이다. 따라서 맨 뒤에서부터 최대한 길게 매칭을 하는 그리디한 풀이가 가능함을 알 수 있다.

 뒤에서부터 최대 매칭을 하기 위해서는 R의 각 인덱스에서 앞쪽으로 최대로 몇 글자까지 P의 prefix와 매칭시킬 수 있는지를 구해야 하는데, 이는 문자열 P + '.' + R의 Partial Match Table과 같다. KMP를 사용하여 O(N)에 pi를 구해준 뒤, 뒤에서부터 pi[i]개만큼 매칭시키기를 반복하면서 몇 개의 prefix가 사용되었는지 카운트해준다. 만약 중간에 pi[i] = 0을 만난다면 해당 인덱스에서 한 글자도 매칭이 안된다는 뜻이므로 불가능한 경우이다.

5번

 각 수면 구간에서의 비용을 최소화해야 하는 문제이다. 길이가 t인 수면 구간에서 상태 Si를 유지한다면 P[i]*t의 비용이 들고, 다시 S1으로 돌아가는 데 w[i]의 비용이 들기 때문에 총 비용은 P[i]*t + W[i]가 된다. 즉, 각 상태를 f(t) = P[i]*t + W[i]라는 일차함수로 보고 주어지는 t에 대해 f(t)의 최솟값을 구해주는 문제가 된다. 컨벡스 헐 트릭을 사용하면 O(NlogN)에 해결할 수 있다.

---

3번째 SCPC 참가였다. 1차 예선이긴하지만 그래도 첫 올솔을 해냈다.

+) Round 2 진출