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

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. 특별한 정점

문제 링크

에디토리얼 공유를 허락해 주신 iygav1238님께 감사드립니다.

출제자 분이 만들어 둔 에디토리얼을 참고하자.

매우 높은 발상 및 증명 난이도, 그리고 그와 대비되는 매우 낮은 구현 난이도가 인상적이었다.

L. 수열 재활용

문제 링크

문제 출제 시 썼던 에디토리얼을 참고하자. 솔직히 그렇게 잘 쓰진 못한 것 같아서 나중에 다시 써 볼까 한다.

그런데 저 에디토리얼의 해싱 풀이를 적용할 때, $N$, $M$, $A$의 범위 제한 상 64비트 정수 범위에서는 해시를 하나만 쓰면 거의 반드시 해시 충돌이 발생한다. 대략 3개 정도 쓰면 해시 충돌이 거의 발생하지 않는다. 또는, SA + LCP를 이용한 풀이도 가능하다.

개인적으로는, 모듈러를 먹인 차분 배열을 통해 뭔가를 처리할 수 있다는 초기 관찰이 제일 어려웠던 것 같다. 그 이후에는 라빈-카프 해싱을 어떻게 쓰는지만 안다면 크게 어렵진 않은 것 같다.

M. 🍕😋🤮

문제 링크

16993번 문제에서 사용하는 것과 완전히 같은 세그먼트 트리를 사용하면 피자가 원형이 아니라 선형일 때의 문제는 바로 풀린다. 구체적으로는, 다음과 같은 자료구조를 세그먼트 트리의 원소로 사용하면 된다.

struct Node {
    long long left;  // 구간의 왼쪽 끝을 포함하는 최대 연속합
    long long right; // 구간의 오른쪽 끝을 포함하는 최대 연속합
    long long total; // 구간의 전체 합
    long long max;   // 구간의 최대 연속합 (추가 조건 없음)

    Node(int idx) {
        left = right = total = max = a[idx];
    }
}

Node merge(const Node& a, const Node& b) {
    Node res;
    res.left = max(a.left, a.total + b.left);
    res.right = max(b.right, b.total + a.right);
    res.total = a.total + b.total;
    res.max = max({a.max, b.max, a.right + b.left});
    return res;
}

원형의 피자에서 구간을 선택할 때는, 다음 사실을 이용하면 된다.

• 연속된 피자 조각의 선호도의 합의 최댓값이 되게 하는 구간을 $A$라고 하자. $A$와 $A$의 여집합 중 적어도 하나는 $1$번 조각과 $N$번 조각의 경계를 포함하지 않는다.

$A$가 $1$번 조각과 $N$번 조각의 경계를 포함하지 않는다고 가정하면, 그냥 위에서 말한 것과 같이 선형 배열에서의 문제로 풀면 된다.

$A$의 여집합이 $1$번 조각과 $N$번 조각의 경계를 포함하지 않는다고 가정해보자. 이때는 $A$의 여집합의 연속합이 최소가 되게 한 후, 모든 피자 조각의 선호도 합에서 $A$의 여집합의 연속합을 빼면 된다. 다만 이때는 조건이 위와 살짝 달라진다.

1. 연속 최대 합 대신 최소 합을 구해야 한다.
2. 구간의 길이가 $0$이 될 수 있다.
3. 구간의 길이가 $N$이 될 수 없다.

1번이랑 2번은 세그먼트 트리의 원소를 약간 수정하면 된다. 3번은 구간 $[1, N]$에서 바로 연속합의 최솟값을 구하는 대신, $[1, N-1]$과 $[2, N]$에서 각각 연속합의 최솟값을 구한 후 둘 중 작은 값을 선택하면 된다.

정리

이 대회는 경희대학교에서 학생 주도로 열리는 최초의 PS 대회였다. 그리고 내가 처음으로 문제를 출제하고 운영진으로 참가한 대회다. 이걸 졸업한 뒤에야 처음으로 하게 될 줄은 몰랐긴 했는데… 지금 2학년인 후배가 대회 열려고 열심히 뛰어다니는 걸 보니까 많은 생각이 든다. 대학 다닐 때 좀 더 주도적으로 뭔가 했어야 됐겠다는 아쉬움도 남지만, 지금이라도 뭔가 한 게 다행일지도 모른다.

대회 운영이나 진행 중에 느낀 점이라면, 문제 난이도 조절을 좀 잘못한 것 같다. 대회 시작 이전에도 실버 상위 ~ 골드 중위 수준에 너무 많은 문제가 몰려 있는 것 아니냐는 의견이 좀 있긴 했다 (C~H). 그런데 본 대회에서는 그냥 너무 어려워서 문제였던 것 같다. 본 대회 참가자가 40명이었는데, 1솔 이상이 21명, 2솔 이상이 10명이었다. 상위권 참가자들은 나름 많이 풀긴 했는데, 대회 참가자 대부분이 2솔 이하라면 솔직히 의욕이 많이 꺾일 것 같긴 하다. 특히 B번 문제가 진짜로 2번째로 쉬운 문제이긴 한데 실수할 구석이 꽤 많아서 이런 결과에 큰 영향을 줬을 것 같다. 다음에 교내에서 이런 대회를 연다면 중하위 난이도 문제를 더 쉽게 내고 저난이도 문제에서는 case work나 예외처리 등 실수할 곳이 많이 없게 깔끔하게 풀리는 문제를 좀 늘려야 될 것 같다.

본 대회는 끝난 지 벌써 한 달쯤 됐긴 했다. 주최자 일정이랑 다른 대회 일정이랑 겹쳐서 본 대회 2주 뒤로 미뤄졌던 오픈 콘테스트도 끝난 지 좀 되긴 해서 이걸 이제야 올리는 게 맞나 싶긴 한데 지금이라도 써 보는 게 맞는 것 같다.