2020년 국제정보올림피아드 선발고사 풀이

2020년 1월 17일과 7월 12일에 열린 선발고사 문제 풀이입니다.
1차 3번(지름길), 2차 2번(하나 둘 셋), 2차 3번(열차의 이동)은 아직 풀이가 준비되지 않았습니다.

1-1. 문자열 찾기 (백준 25008)

Subtask 1. $N = M$ (8점)

$f(S_i) = P_i$인 일대응 대응 함수 $f$가 존재하는지 확인하면 되고, $O(N)$에 해결할 수 있습니다.

Subtask 3. $N \leq 2\,000$ (25점)

$S$의 길이가 $M$인 모든 부분 문자열에 대해 Subtask 1의 풀이를 적용하면 $O(NM)$에 해결할 수 있습니다.

Subtask 4. $N \leq 1\,000\,000$ (100점)

KMP 알고리즘을 생각해 봅시다. KMP 알고리즘은 패턴의 실패 함수를 구한 뒤, 원본 문자열과 패턴 문자열을 한 글자씩 비교하면서 매칭에 실패하는 경우 실패 함수를 따라가는 방식으로 진행합니다. 패턴 $P$가 문자열 $S$의 부분 문자열인지 판별하는 가장 기초적인 KMP 알고리즘의 구현은 다음과 같습니다.

vector<int> GetFail(const string &P){
    int n = P.size();
    vector<int> Fail(n);
    for(int i=1, j=0; i<n; i++){
        while(j > 0 && P[i] == P[j]) j = Fail[j-1];
        if(P[i] == P[j]) Fail[i] = ++j;
    }
    return Fail;
}
vector<int> KMP(const string &S, const string &P){
    int n = S.size(), m = P.size();
    vector<int> Fail = GetFail(P), R;
    for(int i=0, j=0; i<n; i++){
        while(j > 0 && S[i] != P[j]) j = Fail[j-1];
        if(S[i] == P[j]){
            if(j + 1 == m) R.push_back(i-m+1), j = Fail[j];
            else j++;
        }
    }
    return R;
}

5번째 줄의 P[i] == P[j]는 단순히 P[i]와 P[j]가 동일한지 비교하는 것이 아닌, P[0..j-1]과 P[i-j..i-1]이 동치인 상황에서 한 글자씩 추가한P[0..j]와 P[i-j..i]가 동치인지 확인하는 부분입니다. 마찬가지로 14번째 줄의 S[i] == P[j]도 P[0..j]와 S[i-j..i]가 동치인지 확인하는 조건식입니다.
즉, 사실상 같은 문자열 $A, B$가 있을 때, 뒤에 각각 $a, b$를 붙인 $A+a$와 $B+b$가 사실상 같은 문자열인지 빠르게 확인할 수 있다면 KMP 알고리즘을 이용해 문제를 해결할 수 있습니다.

만약 문자열 $A$에 이미 문자 $a$가 등장했다면 $a$는 매칭되어야 하는 짝이 정해져 있습니다. 반대로, 등장한 적이 없다면 아직 매칭되지 않은 임의의 문자와 매칭해도 됩니다.
이 정보는 각 문자마다 가장 최근에 등장한 위치를 저장하고 있다면 빠르게 처리할 수 있습니다. 구체적으로, P[i]가 i 이전에서 나온 가장 최근의 위치 Prv[i]를 알고 있다면 상수 시간에 사실상 같은 문자열인지 확인할 수 있습니다.

전체 시간 복잡도는 $O(N+M)$입니다.

1-2. 뚫기 (백준 25009)

Subtask 1. $N \leq 3\,000, M \leq 3\,000, Q=1$ (7점)

사실 $M \leq 3\,000$ 조건이 없더라도 좌표 압축을 하면 $M = O(N)$으로 생각할 수 있습니다.

$i-1$번째 줄에서 $(i, j)$로 이동하는 것은 $(i-1, k)$에서 앞으로 한 칸 전진해 $(i, k)$로 이동한 뒤, 비용이 $A$인 연산을 이용해 $(i, j)$로 이동하는, 두 개의 단계로 나눌 수 있습니다. DP 배열을 다음과 같이 정의하겠습니다.

$D(2i, j) = $ 마지막에 앞으로 한 칸 전진해서 $(i, j)$에 도달하는 최소 비용
$D(2i+1, j) = $ $(i, j)$에 도달하는 최소 비용

$D(2i, j) = D(2i-1, j) + (0 \textit{ or } B)$이고, $D(2i+1,j) = \min\lbrace D(2i,j), D(2i,k)+A \rbrace$ 입니다. $O(N^2)$에 계산할 수 있습니다.

