혜아의 아무말

SCPC 2021 2차 대회가 8월 7일 오전 9시부터 12시간동안 진행되었다.

SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다.

이 게시글에서는 해당 대회 문제의 풀이를 다룬다.

1. 원 안의 점

  문제를 요약하면, 원점 $(0, 0)$을 중심으로 하는 반지름 $R$인 원 내부에 들어있는 좌표가 모두 정수인 점의 개수를 세는 문제이다. 단, 원의 경계에 놓인 점은 생각하지 않는다. ($R \le 200\,000$)

  풀이는 간단하다. $x$좌표가 $a$인 위치에 대해서 $y$좌표로 가능한 값은 $-\sqrt{x^2-a^2}$ 초과 $\sqrt{x^2-a^2}$ 미만인 값이고($-R < a < R$), 정수점의 개수는 $\sqrt{x^2-a^2}$ 미만인 양의 정수의 개수에다가 1을 곱한 값이다. 구현할 때는 $\sum_{a=-R+1}^{R-1} (\lfloor \sqrt{x^2-a^2-1} \rfloor$)과 같은 식으로 구현할 수 있다. ($x^2-a^2$은 정수이기 때문에, $x^2-a^2$ 미만인 정수는 $x^2-a^2-1$ 이하인 정수와 같다.)

  시간복잡도는 $\mathcal{O}(R)$이다.

2. 직8각형

  문제를 요약하면, 한 변의 길이가 $K$인 각 변이 축에 평행한 정사각형 5개가 그림처럼 +모양으로 배치되어 있을 때, 외각에 놓인 8개의 점을 길이가 $K$인 직8각형이라고 부른다. 평면 상의 점 8개와 $K$가 주어질 때, 길이가 $K$인 직8각형이 되도록 점을 옮기려고 한다. 여기서, 점의 순서는 중요하지 않다. 이 때, 필요한 점의 이동거리 합의 최소값을 구하는 문제이다. 여기서, 이동거리는 택시거리이다($(a, b)$와 $(c, d)$ 사이의 거리는 $|a-b| + |c-d|$이다.)

  어떤 점이 직8각형의 어떤 점에 대응되어야 하는지 알 경우에 필요한 이동거리 합의 최솟값을 구하는 방법을 생각해보자.

  첫째로, 택시거리는 $x$좌표와 $y$좌표의 차이의 합이기 때문에, $x$좌표와 $y$좌표를 따로 생각할 수 있다. 그렇기 때문에, $x$좌표와 $y$좌표에 대해 문제를 따로 따로 풀어줄 수 있다.

  둘째로, 이동거리가 최소가 되는 $p_0$의 $x$좌표를 편의상 $a$라고 하면, $p_0, p_1$으로 옮기는 점은 $x$좌표가 $a$, $p_2, p_7$로 옮기는 점은 $x$좌표가 $a+K$, $p_3, p_6$으로 옮기는 점은 $x$좌표가 $a+2K$, $p_4, p_5$로 옮기는 점은 $x$좌표가 $a+3K$가 되도록 옮겨야 한다. $p_i$로 옮겨야 하는 점의 $x$좌표를 $x_i$라고 하면, $|x_0 - a| + |x_1 - a| + |x_2 - (a+K)| + |x_3 - (a+2K)| + |x_4 - (a+3K)| + |x_5 - (a+3K)| + |x_6 - (a+2K)| + |x_7 - (a+K)|$ 를 최소화 하는 문제가 된다. 기본적으로 어떤 배열 $v$에 대해, 합 $|v_i-a|$를 최소화하는 문제는 매우 잘 알려진 문제로, $a$를 $v_i$의 중앙값으로 잡으면 된다. 이 경우도 유사하게, $a$를 $x_0, x_1, x_2-K, x_3-2K, x_4-3K, x_5-3K, x_6-2K, x_7-K$의 중앙값으로 설정하면 될 것이다. $y$좌표에 대해서도 문제를 비슷하게 풀어줄 수 있다.

  이런 식으로, 어떤 점이 직8각형의 어떤 점에 대응되어야 하는지 알 경우 필요한 이동거리 합의 최솟값은 $\mathcal{O}(8)$에서 $\mathcal{O}(8^2)$ 정도의 시간에 중앙값을 구해서 합을 구하는 방식으로 문제를 해결할 수 있다. 이제 모든 조합을 다 시도해보면 $\mathcal{O}(8! \times 8)$ 에서 $\mathcal{O}(8! \times 8^2)$ 정도 시간에 문제를 해결할 수 있다.

3. 산탄총

  문제를 요약하면, $N \times N$ 격자의 각 칸에 (음수일 수 있는) 수가 하나 써 있고, 산탄총의 퍼지는 정도 $K$가 주어진다. 산탄총을 어떤 칸을 중심으로 사격하면 중심과 택시거리가 $K$ 미만인 칸에 대해서, 해당 칸과 중심의 택시거리가 $x$이면 해당 칸에 있는 수에 $K-x$를 곱한 수 만큼의 점수를 얻는다. 여기서, 중심은 격자 밖일수도 있다. 산탄총을 한번 사격해서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 오른쪽 그림은 $K=3$일때 산탄총을 사격해서 얻을 수 있는 점수의 모양이다. ($1 \le K \le N \le 600$)

  모든 칸을 중심으로 해서 산탄총을 쐈을 때, 각각의 점수를 구해서 그 중 최댓값을 구하면 되는 문제이다. 격자의 밖을 중심으로 하는 경우도 물론 고려해야한다. 격자에서 $K$ 이상 떨어진 곳을 중심으로 산탄총을 사격하는 경우에는 점수가 항상 0이므로 고려하지 않아도 되고, 각 좌표가 $-K$ 부터 $N+K$인 곳을 고려해서 사격하면 된다.

  이제, 각 칸의 점수를 효율적으로 구하기 위해서, 중심을 오른쪽으로 한 칸 옮길 때 점수 차이를 살펴보자. 두 칸의 경계를 기준으로 왼쪽에 있는 칸의 거리는 1씩 늘어나고, 오른쪽에 있는 칸의 거리는 1씩 줄어든다. 열 번호가 왼쪽 칸 이하이면서, 거리가 $K$미만인 칸(아래 그림에서 주황색 영역)의 수의 합만큼 값이 줄어들고, 열 번호가 오른쪽 칸 이상이면서, 거리가 $K$미만인 칸(아래 그림에서 파란색 영역)의 수의 합만큼 값이 늘어난다.

  이제, 파란색 영역과 주황색 영역의 합을 효율적으로 구해보자. 파란색 영역의 중심칸을 아래로 한 칸 옮기면 거리가 $K-1$인 점들이 바뀌게 된다. 여기서 위쪽 칸과 거리가 $K-1$이면서, 열 번호가 위쪽 칸 이상이고, 행 번호가 위쪽칸 이하인 점들(아래 그림에서 빨간색 영역)의 수의 합 만큼 값이 줄어들고, 아래쪽 칸과 거리가 $K-1$이면서, 열 번호가 위쪽 칸 이상이고, 행 번호가 오른쪽 칸 이상인 점들(아래 그림에서 초록색 영역)의 수의 합 만큼 값이 늘어난다. 주황색 영역도 대칭적으로 구할 수 있다.

  이제, 우리는 빨간색과 초록색으로 표현된 영역인 대각선 모양의 $K$개의 칸의 합을 효율적으로 구해야하는데, 이는 중심칸이 오른쪽 아래로 내려갔을 때, 왼쪽 끝과 오른쪽 끝의 수가 더해지고 빠지는 것으로 문제를 해결할 수 있다. (그림의 노란색과 보라색 칸) 초록색 영역도 대칭적으로 구할 수 있다.

  이 영역들의 합을, 좌표를 섬세하게 계산해주면 문제를 해결할 수 있다. 각 영역은 중심이 한 점에서 다른 점으로 옮겨질 때 상수번의 연산만을 하기 때문에, 시간 복잡도는 $\mathcal{O}(N^2)$이다.

