KHSPC 뒷북 후기 + 비공식 에디토리얼 (2)

J번까지의 풀이를 포함한 이전 글은 여기서 확인할 수 있다. 지금은 바로 본론으로 들어가겠다.

대회 링크

에디토리얼

문제 번호는 본 대회 기준이며, 출제진 및 검수진이 쉽다고 느꼈던 문제일수록 앞쪽에 있다.

I. 쿠옹이의 궁금증

문제 링크

상당히 고통스러운(…) 구현 문제다. 정해가 좀 많은데, segment tree DP, 백트래킹, meet in the middle 등이 있다는 것 같다. 여기서는 내가 푼 방법인 meet in the middle 풀이를 소개한다.

대략 $M \leq 6$ 정도의 입력에서는 브루트포스로 문제를 풀 수 있다. $M \geq 7$일 때는 길이 $M$인 식이 모두 (수식)(연산자)(수식) 형태 또는 (수식)(연산자)(수)(연산자)(수식) 형태라는 것을 이용해 풀 수 있다. $M >\geq 7$ 이면 $N$의 범위 제한 때문에 연산자 없이 그냥 하나의 수인 경우는 없다.

1. (수식)(연산자)(수식) 형태

길이가 6 이하인 모든 식에 대해, 다음 경우의 수를 미리 구해두자.

• $count[i][j][k]$ := 길이가 $i$, 연산자 위치가 $j$인 식의 값이 $k$인 경우의 수

문자열이 0-based index라고 가정하고 예를 들면, $1+2+3$라는 식은 $i=5$, $j=(1, 3)$, $k=6$인 경우의 식에 해당한다.

이때 $k$ 값의 범위는 $-2.5 \cdot 10^5 \leq k \leq 2.5 \cdot 10^5$ 정도로 하면 된다. 이 범위 밖의 값을 갖는 식에 대해서는 경우의 수를 따로 세지 말자.

이제 위 형태를 만족하는 길이 $M$인 식의 경우의 수를 구하기 위해, 다음 조건을 만족하는 모든 식 길이의 쌍 $(\lvert l \rvert, \lvert r \rvert)$을 구하자. $\lvert l \rvert$은 왼쪽 수식의 길이, $\lvert r \rvert$은 오른쪽 수식의 길이이다.

• $\lvert l \rvert + \lvert r \rvert = M - 1$ (여기서 $\lvert x \rvert$는 식 $x$의 길이)
• $1 \leq \lvert l \rvert \leq 6$, $1 \leq \lvert r \rvert \leq 6$

아까 $count$를 구할 때 길이 정보뿐만 아니라 연산자 위치 정보까지 구했으므로, 이런 식으로 구한 식의 연산자 위치도 알 수 있다. 왼쪽 수식의 연산자 위치를 $j_l$라고 하고, 오른쪽 수식의 연산자 위치를 $j_r$라고 하자. 모든 $(\lvert l \rvert, \lvert r \rvert, j_l, j_r)$ 튜플 중 최종 식의 연산자 위치가 중복되지 않고 최종 수식의 값이 $N$인 경우의 수를 구하면 된다.

그런데 이러면 문제가 있다. 연산자가 수식 중앙에서 너무 멀리 떨어져 있는 식은 이 형태를 따르지 않는다. 예를 들면, $12+12345+12$ 같은 식은 위 방법으로 구할 수 없다. 구체적으로는, $M=11$ 기준으로 수식 정중앙 또는 정중앙에서 한 칸 떨어진 곳에 연산자가 있어야 한다. 이것 때문에 아래 방법도 필요하다.

2. (수식)(연산자)(수)(연산자)(수식) 형태

$M=11$일 때, 연산자가 수식 정중앙에서 두 칸씩 떨어져 있는 식을 생각해보면 $123+123+123$ 같이 왼쪽 식이 3글자, 오른쪽 식이 3글자로 나오는 것을 생각할 수 있다. 또한, $123+1234567$처럼 6자리 이상의 수가 나오는 식은 $N$의 제한 때문에 생각할 필요가 없다.

이를 종합하면, (수식)(연산자)(수)(연산자)(수식) 형태에서 왼쪽 부분 식의 길이가 1~3, 오른쪽 부분 식의 길이가 1~3인 경우에 대해 경우의 수를 구하면 된다. 왼쪽 식과 오른쪽 식의 값이 결정되면 가운데의 수는 자동으로 결정되며, 가운데 수의 길이가 $M - \lvert l \rvert - \lvert r \rvert - 2$인 경우만 경우의 수를 세서 더해주면 된다. 왼쪽 및 오른쪽 식이 가질 수 있는 값의 범위는 각각 절댓값 $10^\lvert l \rvert$, $10^\lvert r \rvert$ 내의 범위인 것을 고려하면 주어진 시간 내에 경우의 수를 구할 수 있다.