Subtask 2. $Q \leq 50$ (29점)

$D(i,\ast)$를 하나의 세그먼트 트리로 관리합니다. $D(i-1, \ast)$를 빠르게 $D(i, \ast)$로 바꾸는 방법을 찾아야 합니다.

$D(2i,j) = D(2i-1, j) + B$는 막이 존재하는 구간에 $B$를 더하는 것과 동일하고, 이는 세그먼트 트리와 레이지 프로퍼게이션을 이용해 $O(\log N)$에 수행할 수 있습니다.
$D(2i+1,j) = \min\lbrace D(2i,j), D(2i,k)+A \rbrace$는 $D(2i,\ast)$의 최솟값 $D(2i,k)$를 구한 다음, 트리의 기존 값과 $D(2i,k)+A$ 중 더 작은 값으로 갱신해야 합니다. 이는 세그먼트 트리 비츠를 이용해 $O(\log N)$에 수행할 수 있습니다.

각 쿼리를 $O(N \log N)$에 처리할 수 있으므로 전체 시간 복잡도는 $O(QN \log N)$입니다.

Subtask 5. $N \leq 10\,000$ (100점)

Subtask 1/2의 풀이를 아무리 최적화해도 쿼리를 $O(N \log N)$보다 빠르게 처리할 수는 없어 보입니다. 대신, 각 연산을 각각 최대 $N$번만 사용해도 최적해를 찾을 수 있다는 점을 이용해 다른 풀이를 생각해 봅시다.

만약 모든 $0 \leq i \leq N$에 대해, 비용이 $A$인 연산을 정확히 $i$번 사용했을 때 필요한 $B$ 연산의 횟수를 알고 있다면, $i$가 증가할수록 필요한 $B$ 연산의 횟수는 단조감소하므로 이분 탐색을 이용해 각 쿼리를 $O(\log N)$에 처리할 수 있습니다. 모든 $i$에 대해 직접 계산해보면 계산 방법에 따라 Subtask 3/4를 해결할 수 있습니다.

도착점까지 갈 때 필요한 A 연산의 횟수 $a$와 B 연산의 횟수 $b$를 2차원 점 $(a, b)$로 나타내보면, 볼록 껍질의 왼쪽 아래 부분을 구성하는 점만 실제 정답이 될 수 있다는 것을 알 수 있습니다. 좌표 범위가 $X$일 때 볼록 껍질의 꼭짓점이 될 수 있는 정수 격자점은 최대 $O(X^{2/3})$개이기 때문에, $N+1$개의 점에서 모두 DP를 하는 것 대신 왼쪽 아래 껍질 상의 점에 대해서만 DP를 하면 시간 복잡도를 줄일 수 있습니다.

필요한 점을 빠르게 찾는 방법을 알아봅시다. 먼저, x좌표가 가장 작은 왼쪽에 있는 점 $L$과 y좌표가 가장 작은 아래에 있는 점 $U$는 항상 껍질에 포함됩니다. 그러므로 두 점을 먼저 구합니다.
그 다음에는 $L$과 $U$를 잇는 직선과 평행한 껍질의 접선의 접점 $M$을 찾습니다. 다시 $L$과 $M$을 잇는 직선, $M$과 $U$를 잇는 직선의 기울기를 재귀적으로 처리하는 과정을 통해 모든 점을 찾아줄 수 있습니다.

만약 주어진 기울기에 대한 볼록 껍질의 접점을 $T(N)$ 시간에 찾을 수 있다면 모든 점을 $O(N^{2/3}T(N))$에 구할 수 있습니다. 이때 $L$과 $U$는 기울기가 $1/0, 0/1$인 접선의 접점입니다.
기울기가 $-p/q\ (p,q \geq 0)$인 접점을 구하는 것은 A 연산의 비용이 $p$, B 연산의 비용이 $q$인 문제를 해결하는 것으로 생각할 수 있습니다. 이는 Subtask 2의 풀이를 이용해 $O(N \log N)$에 해결할 수 있습니다.

$T(N) = O(N \log N)$이므로 $O(N^{2/3} \cdot N \log N)$에 모든 점을 계산할 수 있습니다. 쿼리는 $O(\log N)$에 처리할 수 있으므로 전체 시간 복잡도는 $O((N^{5/3} + Q) \log N)$입니다. 만약 세그먼트 트리 대신 평방 분할을 사용하면 $O(N^{13/6} + Q \log N)$이 됩니다.

1-3. 지름길 (백준 25010)

풀이 준비 중