4. 패턴 매칭

  문제를 요약하면, 두 문자열 $A$와 $B$가 매칭된다는 것은, $A$와 $B$의 길이가 같고, $A_i = A_j$와 $B_i=B_j$가 동치라는 것을 의미한다. 텍스트 하나와 $K$개의 패턴을 주어질 때, 각 패턴이 텍스트에 등장하는 횟수를 계산하여라. (텍스트의 길이 $2\,000\,000$ 이하, 패턴의 길이 $500$이하, 패턴 길이 합 $30\,000$이하)

  Aho-corasik의 패턴 매칭 알고리즘을 사용하자. 우리가 문자열의 각 문자 대신 매칭에 사용할 대상은 이전에 같은 문자가 언제 등장했는지 여부이다. 다음과 같은 관찰을 활용하자.

  관찰. 어떤 문자열 $S$의 $f(S)$를 다음과 같이 정의하자.

    - $f(S)$는 길이가 $S$와 같은 배열이다. $f(S)$의 $i$ 번째 값은 $S_i = S_{i-L}$을 만족하는 최소인 양수 $L$이다. (조건을 만족하는 $L$이 없을 경우 $f(S)$의 $i$ 번째 값은 0이다.)

  문제에서 정의한 문자열 $A$와 $B$가 매칭되는 것은 $f(A)$와 $f(B)$가 동일한 것과 동치이다.

  증명. (⇒) $f$를 정의할 때 사용한 연산은, 문자열의 두 값이 같다는 연산 뿐이기 때문에, 문제에서 주어진 $A$와 $B$에 대한 $f(A)$와 $f(B)$의 값은 동일하다.

  (⇐) $A_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치를 찾아보자. $f(A)_i$가 0이면, 같은 문자가 등장하지 않는다. $f$의 정의에 따라, $A$의 $i-f(A)_i$ 번째 위치에서 $A_i$와 같은 문자가 등장하고, $i-f(A)_i$ 번째 위치에서 $i$번째 위치 사이에서는 문자가 등장하지 않는다. 이제 $i-f(A)_i$ 번째 위치 이전에서는 $A_i$와 같은 문자가 언제 등장하는지를 살펴보자. $A_{i-f(A)_i} = A_i$이기 때문에, $f(A)$ 배열의 $i-f(A)_i$ 값을 확인하는 것으로 재귀적으로 확인해 줄 수 있다.

$f(A)$와 $f(B)$의 값이 같다는 것은, $A_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치와, $B_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치의 집합이 같다는 뜻이다. 그렇기 때문에, $A_i = A_j$와 $B_i=B_j$는 동치이다.

  이를 직접 사용하려고 하면, 위의 정의가 "길이가 다른 두 문자열"에 대해서는 동작하지 않는다는 것을 알 수 있다. 예를 들면 $S=abaca$와 $T=xyx$가 있다고 하자. $f(S)$는 $[0, 0, 2, 0, 2]$이고 $f(T)$는 $[0, 0, 2]$이다. 위에 정의한 문자열 매칭을 그대로 사용하면, $S$는 $T$의 첫 번째 위치에서만 매칭되는 것으로 생각되지만, 실제로는 세번째 위치에서도 매칭된다. 이는 부분문자열 $aca$와 $xyz$에서 첫번째 $a$에 해당하는 $f$값 $2$가 매칭되는 패턴 $xyz$의 $x$의 인덱스인 $0$보다 커서, $2$칸 전의 문자가 사실 같음에도 매칭할 때는 고려대상이 되지 않기 때문에 발생하는 문제이다. 특정 위치의 함수값이 인덱스보다 큰 경우는 고려 대상에서 제외해서 배열의 값을 $0$으로 바꿔줘야 하고, 이는 Aho-corasik의 failure function을 계산할 때 처리해 줄 수 있다.

  이래서, (일반적인) 스트링 $f(T)$에서 패턴 $f(P)$가 언제 등장하는지 개수를 세는 문제로 바뀌었다. 기본적인 Aho-corasik 문제임으로 따로 설명하지는 않는다. 위의 failure function을 계산할 때, 자기보다 길이가 긴 인덱스 값이 등장하는 시점에 유의하자.

  시간복잡도는 문자열 길이와 패턴 길이 합의 선형에 비례하는 시간복잡도가 든다.

5. Hanoi Tower

  문제를 요약하면, 일반적인 하노이 타워 문제와 같이, 1번 기둥에 있는 원판을 3번 원판으로, 큰 디스크가 작은 디스크 위에 올라가지 않도록 모두 옮기는 문제이다. 단, 기존 하노이 타워는 한 기둥에서 다른 기둥으로 옮길 때, 한 기둥의 첫 번째 원판을 다른 기둥의 첫 번째 원판이 되도록 옮겼다. 하지만, 이번 하노이 타워는 한 기둥의 가운데 원판이 다른 기둥의 "가운데 원판"이 되도록 옮겨야 한다. 여기서 어떤 기둥의 가운데 원판은, 그 기둥에 쌓인 원판의 개수를 $n$이라고 할 때, $1+\left\lfloor\frac{n}{2}\right\rfloor$ 번째 원판을 말한다. 최대 이동 회수 $M = 980403$이 주어졌을 때, 디스크의 개수 $N$을 (코드를 제출하는 사람이) 정하고, 1번 기둥의 $N$개의 원판을 3번 기둥으로 옮기는 문제이다. ($N = 26$인 경우 만점이다.)

  여러가지 관찰이 필요한 문제이다. 다음과 같은 관찰을 하나씩 해 보자.

관찰 1. 한 기둥의 가장 위에 있는 원판을 다른 기둥의 가장 위로 옮기려면, 해당 원판을 제외하고는 두 기둥에 다른 어떠한 원판도 존재하지 않아야 한다.