코드가 너무 길어서 여기 직접 적기는 힘들 것 같고, 여기에서 확인하자.

J. 부도덕한 그래프 (Hard)

문제 링크

두 가지 풀이가 있다. 하나는 sqrt decomposition이고, 하나는 bitset이다. 여기서는 둘 다 소개한다.

1. Sqrt Decomposition

처음 출제할 때 정해로 제안된 풀이다. ‘정점 $(x, y, z)$가 도덕적인 관계이다’라는 명제를 다음 세 조건을 모두 만족하는 것으로 정의하자.

1. 간선 $(x, z)$가 존재한다.
2. 간선 $(y, z)$가 존재한다.
3. 간선 $(x, y)$ 또는 간선 $(y, x)$가 존재한다.

그래프에서 (도덕적인 관계의 수) + (부도덕한 관계의 수)는 쉽게 구할 수 있다. 각 정점에 $v$에 대해, indegree $\deg_{in}(v)$를 구해서 $\deg_{in}(v) \cdot (\deg_{in}(v) - 1) / 2$를 모두 더하면 된다.

이제 여기서 도덕적인 관계의 수를 제외하면 된다. Naive하게 하면 다음과 비슷한 방법으로 구할 수 있다.

for x, z in edges:
    for y in adj_list_reverse[z]:
        if y in adj_list[x]:
            count += 1

adj_list_reverse는 주어진 그래프의 역방향 인접 리스트다. 이렇게 하면 최악의 경우 $O(M^2)$의 시간복잡도를 갖는다. 이를 sqrt decomposition 비슷한 아이디어를 이용해 $O(M \sqrt{M})$으로 줄일 수 있다.

for x, z in edges:
    if len(adj_list_reverse[z]) <= len(adj_list[x]):
        for y in adj_list_reverse[z]:
            if y in adj_list[x]:
                count += 1

    else:
        for y in adj_list[x]:
            if y in adj_list_reverse[z]:
                count += 1

adj_list_reverse는 주어진 그래프의 인접 리스트다. 이렇게 하면 시간복잡도는 아래와 같은 식이 된다

\[\sum_{(x, z) \in E} \min(\deg_{out}(x), \deg_{in}(z)) = O(M \sqrt{M})\]

증명은 다음과 같다. $\sum_{x \in V} \deg_{out}(x) = M$이므로, $\deg_{out}(x) > \sqrt(M)$인 정점은 많아야 $O(sqrt(M))$개이다. 그래프가 단순 그래프이므로, $\min(\deg_{out}(x), \deg_{in}(z)) > \sqrt{M}$인 간선은 많아야 $O(M)$개이다. 나머지 간선에서는 $\min(\deg_{out}(x), \deg_{in}(z)) \leq \sqrt{M}$이므로, 위 식이 성립한다.

저 증명은 jh05013님의 블로그 글에서 무방향 그래프를 방향 그래프로 바꾼 것 밖에 없다. 저게 왜 웰노운이야…

2. Bitset

본 대회에서 나온 유일한 풀이다. 1번 풀이와 (도덕적인 관계의 수) + (부도덕한 관계의 수)를 구하는 것까지는 동일하다. 그런데 이후 과정에서 bitset을 사용하면 엄청 빠른 $O(N^2)$ 풀이가 먹힌다.

우선, $N \times N$ 크기의 인접 행렬을 vector<bitset<50000>>으로 저장해둔다. 이때 원본 그래프와 역방향 그래프 모두 저장해둔다. 이제 각 정점 $z$에 대해, 다음과 같은 과정을 거친다.

for (int z = 0; z < n; z++) {
    for (int x : adj_list_rev[z]) {
        count += (adj_mat_rev[z] & adj_mat[x]).count();
    }
}

K. 특별한 정점

문제 링크

기본적인 아이디어와 증명은 정말 어려운데, 구현은 정말 쉽다. 다만 구현에서 실수할 부분이 아예 없진 않다.

기본적인 아이디어는 다음과 같다.

두 개의 특별한 정점 $u$, $v$에 대해 $u$에서 $v$로 가는 단순 경로에 속하는 모든 특별한 정점들을 하나의 집합으로 보자. 정답은 그러한 집합의 수가 최소가 되도록 나눴을 때의 집합의 수 -1개가 된다. (특별한 정점이 존재하지 않을 경우 0)

아직 작성중입니다.

L. 수열 재활용

문제 링크

작성 준비중입니다.

M. 🍕😋🤮

문제 링크

작성 준비중입니다.

정리

작성 준비중입니다.