1-4. 칠하기 (백준 25011)

Subtask 2. $N,M \leq 1\,000$ (100점)

가로 방향으로 연속한 칸 그룹과 세로 방향으로 연속한 칸 그룹을 정점으로 생각하면 방향 그래프를 만들 수 있습니다. 만들어진 모든 정점을 지나는 보행(walk)이 존재하는지 판별하는 문제로 생각할 수 있습니다.

어떤 정점 $v$를 방문할 수 있다면 $v$와 같은 SCC에 속한 정점을 모두 방문할 수 있기 때문에 SCC를 압축한 DAG에서 문제를 해결해도 됩니다. DAG의 한 정점에서 출발해 모든 정점을 방문하는 walk가 있는지 판별하면 되고, Kosaraju’s Algorithm는 위상정렬 순서대로 SCC를 찾기 때문에 $i$번째 SCC에서 $i+1$번째 SCC로 가는 간선이 있는지 확인하면 됩니다.

시간 복잡도는 $O(NM)$입니다.

2-1. 마법의 다이얼 (백준 25012)

Subtask 1, 3. $N \leq 5\,000$ (26점)

$M$개의 다이얼 중 하나는 돌리지 않아도 최적해를 찾을 수 있습니다.

$f(i,j)$를 $i$번째 다이얼을 돌리지 않으면서 $j$번째 줄에 $M$개의 점이 오도록 만드는 최소 비용이라고 정의합니다. $N$개의 모든 점에 대해 $f$를 계산한 뒤 최솟값을 취하면 되고, $f$는 매번 $O(N)$에 계산할 수 있습니다. 전체 시간 복잡도는 $O(N^2)$입니다.

Subtask 2. $M \leq 5\,000,\ R \leq 5\,000$ (41점)

$f(j)$를 $j$번째 줄에 $M$개의 점이 오도록 만드는 최소 비용이라고 정의합시다. $f$는 매번 $O(N)$에 계산할 수 있습니다.
다이얼 하나를 고정하더라도 최적해를 찾을 수 있기 때문에, 실제로 확인해야 하는 $j$는 $\min(N,R)$가지입니다. $f(j)$는 각 다이얼마다 $j$와 가장 가까운 점을 찾아서 거리를 더하는 것으로 구할 수 있고, 이분 탐색을 이용해 $f(j)$를 $O(M \log N)$에 계산할 수 있습니다. 전체 시간 복잡도는 $O(RM \log N)$입니다.

Subtask 4. $N \leq 500\,000, R \leq 10^9$ (150점)

$f_i(j)$를 $i$번째 다이얼의 $j$번째 줄에 점이 오도록 만드는 최소 비용이라고 정의합시다. $f(j) = \sum f_i(j)$입니다.
함수 $f_i(j)$의 개형을 생각해보면, 기울기가 1 또는 -1인 \/\/\/\... 형태이고, 기울기가 바뀌는 지점은 점의 개수에 비례한다는 것을 알 수 있습니다. 그러므로 $f_i(j)$의 기울기가 바뀌는 지점과 변화량을 모두 구한다면 $f(j)$는 단순히 해당 정보들을 합쳐주는 것으로 구할 수 있습니다.

$i$번째 다이얼의 $a_1 < a_2 < \cdots < a_k$번째 줄에 점이 있다고 가정합시다. $a_x \leq j \leq a_{x+1}$인 $j$에 대해, $j \leq (a_x+a_{x+1})/2$이면 $f_i(j) = j-a_x$이고, $j \geq (a_x+a_{x+1})/2$이면 $f_i(j) = a_{x+1}-j$입니다. $j < a_1 \lor j > a_k$인 경우만 예외처리하면 됩니다.
함수 $f_i(j)$의 개형은 기울기가 1 또는 -1인 \/\/\... 형태라는 것을 알 수 있고, 기울기가 바뀌는 지점은 점의 개수에 비례한다는 것을 알 수 있습니다. 그러므로 $f_i(j)$의 기울기가 바뀌는 지점과 변화량을 모두 구하고, 이 정보들을 모두 합쳐서 $f(j)$ 함수를 만들 수 있습니다.

기울기가 바뀌는 지점은 반정수이므로 2를 곱하면 쉽게 처리할 수 있습니다.

std::map 등을 이용해 $O(N \log N)$에 해결할 수 있습니다.

2-2. 하나 둘 셋 (백준 25013)

풀이 준비 중

2-3. 열차의 이동 (백준 25014)

풀이 준비 중

2-4. 아이싱 (백준 25015)

Subtask 6. $N,M \leq 250\,000$ (150점)

풀이