증명. $n=1$인 경우만 $1+\left\lfloor\frac{n}{2}\right\rfloor = 1$이 된다.

  편의상 원판의 번호를 작은 것 부터 큰 것 까지 $1$부터 $N$까지의 번호를 붙이자. 여기서 다음과 같은 전략을 사용할 수 있다. 1번 기둥에서 3번 기둥으로 원판을 모두 옮기기 위해서는 $2$번 원판부터 $N$번 원판까지를 전부다 2번 기둥으로 옮긴다음에, 1번 기둥에서 3번 기둥으로 1번 원판을 옮기고, 2번 기둥에 놓인 $N-1$개의 원판을 다시 3번 기둥으로 옮겨야 한다.

  일반적인 하노이 타워 문제는 나머지 원판들에 대해 재귀적으로 같은 방식으로 진행했겠지만, 이 문제는 다른 점이 있다. 바로, 1번 원판의 존재때문에 기둥을 빼내는 순서가 다르다는 점이다. 1~5번 원판이 쌓여있을 때 빠지는 순서는 3, 4, 2, 5(, 1)순이다. 하지만 2~5번 원판이 쌓여있을 때 빠지는 순서는 4, 3, 5, 2순이다. 즉, 어떤 기둥 위에 (고정되어서 빠지지 않는) 원판이 $0$개 있는지 $1$개 있는지에 따라서 과정이 다르게 된다. $a$, $b$, $c$번 기둥 위에 고정된 원판이 각각 $x$, $y$, $z$개 있는 상황에서 a번 기둥에서 c번 기둥까지 $N$개의 원판을 옮기는 과정을 $Mabc(N, a, b, c)$이라고 말하자. 가장 처음의 상황은 $M000(N, 1, 2, 3)$이고, $M000(N, a, b, c)$는 $M100(N-1, a, c, b)$를 수행하고, $a$에서 $c$로 1번 원판을 옮기고, $M001(b, a, c)$를 수행하게 된다. 이제 해당 기둥의 "가운데 원판"의 위치가 바뀐다.

관찰 2. 기둥 위에 고정된 원판이 1개 있는 경우, 가운데 원판을 $\left\lfloor\frac{n+1}{2}\right\rfloor$번 원판이라고 생각하면 된다. 또한, 해당 기둥의 가장 아래에 있는 원판을 옮기려면, 해당 기둥에는 고정된 원판과 가장 아래에 있는 원판을 제외하고, 남은 원판이 없어야 한다.

증명. 고정된 원판 1개를 제외하고 원판이 $n$개 있는 경우, 고정된 원판을 포함한 중심 위치는 $1+\left\lfloor\frac{n+1}{2}\right\rfloor$번째이다. 첫 번째인 고정된 원판을 제외하면, 중심 위치는 $\left\lfloor\frac{n+1}{2}\right\rfloor$번 원판이 된다. 여기서 $n \ge 1$ 일 때, 항상 $1 \le \left\lfloor\frac{n+1}{2}\right\rfloor \le n$을 만족하므로, 중심 원판은 항상 옮기려는 원판 중에 존재한다. 가장 아래쪽에 있는 원판을 꺼내려면, $n = \left\lfloor\frac{n+1}{2}\right\rfloor$ 이어야 하고, 이 경우는 $n=1$이다. 옮기려는 원판을 제외하고는 다른 원판이 존재하지 않는다.

  이제 해당 과정을 기준으로 $M100(N, a, b, c)$상황을 생각해보자. ($M001$은 $M100$의 역순으로 진행된다.) 가장 아래에 있는 원판을 옮기는 과정을 생각해보자. 이도 마찬가지로, $a$번 기둥의 $N$번 원판을 제외한 원판들을 전부 $b$번 원판에 옮기고 $N$번 원판을 $c$번 원판에 옮긴 이후에, $b$번 기둥의 나머지 원판을 $c$번 기둥으로 옮기면 된다.

  여기서, 과정을 잘 살펴보면 $a$번 기둥에서 마지막에 나오는 두 개의 1번 원판과 $N$번 원판을 옮길 때, $b$번 기둥을 거쳐갈 필요 없이 $c$번 기둥으로 두 원판을 차례로 옮길 수 있다는 것을 알 수 있다. ($a$번째 원판과 $c$번째 원판의 "가운데 원판"을 정의하는 홀짝성이 달라서 발생하는 일이다.) 그래서 과정을 바꿔서 $N-2$개의 기둥을 한번에 옮기는 것으로 문제를 풀 수 있다.

  이제, 여기서 재귀적인 과정을 하려면 또 역시 자신 위와 아래에 있는 원판이 문제라는 것을 알 수 있다. 하지만 이 경우에는 중심 원판이 바뀌지 않기 때문에, 다음과 같은 관찰을 이용해서 재귀식을 그대로 사용할 수 있다.

관찰 3. 기둥 위에 고정된 원판이 X+K개, 아래쪽에 X개 있는 경우 가운데 원판은 기둥 위에 고정된 원판이 $K$개, 아래쪽에 $0$개 있는 경우와 같다.

증명. 원판이 $n$개 있는 경우, 고정된 원판을 포함한 중심 위치는 $1+\left\lfloor\frac{n+2X+K}{2}\right\rfloor$번째이다. $X+K$개의 고정된 원판을 제외하면, 중심 위치는 $1-K+\left\lfloor\frac{n+K}{2}\right\rfloor$번 원판이 된다. $K=0$일 때는, 위에서 $1+\left\lfloor\frac{n}{2}\right\rfloor$번째, $K=1$일 때는, 위에서 $\left\lfloor\frac{n+1}{2}\right\rfloor$번째 원판이다.

  그래서 $1$번과 $N$번 원판을 더 이상 옮기지 않을 생각으로 같이 무시해주어도, 원반의 위치는 변하지 않는다. $M100(N, a, b, c)$는 $M100(N-2, a, c, b)$를 진행하고, $a$ 번 기둥에서 $c$ 번 기둥으로 원판을 두 번 옮기고, $M010(N-2, b, a, c)$를 진행해주면 된다.

  이제 $M010$을 살펴보자. $M010$은 $M000$과 유사하지만, 가운데 원판에 따른 홀짝성을 고려해서 $M101(N-1, a, c, b)$를 진행하고 $a$번 기둥에서 $c$번 기둥으로 원판을 옮기고, $M101(N-1, b, a, c)$를 진행하면 된다. 하지만 이것이 최적이 아닌 경우는 위에 논의했던 대로 $a$ 번 기둥에서 $b$ 번 기둥에 홀짝성이 다른 점을 이용하면 한 번에 두 개의 원판을 옮길 수 있기 때문이다. 이를 이용해서 $a$ 번 기둥에서 $c$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기고, $a$ 번 기둥에서 $b$ 번 기둥으로 $1$번과 $N$번 원판을 옮기고, $c$ 번 기둥에서 $a$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기고, $b$ 번 기둥에서 $c$ 번 기둥으로 $1$번과 $N$번 원판을 옮기고 $a$ 번 기둥에서 $c$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기면 된다.

  ...여기까지가 Jérémy Barbay가 arXiv[1602.03934]에 올린 "Bouncing Towers move faster than Hanoï Towers, but still require exponential time"라는 아티클에 설명되어 있는 사항이고, 이 아티클은 이 방법이 최적이라고 주장하지만, 이 아티클의 증명이 틀렸는지 이 문제가 만점을 받을 수 없는 문제인지, 위에 적힌 방법으로는 만점을 받을 수 없다.($N=25$일 때 $885\,735$번, $N=26$일 때 $1\,594\,323$번 움직인다.)

  이 문제에서 만점을 받으려면, 해당 아티클의 증명의 틀린 부분을 찾으면서 위 문제의 설명에서 간과되어 있는 부분을 찾아야 하는데, $M010(N, a, b, c)$의 과정은 바깥에 있는 고정된 원판을 움직일 수 없는 것을 가정하고 있지만, 사실 고정된 원판을 움직이고 원래 위치로 돌려놓으면 된다!

  다음과 같은 과정을 생각하자. $N$번 원판의 위치를 고려하지 않고 $1$번부터 $N-1$번까지의 원판을 $a$ 번 기둥에서 $b$ 번 기둥으로 옮겨놓는다. 그 후 $N$번 원반이 $a$ 번 기둥에 있으면 $c$ 번 기둥으로, $c$ 번 기둥에 있으면 $a$ 번 기둥으로 옮긴 다음에, 다시 $1$번부터 $N-1$번까지의 원판을 위 과정의 역순으로 $b$ 번 기둥에서 $c$ 번 기둥으로 옮겨놓는다. 이 경우 $M010(N, a, b, c)$는 (Notation을 확장해서 관찰 3에서 $K=-1$이라는 의미로) $M(-1)01(N-1, a, c, b)$를 진행하고 $N$번 원판의 $a$, $c$위치를 바꾼 이후에 $M10(-1)(N-1, b, a, c)$를 실행한다고도 볼 수 있겠다. 여기서 $K$가 $0$이나 $1$이 아닐 경우에는, 가운데 원판이 고정된 원판을 가리킬 수 있다는 점이고, 우리는 이 경우를 특별하게 허용하기로 했다.

  위쪽에서 고정된 원판을 -로 표현했다. 아래쪽에서 고정된 원판은 +로 표현하자. $1$번부터 $N$번까지의 원판을 빼내는 과정의 마지막은 $2, +, 1$번 원판 순이 되어버렸다. 이 경우에도 $1$번 원판을 빼내려면 나머지 원판을 다 빼내야 하기 때문에, 나머지 $2$번부터 $N$번 원판까지를 생각해보자. 가장 빨리 빼내는 방법은 $2$번부터 $N$번까지의 원판을 한 개 이하를 제외하고 $b$ 번 기둥에 몰아놓은 이후에 1번 원판을 $c$ 번 기둥으로 옮기는 것이다. 여기서 한 개 이하의 원판을 제외하는 이유는, 한 개의 원판이 있어도 1번 원판이 $c$번 기둥으로 들어갈 수 있기 때문이다. 여기서 우리는 1번과 2번 다음으로 빼기 어려운 $N$ 번 원판을 $c$ 번 기둥에 같이 남기는 방식을 사용할 것이다.

  $3$번 원판부터 $N$ 번 원판까지를 $c$ 번 기둥에 옮기고, $2$번과 $+$ 번 원판을 $b$ 번 기둥에 옮기다. 그리고 나머지 허용된 하나의 $N$ 번 기둥을 제외한 $3$번 부터 $N-1$번 원판을 $b$ 번 기둥에 옮긴다. 나머지는 재귀적으로 $M(-1)01(N-2, b, a, c)$를 호출해주면 된다.

  이를 구현하면 $N=26$일 때 $972\,051$번 연산을 사용해서 원판을 전부 옮길 수 있고, 이는 $980\,403$이라는 제한 안에 들어가는 수이다.

아래는 풀이를 구현한 소스코드이다.

#1

#2

#3

#4 (node가 패턴의 길이만큼의 배열을 담고 있어서, 시간복잡도가 더 크나, 통과 가능하다)

#5

  7월 19일 오전 9시 30분 부터 12시 10분경까지 풀배터리 검사 두번째를 했습니다. 이번에도 역시 자세한 검사 내용은 검사가 오염되기 때문에 말 하지 않겠지만, 정답이 있는 검사가 아니라 그냥 본인의 생각을 얘기하면 되는 검사였습니다. 그래서 부담스럽지 않게 제 생각을 말했던 편인 것 같습니다.

  10시 50까지 정해진 검사를 하고 쉬었다가 11시 부터 검사를 다시 시작했고, 여기서는 제 과거 일들이라든가, 제가 과거의 어떤것들을 느꼈고 어떠한 계기들이 있었는가, 그리고 현재 제일 고민하고 있는 것은 어떤 것인지 등등에 대해서 말했습니다.

  젠더 디스포리아와 관련된 것은 여기서 말 했는데, 제가 호르몬 치료를 받고 싶은지, 제가 검사지에 작성한 여성상과 남성상에 대해서 물어보시면서 제 여성상과 남성상은 사실 양쪽 성별 모두가 이룰 수 있는 것인데, 왜 굳이 다른 성별이 되고 싶은지 등등을 물어봐서 상세하게 대답했습니다. 저는 제가 생각하고 있는 것을 가감없이 말했습니다.

  또한, 제가 가지고 있는 것으로 추측되는 다른 종류의 정신질환에 대해서도 길지 않게 물어보았습니다. 이와 관련해서 섹슈얼한 부분의 이야기가 메인이 되어서 저는 이 부분의 이야기를 되게 많이 한 편인데, 말하기 힘든 주제일텐데 자세하게 말해줘서 좋다라는 얘기도 했습니다. 보통 사람들은 이런 이야기를 정신과 의사에게도 말하기 꺼려한다고 합니다.

  검사 결과는 다음 진료인 8월 10일 화요일에 같이 나온다고 합니다.

SCPC 2021 1차 대회가 7월 16일 오후 3시부터 24시간동안 진행되었다.

SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다.

이 게시글에서는 해당 문제들의 풀이를 다룬다.

1. 친구들

  문제를 요약하면, i 번 정점과 i+D_i 번 정점을 연결 할 때, (1≤D_i≤N, i+D_i가 N을 넘으면 연결하지 않음), 연결 성분의 개수를 계산하는 문제이다. 그래프를 만들어주고 DFS와 같은 방법을 이용해서 연결 성분을 세어 주면 끝나는 문제이다.

  이 문제에는 같은 시간복잡도의 좀 더 간단한 풀이가 있는데, i+D_i가 N을 넘는 수의 개수가 답이 된다. 이를 증명하기 위해서는 다음과 같은 관찰이 필요하다.

- 이 그래프에는 사이클이 존재하지 않는다.

  만약에 이 그래프에 사이클이 존재한다고 하자. 이 때, 이 사이클에 있는 정점중 가장 낮은 번호를 가진 정점은, 자기보다 번호가 큰 정점 두 개와 연결이 되어있다. 정점을 연결하는 규칙은 수가 작은 i 번 정점과 수가 큰 i+Di 번 정점을 연결하는 것이므로 작은 i 번 정점에 두 개의 연결이 있을 수 없어서 모순이다.

이런 관찰을 통해, 최초에 정점이 존재하지 않았던 상태에서 연결 성분의 개수가 N개이고, 한 번 연결할 때 마다 연결 성분의 개수가 1씩 줄어드므로, 답은 N - (i+D_i가 N 이하인 수의 개수) = i+D_i가 N 초과인 수의 개수이다.

2. 이진수

  문제를 요약하면, 길이 N의 0과 1로 이루어진 문자열 B와 어떤 상수 T가 주어지는데, 0과 1로 이루어진 (숨겨진) 길이 N의 문자열 A에 대해서 A_i+T와 A_i-T중 1이 하나 이상 존재하는 경우에만 B_i가 1이 되도록 만들어진 문자열이다. 단, A의 i+T번째 문자나 i-T번째 문자가 존재하지 않는 경우에는 0으로 취급한다. 사전순으로 가장 빠른 A를 찾아서 출력하는 문제이다.

주어진 입력에 해당하는 A가 존재하는지 (문제에서 요구하지는 않았지만) 찾는 알고리즘을 생각하도록 하자.

- B_i-T나 B_i+T중 0이 있다면, A_i는 0이어야 한다.

  만약 A_i가 1인 경우, B_i-T와 B_i+T가 (존재한다면) 1이어야 하기 때문에, 만약 이 두 수 중 0이 있으면, A_i는 0이어야 모순이 발생하지 않는다.

- B_i-T와 B_i+T중에 0이 없다면, A_i를 1로 두어도 "상관 없다." 여기서 "상관 없다"의 의미는, A가 만약에 존재한다면, A_i가 1인 답도 존재한다는 의미이다.

  만약에 A_i가 0인 답이 존재한다고 하자. 이 A_i를 1로 바꾸게 되면, B_i-T와 B_i+T만 영향을 끼치고, 이 두 숫자는 이미 1이기 때문에, 해당하는 칸에도 영향을 끼치지 않는다. 그래서 A_i가 1이게 되는 답이 존재한다.

  이 두 가지 사항을 이용해서, A가 존재하는지 찾는 알고리즘을 만들었으면, 사전순으로 가장 빠른 A를 찾는 알고리즘은, 가장 첫 자리가 0인 A가 존재하는지 확인하고, 존재한다면 가장 첫 자리를 0으로, 존재하지 않는다면 가장 첫 자리를 1로 설정한다. 마찬가지로 (첫 자리가 고정된 A에 대해) 둘째 자리가 0인 A가 존재하는지 확인하고, 존재한다면 가장 첫 자리를 0으로, 존재하지 않는다면 1로 설정한다, 이를 계속 반복하는 것이 문제의 풀이가 될 것이다. 여기까지의 알고리즘을 구현하면 O(N²) 시간 복잡도의 풀이를 얻을 수 있다.

  이 알고리즘의 시간을 줄이는 법은, A가 존재하는지 확인하는 알고리즘은 A_i의 값 하나의 변경에 대해서는 작은 영향을 끼친다는 것을 관찰하는 것이다. 주어진 입력에 해당하는 최대의 A를 만들자. 그 후, 앞에서부터 살펴보면서, 1이 있으면 해당 1을 0으로 바꿀 수 있으면 바꾸는 과정을 반복하면 문제를 해결할 수 있다. (이는 A_i가 0인 A가 존재하는지 확인하고, 가능하면 0으로 설정하는 과정과 동일하다.) 1을 0으로 바꿀 수 있는지 여부는 A_i를 바꾸었을 때, B라는 문자열 전체, 특히 B_i-T와 B_i+T가 바뀌지 않을 것을 의미한다. 이를 위해서 추가적으로 A_i-2T와 A_i+2T 칸을 확인 해 줘야 한다. 이 과정을 구현하면 O(N) 시간 복잡도의 풀이를 얻을 수 있다.

3. No Cycle

  문제를 요약하면, 그래프가 주어지는데 M개의 간선들은 방향성이 있고, K개의 간선들은 방향성이 없다. 이 때, 방향성이 없는 간선에 적당히 방향을 줘서 사이클이 없도록 해야한다. 단, 답이 여러개 존재하는 경우에 사전순으로 가장 빠른 답을 출력해야한다. 여기서 답은 길이 K의 0과 1로 이루어진 문자열인데, i 번째 방향성이 없는 간선은 두 개의 정점 쌍 (u_i, v_i)로 주어지며, u_i→v_i로 방향을 주면 답의 i번째 문자가 0이고, v_i→u_i로 방향을 주면 답의 i번째 문자가 1이다.

  2번 문제와 유사한 종류의 관찰을 요구한다. 일단 답이 존재하는지 아닌지 찾는 알고리즘에 대해서 확인 해 보자. 방향이 주어진 M개의 간선에 대해서는 사이클이 없기 때문에 위상정렬을 실행할 수 있고, 해당 위상정렬에 대해 뒤쪽에 있는 간선을 앞쪽에 있는 간선으로 이어주면 항상 사이클이 없는 답을 찾을 수 있다.

  사전순으로 가장 빠른 것을 찾는 알고리즘은 2번 문제에 설명된 대로 가장 첫 자리를 0인 답이 존재하는지 아닌지 확인하고, 존재한다면 0, 존재하지 않는다면 1로 설정한 뒤에, 둘째 자리에 대해서도, 셋째 자리에 대해서도 마찬가지로 같은 방법으로 문제를 해결하는 것이다. 이 문제에서는 이미 방향성이 주어진 간선이 사이클이 존재하지 않는 경우 항상 답이 존재하기 때문에, i 번째 자리를 정하고 있다면 i+1 번째 이후의 모든 간선을 무시하고, i번째 간선을 정방향으로 넣었을 때 지금까지 들어가있는 간선에 사이클이 존재하지 않는지 여부를 확인 해 주는 것으로 문제를 해결할 수 있다. 시간복잡도는 O(MK+K²)이다.

4. 예약시스템

  문제를 요약하면, 사람이 2M명 있고 그룹이 N개 있다. 각 사람은 그룹 중 하나에 속해있으며, 스트레스 지수가 있다. 이 2M명의 사람을 2×M 모양의 방에 배치하려고 하는데, 그룹이 다른 두 사람이 인접한 방에 배치된 경우에는 충돌이 발생하고, 두 사람의 스트레스 지수의 합만큼 비용이 발생한다. 방에 사람을 적당히 배치해서 비용의 합을 최소화 하는 문제이다. 단, 같은 그룹끼리는 서로 연결되어 배치되어 있어야 하고, 한 그룹에는 5명 이상의 사람이 속해있다.

  문제를 생각하기 용이하게 해주도록 배치의 비용을 다르게 나타내어 보자. 사람을 기준으로 생각했을 때, 해당 사람이 만드는 충돌의 개수는, 그 사람에게 인접한 다른 색을 가진 사람의 개수랑 같다. 그렇기 때문에, 총 비용은 모든 사람의 (해당 사람과 인접한 색이 다른 사람 수)×(해당 사람의 스트레스 지수)의 합이다.

  이제 정답이 가질 수 있는 배치를 생각 해 보자, 첫번째로 2×M 모양에서 첫번째 열과 마지막 열은 특수하게 다루어져야 하는데, 그룹의 경계를 생각할 때 가장 왼쪽 혹은 가장 오른쪽 열은 그룹의 경계이지만 충돌이 발생하지는 않는다. 그렇기 때문에, 우리는 이 두 열에 대한 특수한 배치를 증명할 것이다.

- 첫번째 열과 마지막 열의 두 사람이 같은 그룹인 정답이 존재한다.

  만약에 첫번째 열을 차지하는 두 그룹이 다른 사람인 정답이 존재한다고 하자. 이 둘은 크기가 더 작은 그룹이 존재한다. 해당 그룹을 A라고 하자. 모든 그룹은 연결되어야 하기 때문에, A는 일직선으로 존재하고 B도 A의 맞은 편 행에 일직선으로 존재하게 된다. (A가 끝난 이후에는 아무렇게나 존재할 수 있다.) 각 사람에 대해서 다음 그림과 같이 번호를 붙이자. (A3가 A의 가장 왼쪽 사람, A2, A1이 A의 가장 오른쪽 사람, A1의 오른쪽 사람이 C이고, B1, B2가 B의 가장 왼쪽 사람, B3가 A1의 맞은편 행에 있는 사람이다.)

  여기서 연결관계가 바뀐 사람들의 비용차이를 계산 해 보자. 여기서 B와 C가 같은 그룹일 수 있음에 유의하여라.

    * A1: 발생하는 충돌이 1개 줄었다. (B3, C → B2)

    * A2: 발생하는 충돌이 1개 늘었다. (B1)

    * A3: 발생하는 충돌이 1개 줄었다. (B1)

    * B1: 발생하는 충돌이 1개 혹은 0개 늘었다. (A3 → A2, C)

    * B2: 발생하는 충돌이 1개 줄었다. (A1)

    * B3: 발생하는 충돌이 1개 줄었다. (B1)

    * C: 발생하는 충돌이 1개 혹은 0개 줄었다. (B1)

  바꿔서 코스트가 가장 커지는 경우는 발생하는 B1에서 발생하는 충돌이 1개 늘고, C에서 발생하는 충돌이 바뀌지 않는, B와 C가 다른 그룹인 경우이다. 이 경우를 상정하자.

  최초 배치에서, A1은 충돌이 2개 발생하고, A2는 충돌이 1개 발생했다. 그렇기 때문에 위의 답이 최적이려면 A2의 스트레스 지수는 A1의 스트레스 지수보다 크거나 같아야 한다. 또한, B1과 B2는 모두 충돌이 1개 발생했기 때문에, B1의 스트레스 지수가 B2의 스트레스 지수보다 작거나 같은 답이 존재한다. 이런 사항을 고려해보면, A1과 B1에서 발생하는 비용의 증가는 A2와 B2에서 발생하는 충돌의 감소가 모두 해결해 줄 수 있고, 추가로 A3와 B3 혹은 C에서 발생하는 충돌의 감소가 스트레스 지수를 더 줄여준다. 그렇기 때문에, 첫번째 열과 마지막 열의 두 사람이 같은 그룹인 정답이 존재한다.

  위와 같은 증명으로, 우리는 첫번째 열과 마지막 열의 두 그룹을 고정할 수 있다. 해당 그룹 전체에서 발생하는 스트레스 지수에 대해서 생각하자. 해당 그룹의 경계에서는 최소 두 명의 스트레스 지수가 발생한다. 홀수인 경우에는 (가장 작은 스트레스 지수)*2 + (2번째로 작은 스트레스 지수)가 되고, 짝수인 경우에는 (1, 2번째로 작은 스트레스 지수의 합)이 된다.

  이제 해당 그룹이 아닌 내부에 존재하는 그룹에 대해서 생각하자.

  - 해당 그룹이 두 열 이상에 대해 두 행의 방을 모두 차지하고 있는 경우. (2×2 방을 차지하고 있는 경우)

    두 열을 기준으로 왼쪽과 오른쪽으로 분리하게 되고, 왼쪽 경계와 오른쪽 경계에 있는 사람들이 충돌하게 된다. 해당 경계에 두 사람만 존재하는 것이 가능하므로, 왼쪽 경계에 두 사람 오른쪽 경계에 두 사람이 존재하는 경우가 해당 그룹이 가질 수 있는 경계의 최솟값이다.

    * 해당 그룹의 크기가 홀수일 경우, 한쪽 경계에는 두 행을 모두 차지하고, 다른쪽 경계에는 한 행만 차지하는 경우가 된다. (사진에 있는 2번째 그룹에 해당된다.) 이 경우, 경계에 스트레스 지수가 낮은 사람을 배치하면 해당 그룹의 스트레스 지수는 (가장 작은 스트레스 지수)*2 + (2, 3, 4번째로 작은 스트레스 지수의 합)이 된다.

   * 해당 그룹의 크기가 짝수일 경우, 양쪽 경계에서 두 행을 모두 차지하는 것이 스트레스 지수의 최솟값이다. 이 경우 해당 그룹의 스트레스는 (1, 2, 3, 4번째로 작은 스트레스 지수의 합)이 된다.

   * 해당 그룹의 크기가 짝수이지만, 양쪽에 와야하는 사람 수가 홀수라서 양쪽 경계에서 두 행을 모두 차지하지 못하는 경우가 있을 수 있다. 이 경우 그룹의 스트레스의 지수는 (1, 2번째로 작은 스트레스 지수의 합)*2 + (3, 4번째로 작은 스트레스 지수의 합)이다.

  - 해당 그룹이 한 열 이하에 대해 두 행의 방을 모두 차지하고 있는 경우.

    나머지 양 끝쪽에 존재하는 방에 대해서는, 충돌이 적어도 두 번 이상 일어나고, 칸 하나를 제외한 나머지 칸에 대해서도 충돌이 한 번 이상 일어나게 되기 때문에, 스트레스 지수의 합은 (1, 2번째로 작은 스트레스 지수의 합)*2 + (3, 4번째로 작은 스트레스 지수의 합) 이상이 되게 된다. 그러므로 해당 경우는 스트레스 지수가 위에 말한 경우보다 크게 된다.

  이제 위와 같은 상황이 가능한 배치가 존재하는지 확인 해 보자. 홀수 그룹의 방을 항상 두 개씩 인접해서 배치하는 전략을 사용하면, 위에서 말한 모든 그룹의 스트레스 크기를 최소화하는 배치를 할 수 있다. 이렇지 못하는 경우는, 홀수 크기의 그룹이 정확히 2개이며 왼쪽 끝과 오른쪽 끝에 가야하는 경우이고, 이 경우에는 양쪽에 와야 하는 사람 수가 홀수인 짝수 크기 그룹과 같은 형태로 배치할 수 있다.

  이 방법으로 오른쪽과 왼쪽 끝에 가야하는 그룹을 정하고, 나머지의 스트레스 지수를 더하는 방식을 사용하면 O(M³) 혹은 O(M²)의 시간복잡도가 발생하게 된다. 이제 이 과정을 최적화 하자.

  홀수 크기의 그룹이 정확히 2개이며, 왼쪽 끝과 오른쪽 끝에 가야하는 경우를 제외하고는, 각 그룹의 스트레스 크기는 최소화 되기 때문에 총 비용은 (두 그룹을 제외한 각 그룹의 가운데에서 스트레스 지수) + (두 그룹의 양쪽 끝에서 스트레스 지수)이며, 이를 다시 쓰면, (모든 그룹의 가운데에서 스트레스 지수) - (두 그룹이 양쪽 끝에 왔을 때 줄어드는 스트레스 지수의 양)이 된다. 각 그룹의 양쪽 끝에 왔을 때 줄어드는 스트레스 지수의 양은 고정되어있기 때문에, 이 중 최댓값 두 개를 골라서 전체 스트레스 지수에서 빼주는 방식을 사용하면 총 O(N+M)의 시간복잡도를 얻을 수 있다.

문제의 조건 중에, 각 그룹끼리 연결될 것과, 그룹의 크기가 5이상일 것이라는 조건이 있다. 왜 이런 조건이 존재하는지는 다음과 같은 예제로 알아볼 수 있을 것 같다.

5. 차이

  문제를 요약하면, 쿼리가 다음과 같이 두 종류 들어오고, 2번 종류 쿼리에 대해 답을 해야한다.

  - 1번: i, j, v가 주어진다. 이는 X_i-X_j=v라는 정보를 의미한다.

  - 2번: i, j가 주어진다. 지금까지 1번 쿼리로 들어온 정보들을 토대로 X_i-X_j의 값을 계산해야 한다. 여기서 계산이라고 함은 다음과 같은 과정으로만 재귀적으로 정의된다.

    * X_i-X_j=v나 X_j-X_i=-v가 1번 쿼리로 주어졌다면, X_i-X_j=v라고 계산할 수 있다.

    * X_i-X_j=v와 X_j-X_k=u라고 계산할 수 있으면, X_i-X_k=v+u라고 계산할 수 있다.

  위의 과정을 (유한번) 재귀적으로 사용해서, X_i-X_j의 값을 계산할 수 있는지와, 계산할 수 있다면 계산 결과가 유일한지를 판단하여라. (1번으로 주어진 정보에 모순이 존재할 수도 있다.)

  위와 같은 문제에서, X_i-X_j의 값을 계산할 수 있는지를 먼저 살펴보자. 계산에 관한 정보를 빼고 보면, 위의 설명은 i와 j가 연결되어있는지 아닌지에 관한 설명이다. 그렇기 때문에, 잘 알려진 Disjoint-set과 같은 알고리즘을 사용해서 문제를 해결할 수 있다.

  이제, 값을 계산해 보자. Disjoint-set알고리즘은, 트리에서 자신의 부모 노드를 가지고 있는 알고리즘이다. 그렇기 때문에, 자신의 부모 노드와 자신과의 차이를 누적하면, 자신과 루트 노드의 차이를 알 수 있다. Disjoint-set알고리즘 상의 트리에서 노드 i의 부모가 p이고 루트가 r인 경우에, X_r-X_p는 재귀적으로 구할 수 있고, X_p-X_i는 Disjoint-set에서 자기 부모를 저장하는 배열에 자기 부모와 자기 자신의 차이를 추가적으로 저장해서 차이를 구할 수 있다. 2번 쿼리가 들어왔을 때, i와 j가 같은 연결성분에 들어있지 않다면, 값을 계산할 수 없다. 하지만 같은 연결성분 안에 있다면, X_r-X_i와 X_r-X_j를 계산해서 (X_r-X_j)-(X_r-X_i)이 답이 된다.

  이제, 1번 쿼리를 생각해 보자. 하는 과정에서, 서로 다른 두 연결성분에 들어 있으면, 해당 두 연결성분을 X_i-X_j=v라는 관계로 추가로 연결 해 주면 된다. 하지만, 같은 연결성분에 들어있는 경우 계산 결과에 모순이 발생할 수 있다. 이 때는, X_i-X_j=v가 맞는지 2번 쿼리와 같은 방법으로 실제로 확인해 주고, 모순이 발생한 경우에는 해당 연결성분 전체에서 모순이 발생한다고 생각할 수 있다. i,j를 포함하는 X_i-X_j의 결과로 두 개 이상의 답이 존재하는 경우에는 같은 연결 성분에 속한 a, b에 대해서도 X_a-X_i + X_i-X_j + X_j-X_b = X_a-X_b의 결과가 두 개 이상이 된다. 그렇기 때문에 루트노드 쪽에 해당 연결성분에 모순이 발생하는지 아닌지를 체크해 주면 된다. 시간 복잡도는 Disjoint-set 알고리즘과 같은 O(Mα(M)) 이다.

  아래는 문제에 대한 코드이다.

1번

#include <cstdio>
#include <vector>
using namespace std;

int solve(const vector<int>& V)
{
    int N = (int)V.size();
    int ans = 0;
    for(int i=0; i<N; ++i)
        if(i + V[i] >= N) ++ans;

    return ans;
}

int main()
{
    int T; scanf("%d", &T);
    for(int t=1; t<=T; ++t)
    {
        int N; scanf("%d", &N);
        vector<int> V(N);
        for(int i=0; i<N; ++i) scanf("%d", &V[i]);

        printf("Case #%d\n%d\n", t, solve(V));
        fflush(stdout);
    }
}

2번

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string solve(int T, const string &B)
{
    int N = (int)B.length();
    string A(N, '1');
    for(int i=0; i+T<N; ++i)
    {
        if(B[i+T] == '0') A[i] = '0';
        if(B[i] == '0') A[i+T] = '0';
    }
    for(int i=0; i<N; ++i) if(A[i] == '1')
        if(i-T < 0 || (i-2*T >= 0 && A[i-2*T] == '1'))
            if(i+T >= N || (i+2*T < N && A[i+2*T] == '1'))
                A[i] = '0';
    return A;
}

int main()
{
    int TC; cin >> TC;
    for(int t=1; t<=TC; ++t)
    {
        int N, T; cin >> N >> T;
        string B; cin >> B;
        cout << "Case #" << t << '\n' << solve(T, B) << endl;
    }
}

3번

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

enum State {WHITE, BLACK, GRAY};

bool dfs(const vector<vector<int>>& conn, vector<State>& visit, int a)
{
    if(visit[a] == BLACK) return false;
    if(visit[a] == GRAY) return true;

    visit[a] = GRAY;
    for(int x: conn[a])
        if(dfs(conn, visit, x))
            return true;
    visit[a] = BLACK;

    return false;
}

bool hasCycle(const vector<vector<int>>& conn)
{
    vector<State> visit(conn.size(), WHITE);
    for(int i=0; i<(int)conn.size(); ++i)
        if(dfs(conn, visit, i))
            return true;
    return false;
}

string solve(int N, vector<pair<int, int> > O, vector<pair<int, int> > U)
{
    vector<vector<int> > conn(N);
    for(auto [u, v]: O) conn[u-1].push_back(v-1);

    string ans;
    for(auto [u, v]: U)
    {
        --u; --v;
        conn[u].push_back(v);
        if(hasCycle(conn))
        {
            conn[u].pop_back();
            conn[v].push_back(u);
            ans += '1';
        } else ans += '0';
    }
    return ans;
}

int main()
{
    int T; cin >> T;
    for(int t=1; t<=T; ++t)
    {
        int N, M, K; cin >> N >> M >> K;
        vector<pair<int, int> > O, U;
        for(int i=0; i<M; ++i)
        {
            int a, b; scanf("%d%d", &a, &b);
            O.emplace_back(a, b);
        }
        for(int i=0; i<K; ++i)
        {
            int a, b; scanf("%d%d", &a, &b);
            U.emplace_back(a, b);
        }
        cout << "Case #" << t << '\n' << solve(N, O, U) << endl;
    }
}

4번

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

long long solve(vector<vector<int>> V)
{
    vector<pair<int, int> > O; // stress, lift
    vector<tuple<int, int, int> > E; // stress, lift, special
    for(auto& x: V)
    {
        sort(x.begin(), x.end());
        if(x.size()%2 == 0)
        {
            int stress = x[0] + x[1] + x[2] + x[3];
            int lift = x[2] + x[3];
            int special = x[0]*2 + x[1]*2 + x[2] + x[3];
            E.emplace_back(stress, lift, special);
        }
        else
        {
            int stress = x[0]*2 + x[1] + x[2] + x[3];
            int lift = x[2] + x[3];
            O.emplace_back(stress, lift);
        }
    }

    long long ans = 0;

    if(O.size() != 2 || E.size() != 0) // handle normal case, careful not to include OE...EO
    {
        vector<int> lifts;
        for(auto [st, li, sp]: E) lifts.push_back(li);
        if(O.size() == 2) lifts.push_back(max(get<1>(O[0]),get<1>(O[1])));
        else for(auto [st, li]: O) lifts.push_back(li);
        sort(lifts.rbegin(), lifts.rend());

        for(auto [st, li, sp]: E) ans += st;
        for(auto [st, li]: O) ans += st;
        ans -= lifts[0] + lifts[1];
    }

    if(O.size() == 2) // special case
    {
        long long spc = 0;
        for(auto [st, li, sp]: E) spc += sp;
        for(auto [st, li]: O) spc += st-li;
        if(ans == 0) ans = spc;
        else ans = min(ans, spc);
    }

    return ans;
}

int main()
{
    int T; scanf("%d", &T);
    for(int t=1; t<=T; ++t)
    {
        int N, M; scanf("%d%d", &N, &M);
        vector<vector<int> >V(N);
        for(int i=0; i<N; ++i)
        {
            int s; scanf("%d", &s);
            V[i].resize(s);
            for(int j=0; j<s; ++j) scanf("%d", &V[i][j]);
        }
        printf("Case #%d\n%lld\n", t, solve(V));
    }
}

5번

#include <cstdio>
#include <vector>
using namespace std;

struct UFD
{
    vector<pair<int, long long> > ufd;
    explicit UFD(int N): ufd(N) {
        for(int i=0; i<N; ++i) ufd[i] = {i, 0LL};
    }
    bool isValid(int x)
    {
        return ufd[Find(x).first].second == 0LL;
    }
    void setInvalid(int x)
    {
        ufd[Find(x).first].second = -1LL;
    }
    pair<int, long long> Find(int a)
    {
        auto [p, u] = ufd[a]; // x[p]-x[a] = u;
        if(a == p) return {p, u};

        auto [r, v] = Find(p); // x[r]-x[p] = v;
        return ufd[a] = {r, u+v};
    }

    void Union(int a, int b, int t)
    {
        auto [pa, va] = Find(a); // x[pa]-x[a] = va
        auto [pb, vb] = Find(b); // x[pb]-x[b] = vb
        if(!isValid(a) || !isValid(b))
        {
            ufd[pb].first = pa; setInvalid(pa);
        }
        else if(pa == pb)
        {
            if(vb-va != t) setInvalid(pa);
        }
        else ufd[pb] = {pa, va-vb+t};
    }

    enum Cases {No, Yes, Any};
    pair<Cases, long long> diff(int a, int b)
    {
        auto [pa, va] = Find(a); // x[pa]-x[a] = va
        auto [pb, vb] = Find(b); // x[pb]-x[b] = vb
        if(pa != pb) return {Any, 0LL};
        else if(!isValid(a)) return {No, 0LL};
        else return {Yes, vb-va}; // vb-va = (x[p]-x[b])-(x[p]-x[a]) = x[a]-x[b]
    }
};

void solve()
{
    int N, Q; scanf("%d%d", &N, &Q);
    UFD ufd(N);
    while(Q--)
    {
        int c; scanf("%d", &c);
        if(c == 1)
        {
            int u, v, t; scanf("%d%d%d", &u, &v, &t);
            ufd.Union(u-1, v-1, t);
        }
        else
        {
            int u, v; scanf("%d%d", &u, &v);
            auto [res, val] = ufd.diff(u-1, v-1);
            if(res == ufd.No) puts("CF");
            else if(res == ufd.Any) puts("NC");
            else printf("%lld\n", val);
        }
    }
    return;
}

int main()
{
    int T; scanf("%d", &T);
    for(int i=1; i<=T; ++i)
    {
        printf("Case #%d\n", i);
        solve();
    }
}