취미로 코딩하기

※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.

개요

PS/CP에서 주어지는 그래프 중 정점이 많이 주어지는(10만개 이상) 그래프는 대부분 sparse하다는 점을 의식해본 적이 있을 것이다. 시간 제한 내로 그래프가 dense해질 정도로 에지를 입력을 통해 많이 줄 수 없기 때문이다. 그렇다면 이 sparse하다는 점을 파고드는 문제해결전략도 있을 것이라는 생각이 이어서 든다.

이 글에서는 그래프의 밀도와 관련된 지표 중 하나인 deneneracy를 설명한다. 그리고 이와 관련된 degeneracy ordering을 소개하고, PS에서 이를 활용하는 해결할 수 있는 대표적인 문제인 counting 3-cycle과 counting 4-cycle 문제를 살펴본다.

이 내용을 이해한다고 바로 PS/CP 실력이 증가하거나 하지는 않겠지만, 이후에 그래프 관련 개념을 공부하거나 문제를 풀 때 조금 더 넓은 시야를 가지고 접근하는 등 도움이 될 것이라고 생각한다.

Degeneracy, \(k\)-core

\(G\)의 모든 subgraph의 "degree가 가장 작은 정점"의 degree가 \(k\) 이하일 때 \(G\)를 \(k\)-degenarate graph라 한다.

또한, 그래프 \(G\)가 주어질 때, \(G\)의 부분그래프 중 "degree가 가장 작은 정점"의 degree가 가장 큰 부분그래프가 존재할 것이다. 그러한 부분그래프의 크기를 \(G\)의 degeneracy라고 정의한다. 즉, \(G\)의 degeneracy는 \(G\)가 \(k\)-degenerate graph가 되게 하는 \(k\)의 최솟값이다. 또한 degree가 가장 작은 정점의 degree가 \(k\)인 \(G\)의 maximal한 connected subgraph들을 각각 \(k\)-core이라고 부른다.

degeneracy는 주어진 그래프에서 모든 정점의 degree가 degeneracy \(k\)이상인 부분(\(k\)-core)이 그래프에 있다는 것을 보여주는 값이므로, 이를 통해 그래프의 부분밀도에 대한 정보를 간접적으로 알 수 있다.

※주의: 당연하지만, \(k\)-core의 형태가 complete graph일 필요는 없다. complete graph의 형태가 아닌 \(k\)-core의 가능한 형태 중 하나로 regular graph가 있다.

한편, 어떤 그래프의 간선의 개수가 \(E\)라면 이 그래프의 degeneracy는 \(O(\sqrt{E})\)이 됨을 관찰하자. degeneracy가 \(k\)인 그래프는 정점이 \(k+1\)개인 complete graph이므로 \(\frac{k(k+1)}{2}\)개의 간선이 필요하기 때문이다.

Degeneracy Ordering, Coloring Number

※여기서 말하는 coloring number은 chromatic number과 다른 개념이므로 유의하자.

그래프의 degeneracy를 계산하는 것은 어렵지 않다. 가장 degree가 작은 정점을 지우는 것을 반복하면서, 매 순간의 최소 degree 정점의 degree 중 최댓값을 구하는 찾으면 된다. 이해와 증명 모두 직관적이므로 자세한 설명은 생략한다. 이 과정에서 지워지는 정점의 순서를 degeneracy ordering이라고 한다.

degeneracy ordering의 특징은 각 정점에 대하여 이후에 등장하는 정점의 수가 전체 그래프의 degeneracy \(k\) 이하라는 것이다.

degeneracy ordering의 역순으로 각 정점을 지금까지 색칠된 인접 정점을 칠하는 데에 사용되지 않은 색을 칠해나가는 전략을 생각해보자. degeneracy ordering의 특징을 잘 생각해보면 색칠할 차례의 각 정점에 대하여 그보다 앞 순서에서 색칠된 인접한 정점의 개수는 많아야 \(k\)개이므로 많아야 \(k+1\)개의 색으로 인접한 정점의 색이 다르게 그래프의 정점을 색칠할 수 있음을 알 수 있다. 이러한 이유에서 \(k+1\)을 coloring number라고 부르기도 한다. 다만 이름이 chromatic number(인접한 정점의 색이 다르게 그래프의 정점을 칠하기 위해 필요한 색의 최소 개수)와 혼동되기 쉬우므로 이 이름으로 자주 부르지는 않는다.

Counting 3-cycles

이제 degeneracy ordering을 활용하여 해결할 수 있는 문제인 counting 3-cycles를 소개한다. counting 3-cycles 문제는 다음과 같은 문제를 말한다.

정점이 \(V\)개이고 간선이 \(E\)개(self-loop, duplicate edge 없음)인 무방향그래프 \(G\)가 있다. 이 그래프에서 찾을 수 있는 3-cycle(세 개의 정점으로 구성된 cycle)은 총 몇 개인가?

\(N\) 또는 \(E\)가 10만 이상인 그래프가 입력으로 주어지면 위 문제를 간단한 방법으로 해결하기는 쉽지 않아보인다. 그러나 문제의 형태가 매우 단순하다 보니 다양한 풀이가 존재하는 문제이기도 하다. 이 글에서는 degeneracy ordering을 이용한 방법을 알아보자.

주어진 그래프가 DAG가 되게끔 각 간선에 방향을 임의로 부여해보자. 이 때, 원래 그래프에서의 3-cycle은 항상 (cycle 위에서) indegree가 2인 정점 \(A\), indegree와 outdegree가 각각 1인 정점 \(B\), outdegree가 2인 정점 \(C\)로 구성된다.

그렇다면, 주어진 그래프의 모든 간선에 대하여 그 간선의 양 끝 정점과 (DAG에서) 인접한 정점을 찾는 것을 반복하는 것으로 각 cycle을 \(A\)와 \(B\)를 잇는 간선이 선택되었을 때 정확히 한 번 셀 수 있다.

이제, DAG를 degeneracy ordering을 활용하여 구성해보자. 각 간선의 방향을 degeneracy ordering 기준 먼저 오는 정점에서 나중에 오는 정점으로 향하게 설정하면, 각 정점의 outdegree는 그래프의 degeneracy \(k\) 이하가 된다. 또한 설명했듯이 \(k\)는 \(O(\sqrt{M})\)이다.

따라서 위에서 구성한 알고리즘은 degeneracy ordering을 활용하여 구성한 DAG에서 각 간선 선택의 경우의 수 \(E\)에 대하여 두 정점과 인접한 공통 정점집합 찾기를 각각 \(O(\sqrt{M})\)에 해낼 수 있다.

따라서 degeneracy ordering을 활용하면 counting 3-cycle 문제를 \(O(M\sqrt{M})\)에 해결할 수 있다.

Counting 4-cycles

3-cycle의 경우와 비슷한 방법으로 counting 4-cycles 문제도 정의 및 해결할 수 있다. counting 4-cycles 문제는 다음과 같은 문제를 말한다.

정점이 \(V\)개이고 간선이 \(E\)개(self-loop, duplicate edge 없음)인 무방향그래프 \(G\)가 있다. 이 그래프에서 찾을 수 있는 4-cycle(네 개의 정점으로 구성된 cycle. 구성 간선의 집합이 다르면 다른 cycle이다.)은 총 몇 개인가?

3-cycle의 경우와 다르게, 4-cycle은 DAG 위에서도 다양한 형태로 나타날 수 있다. 특히, (원래 그래프에서의) 4-cycle은 (DAG에서의) indegree가 2인 정점의 개수가 1개일 수도 있고 2개일 수도 있다. 그러니 각 4-cycle을 한 번씩만 세려면 조금 더 구체적인 조건을 세워야 할 것이다.

이러한 조건을 세우는 방법 중 하나로 indegree가 2이면서 맞은편에 있는 정점의 degeneracy order보다 큰 order를 가지는 정점을 갖는 4-cycle만을 세는 것이 있다.

이러한 4-cycle은 그래프의 각 정점(이것이 indegree가 2인 찾고자 하는 정점의 맞은편 정점이다)으로부터 "원래 그래프에서의" 인접 정점을 찾고, 그 정점에서 이어서 DAG에서의 degeneracy order가 첫 정점보다 더 큰 인접 정점(이것이 indegree가 2인 찾고자하는 정점이다)들을 조사하는 것으로 모두 셀 수 있다.

위 알고리즘에서, 무방향그래프에서의 인접 정점을 찾는 횟수는 \(O(M)\)이며 각 정점에서 인접 정점을 조사하는 과정은 \(O(\sqrt{M})\)이다. 따라서 이 알고리즘의 최종 시간복잡도는 \(O(M\sqrt{M})\)이 된다.

여담

이 글에서 소개한 내용 말고도, degeneracy ordering은 그래프의 모든 maximal clique를 효율적으로 탐색하는 알고리즘인 Bron-Kerbosch 알고리즘의 최적화에 쓰이는 등 다른 곳에서도 사용하는 개념이다. 언젠가 clique 관련된 글을 작성하게 된다면 같이 소개하지 않을까....

3-cycle과 4-cycle을 셀 때, degeneracy ordering이 아닌 다른 ordering을 이용하기도 한다. PS/CP에서 널리 쓰이는 ordering 중 하나로 각 정점들을 degree가 \(\sqrt{M}\) 이상인 정점과 미만인 정점으로 나누어 degree가 낮은 정점들에 낮은 order를 부여하고 degree가 높은 정점에 높은 order를 부여하는 방법이 있다. degree가 낮은 정점의 outdegree는 많아야 \(\sqrt{M}\)이 되며, degree가 높은 정점은 그래프에 많아야 \(O(\sqrt{M})\)개이므로 degree가 높은 정점의 outdegree 또한 많아야 \(\sqrt{M}\)이 됨을 관찰하자.

특정 형태의 그래프의 개수를 세는 문제를 해결할 때, bitset을 활용한 최적화를 시도하는 것도 좋은 방법이 될 수 있다.

관련 문제

[BOJ3528] K-Graph Oddity

degeneracy ordering을 이용한 정점 채색법을 활용해보자.

이 글의 흐름에서는 살짝 벗어나지만, 이 문제와 관련된 더 많은 내용을 알고 싶다면 Brooks' Theorem과 Δ-coloring을 찾아보자.

[BOJ1762] 평면그래프와 삼각형

planar graph의 degeneracy는 5 이하임을 증명하고, 이를 활용해 문제를 해결해보자.

위 degeneracy의 상한을 이용하면 \(O(M\sqrt{M})\)으로 풀리지 않을 정도로 \(M\)이 커져도 충분히 문제를 해결할 수 있음을 알 수 있다.

[BOJ33946] 부도덕한 그래프 (Hard)

DAG에서의 세 정점이 이룰 수 있는 관계를 잘 생각해보자.

[BOJ32395] 4-cycle (Hard)

4-cycle을 세는 기본 문제이다.

[BOJ2390] ⎐

4-cycle에 뭔가가 더 붙은 그래프도 세어보자.

[BOJ28200] 4

비슷한 방법으로 4-clique 또한 셀 수 있다.

[BOJ31185] Ancient Magic Circle in Teyvat

포제원리를 활용하면 4-anticlique 또한 셀 수 있다.

참고 자료

https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)

https://dl.acm.org/doi/10.1145/2402.322385

https://www.cs.cornell.edu/courses/cs6241/2019sp/readings/Chiba-1985-arboricity.pdf : 그래프의 밀도와 관련된 또다른 지표인 arboricity의 개념을 이용하여 3-cycle 및 4-cycle counting을 계산하는 방법을 소개한다. arboricity와 degereracy는 많아야 2배 차이나는 지표이므로, 전반적인 흐름은 degeneracy를 활용한 것과 크게 다르지 않다.

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8551번 문제인 Blokada이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/8551

최소한 몇 개의 방향간선을 지워야 1번 정점에서 \(N\)번 정점으로의 연결된 경로가 없게 할 수 있는지를 묻는 문제이다.

이 값은 Max-Flow Min-Cut Theorem에 의해 각 간선의 가중치를 1으로 가정할 때의 1번 정점에서 \(N\)번 정점까지 흘릴 수 있는 최대 유량과 같다.

Dinic's Algorithm을 이용해 최대 유량을 구하고 문제를 해결하자. 모든 간선의 가중치가 1인 유량 그래프에서 Dinic's Algorithm의 시간복잡도는 \(O(\min(E\sqrt{E}, E\sqrt{V^{\frac{2}{3}}}))\)이므로 주어지는 입력의 크기가 상식적이라면 문제를 충분히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
using namespace std;

int ans, src, snk, N, M;
vector<int> G[10002];
bitset<10002> flow[10002];
int lv[10002], trn[10002];
queue<int> que;

bool dfs(int cur) {
    if (cur == snk) return 1;
    int sz = G[cur].size();
    for (int &i = trn[cur]; i < sz; i++) {
        int nxt = G[cur][i];
        if (lv[nxt] != lv[cur] + 1 || !flow[cur][nxt]) continue;
        if (dfs(nxt)) {
            flow[cur][nxt] = 0;
            flow[nxt][cur] = 1;
            return 1;
        }
    }
    return 0;
}

bool bfs() {
    memset(lv, 0, sizeof(lv));
    lv[src] = 1;
    que.push(src);
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (auto &nxt:G[cur]) {
            if (lv[nxt] || !flow[cur][nxt]) continue;
            lv[nxt] = lv[cur] + 1;
            que.push(nxt);
        }
    }
    return lv[snk];
}

void dinic() {
    while (bfs()) {
        memset(trn, 0, sizeof(trn));
        while (dfs(src)) ans++;
    }
}

void addedge(int x, int y) {
    flow[x][y] = 1;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    src = 1, snk = N;
    while (M--) {
        int x, y; cin >> x >> y;
        addedge(x, y);
    }
    dinic();
    cout << ans;
}

※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.

들어가기 전에

Sum Over Subsets DP, 줄여서 SOS DP는 PS/CP에서는 꽤 유명한 주제라고 생각한다. 이름값이 있는 알고리즘이다보니 글쓴이도 예전에 SOS DP를 익히려고 시도한 적이 있었으나, 그 때에는 개념을 읽어도 이를 적용해 해결할 수 있는 관련 문제를 제대로 찾지 못해 나중으로 미뤘었다.

앞으로 계속 익힐 주제들과 비교했을 때 SOS DP는 더 미루기에는 너무 유명한 주제라는 생각이 들었다. 더 미루지 말고 이런 생각이 든 김에 SOS DP와 그 관련 주제를 공부해 보자.

Submask Enumeration

원소가 \(K\)개인 집합 \(S\)의 각 부분집합 \(A\)는 \(K\)개의 비트를 이용하여 각 원소와 대응되는 비트를 키고 끄는 것으로 모두 나타낼 수 있다. 만약 \(S\)의 모든 각 부분집합 \(m\)에 대하여 각 집합의 모든 부분집합 \(m'\)에 접근하는 알고리즘을 설계한다면 총 몇 개의 \(m'\)에 접근하게 될까?

단순하게 생각하면, 부분집합의 개수가 가장 많은 \(S\)의 부분집합 \(m\)은 \(S\)이고 \(S\)의 부분집합의 개수는 \(2^K\)개이므로 일단 \(O(4^K)\)가 될 것이라고 생각할 수 있다. 그러나 실제로는 이보다 더 적은 \(3^K\)개의 \(m'\)에 접근하게 된다. 

\(A\)의 원소 \(k\)개인 부분집합은 \(\binom{K}{k}\)개이며, 각 부분집합은 \(2^k\)개의 부분집합을 가진다. 따라서 \(A\)의 원소 \(k\)개인 부분집합에서는 총 \(\binom{K}{k}2^k\)개의 \(m'\)에 접근하게 된다.

이를 모든 \(k\)에 대해 합하면 이항정리(binomial theorem)에 의해 \(\sum_{k=0}^K \binom{K}{k}2^k=3^K\)가 된다.

\(3^{17}\)이 129140163이므로, 제한시간이 넉넉하게 주어지는 문제의 경우 이러한 접근법으로 해결할 수도 있다.

참고로, bitmask를 활용하여 표현된 어떤 집합을 나타내는 정수\(x\)가 있을 때, \(x\)의 모든 부분집합은 초기값이 \(x\)인 변수 \(x'\)에 대하여 \(x':=(x'-1)\&x\)를 반복하는 것으로 모두 접근할 수 있다.

Sum Over Subsets DP

집합의 부분집합에 대한 몇몇 DP 문제는 위와 같은 접근으로 해결할 수 있지만, 모든 문제를 위와 같이 해결할 수 있는 것은 아니다.

Sum Over Subsets DP는 원소가 \(K\)개인 집합 \(S\)의 모든 부분집합 \(m\)에 대하여 대하여 \(f(m)\)의 값이 알려져 있을 때 \(\sum_{m'\subseteq m} f(m')\)의 값들을 \(O(K2^K)\)에 계산하는 동적 계획법 알고리즘이다.

각 부분집합 \(m\)과 원소의 인덱스 \(k\)에 대하여 \(dp(m, k)\)를 \(m\)의 부분집합 \(m'\)중 \(k\)를 초과하는 인덱스의 원소의 포함 여부는 \(m\)과 상태가 동일한 집합에 대한 \(f(m')\)의 합으로 정의하자. 그리고 초기값으로 \(S\)의 각 부분집합 \(m\)에 대하여 \(dp(m, -1)\)을 \(f(m)\)이라 정의하자.

\(dp(m, k)\)의 합을 구성하는 부분집합들을 인덱스 \(k\)의 원소를 포함하는 부분집합과 그렇지 않은 부분집합으로 나누어 생각해보자. "인덱스 \(k\)의 원소를 포함하는 부분집합"은 \(k\) 이상의 인덱스를 갖는 원소의 포함 여부가 \(m\)와 상태가 동일하다. 따라서 이 집합들의 \(f\)값의 합은 \(dp(m, k-1)\)와 같다. 그리고 "그렇지 않은 부분집합"의 \(f\)값의 합은 \(m\)에서 인덱스 \(k\)의 원소를 제거한 집합 \(m^*\)에 대하여 인덱스가 \(k\) 이상의 인덱스를 갖는 원소의 포함 여부가 \(m^*\)와 동일한 부분집합 \(m'\)들에 대한 \(f(m')\)의 합과 같다.

위의 관계를 식으로 나타내면 다음과 같다.

\(S\)의 부분집합 \(m\)에 대하여, \(m\)이 인덱스 \(k\)의 원소를 포함할 경우 \(dp(m, k) = dp(m^*, k-1) + dp(m,k-1)\)

\(m\)이 인덱스 \(k\)의 원소를 포함하지 않을 경우 \(dp(m, k) = dp(m, k-1)\)

구하고자 하는 값은 \(dp(S,K-1)\)이므로, 이를 계산하려면 위 형태의 점화식을 \(O(K2^K)\)회 계산하면 된다. 위 점화식을 이루는 연산은 단순 덧셈이니 \(O(1)\)에 실행할 수 있다. 따라서 점화식을 이루는 각 집합에 대한 접근이 O(1)에 이뤄질 수 있으면 이 알고리즘의 시간복잡도는 \(O(K2^K)\)가 된다. 이는 비트마스킹을 이용하여 간단히 해낼 수 있다.

정확히 위의 문제를 해결하고자 하는 경우, \(k\)값에 대한 모든 \(dp\)값을 계산한다면 \(k-1\) 이하의 값은 더 이상 필요없어지므로, \(k\)에 대해 순차적으로 계산하면서 각 \(k\)에 대하여 집합들을 적절한 순서로 방문하는 것으로 \(O(2^K)\)의 메모리를 활용해 문제를 해결할 수도 있다.

Sum Over Supersets DP

Sum Over Subsets DP는 원소가 \(K\)개인 집합 \(S\)의 모든 부분집합 \(m\)에 대하여 \(f(m)\)의 값이 알려져 있을 때 \(\sum_{m\subseteq m'\subseteq S} f(m')\)의 값들을 \(O(K2^K)\)에 계산하는 동적 계획법 알고리즘이다.

이 문제는 앞에서 살펴본 Sum Over Subsets DP와 완전히 동일한 방식으로 해결할 수 있다. 단순히 각 부분집합들을 \(S\)에 대한 여집합에 대응시키면 문제가 Sum Over Subsets DP와 동일해짐을 확인하자.

OR Convolution

두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i|j=m}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(|\)은 두 정수의 bitwise OR 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 OR Convolution이라고 한다.

편의를 위해, 집합 \(m'\)에 대하여 \(a_{m'}\)을 \(a\)의 "\(m'\)에 대응되는 비트마스크"번째 수로 정의하자.

그리고 두 함수 \(A\)와 \(B\)를 \(A(m)=\sum_{m'\subseteq m} a_{m'}\), \(B(m)=\sum_{m'\subseteq m} b_{m'}\)으로 정의하자.

이 때, \(A(m)\cdot B(m)\)의 값은 \( \sum_{m'\subseteq m} a_{m'} \cdot \sum_{m'\subseteq m} b_{m'} \)이 된다.

그리고 위의 값은 \(C(m)=\sum_{m'\subseteq m} c_{m'}\)의 값과 같다는 것을 어렵지 않게 알 수 있다.

\(a_n\)과 \(b_n\)으로부터 \(A\)와 \(B\)를 얻는 것은 SOS DP로 어렵지 않게 해낼 수 있다. 그렇다면 \(C\)로부터 \(c_n\)을 얻는 것은 가능할까? \(c_n\)으로부터 \(C\)를 얻는 것은 SOS DP를 통해 어렵지 않게 할 수 있으므로, 이를 거꾸로 수행하면 \(C\)로부터 \(c_n\)을 얻을 수 있다!

AND Convolution

두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i\&j=m}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(\&\)은 두 정수의 bitwise AND 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 AND Convolution이라고 한다.

AND Convolution 역시 위의 OR Convolution과 동일한 원리로 수행할 수 있다.

Subset Convolution

\(K\)값이 크지 않다면, 몇몇 문제는 \(O(K^22^K)\) 꼴의 시간복잡도 풀이를 갖기도 한다. 그 예시로 Subset Convolution을 소개한다.

두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i|j=m, i\&j=0}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(|\)은 두 정수의 bitwise OR 연산을, \(\&\)은 두 정수의 bitwise AND 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 Subset Convolution이라고 한다.

Subset Convolution이 OR Convolution과 다른 점은 \(i\&j=0\) 조건이 하나 추가된 것이 전부임을 확인하자. 이 점을 이용하면 Subset Convolution을 \(O(K^22^K)\)에 계산할 수 있다.

\(A(m, k)\)와 \(B(m,k)\)를 1인 비트의 개수가 \(k\)개인 \(m\)으로 나타나는 항의 값만을 이용한(나머지 항은 0으로 취급) \(a\)와 \(b\)에 대한 SOS DP의 결과라 하자. 그리고 \(C(m, k)=\sum_{k'=0}^{k}A(m,k')\cdot B(m,k-k')\)과 같이 정의하자. 이렇게 \(C\)를 정의하면 \(k\)가 \(m\)의 1인 비트 개수와 정확히 같을 때 \(A\)와 \(B\)에서 겹치는 비트가 없어야지만 OR 값으로 \(m\)이 정확히 나오게 강제할 수 있으므로, 각 \(k\)에 대하여 SOS DP의 undo하는 과정을 거치면 각 \(m\)에 대하여 \(m\)의 1인 비트 개수 \(k\)에 대해 (undo된) 값을 확인하는 것으로 Subset Convolution의 값을 모두 얻을 수 있다.

여담

bitmasking 문제를 만난다면 먼저 최대한 문제를 단순한 형태로 정리해보고, 두 mask 사이의 subset 관계를 활용하기 좋은 형태일 때 이 글의 내용을 풀이법 후보로 생각해보는 것이 좋다. 한편, mask 사이의 포함관계로 문제를 정리할 수 있는 경우더라도, Held-Karp Algorithm(bitmask TSP)이나 각 bitmask를 정점으로 하는 (방향)그래프에서의 BFS 등 더 쉽고 직관적인 방법을 활용할 수 있는지도 생각해보는 것이 좋다. 쉬운 방법으로도 문제를 해결할 수 있다면, 특히 대회에서는 문제를 굳이 어려운 방법으로 해결할 필요는 없다.

글쓴이의 글에서 소개한 접근 방식은 아니지만(그림 없이 다차원 누적합을 묘사하기 귀찮아서 생략했다), SOS DP를 \(K\)차원의 누적 합과 차이배열로 설명하기도 한다. 이 또한 흥미로운 내용이므로 알아두면 좋다.

관련 문제

이 글에서 Submask Enumeration을 설명하기는 했으나, 굳이 SOS DP로 안 풀어도 되는 제한의 문제를 SOS DP로 해결하는 것을 막으려는 목적으로 설명을 한 것이다. 또한 이 글에서 Subset Convolution을 설명하기는 했으나, 어디까지나 \(O(K^22^K)\)의 문제풀이 예시로 보여주기 위해서 설명했을 뿐 그 활용은 이 글의 범위를 넘는다.

아래의 문제들은 SOS DP, AND Convolution, OR Convolution과 관련된 문제들이다. 몇몇 문제는 Generating Function(생성함수)의 개념이 익숙하지 않다면 어려울 수 있다.

[BOJ25563] AND, OR, XOR

자기 자신에 대한 AND Convolution과 OR Convolution으로 AND와 OR의 경우를 해결할 수 있다. XOR의 경우는 간단하므로 생략한다.

[BOJ13759] &

Sum Over Superset DP의 결과가 나타내는 것이 무엇인지를 잘 생각해보자.

[BOJ23949] Shifts

각각의 guard에 대하여, 각 날 하루를 일했을 때의 \(H\)값을 초기값으로 넣고 Sum Over Subsets DP를 돌리면 나오는 결과가 무엇인지 생각해보자.

[BOJ2803] 내가 어렸을 때 가지고 놀던 장난감

각 장난감 상자는 사용하지 않거나 사용하므로, 각각 장난감의 사용 여부로 Sum Over Subsets DP를 한다면 convolution을 이용하여 문제를 해결할 수 있을 것이다. 그러나 각 장난감에 대하여 Sum Over Subsets DP를 사용하는 것은 당연히 무리다. 이를 최적화할 수 있을까?

[BOJ33102] Counting Pairs

조건을 만족하려면 각 비트의 상태가 어때야 하는지를 잘 생각해보자(1)

[BOJ18719] Binomial

조건을 만족하려면 각 비트의 상태가 어때야 하는지를 잘 생각해보자(2)

[BOJ30966] 관심사

원소의 개수가 가장 많은 공통부분집합이 무엇일까?

[BOJ27574] Digits of Unity

SOS DP와 그 역과정의 의미를 잘 생각해보자.

[BOJ25390] Traveling Junkman Problem

문제 풀이의 부분문제로 SOS DP가 사용될 수도 있다.

[BOJ27841] Problem Setting

주어진 전체집합의 부분집합을 이용해 만들 수 있는 chain의 경우의 수를 구해보자.

참고 자료

https://codeforces.com/blog/entry/45223

https://usaco.guide/plat/dp-sos

https://qwerasdfzxcl.tistory.com/35

https://37zigen.com/subset-convolution/

https://www.acmicpc.net/blog/view/127

https://codeforces.com/blog/entry/92153

https://codeforces.com/blog/entry/115438

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 34316번 문제인 사각형 개수 세기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/34316

\(NM\le10^5\) 제약조건을 눈여겨보자. 이 조건으로부터 \(\min(N,M)\le\sqrt{10^5}\)임을 알 수 있다. 이러한 형태로 문제에서 주어지는 입력에 추가적인 제한을 주는 경우는 제법 자주 나타나므로 잘 알아두는 것이 좋다.

\(N\)과 \(M\) 중 더 작은 값을 행의 개수로 하고, 두 개의 행을 골라 각 열의 두 행의 수의 합을 각각 구하는 작업의 시간복잡도는 \(O(\min(N,M)^2\max(N,M))=O(\min(N,M)NM)\)과 같다. \(NM\le10^5\)와 \(\min(N,M)\le\sqrt{10^5}\)가 성립하므로, 이와 같은 접근의 연산량은 1초 안에 충분히 수행 가능하는 점을 관찰할 수 있다. 여기까지 관찰했다면 이후의 계산은 어렵지 않을 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

int R, C;
vector<int> v[316];
ll ans;
int cnt[20];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    if (R < C) {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) cin >> v[r].emplace_back();
        }
    }
    else {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                cin >> v[c].emplace_back();
            }
        }
        swap(R, C);
    }

    for (int r1 = 0; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            memset(cnt, 0, sizeof(cnt));
            for (int c = 0; c < C; c++) {
                cnt[v[r1][c] + v[r2][c]]++;
            }
            for (int i = 2; i < 10; i++) ans += cnt[i] * cnt[20 - i];
            int v1 = cnt[10], v2 = v1 - 1;
            if (v1 & 1) v2 /= 2;
            else v1 /= 2;
            ans += v1 * v2;
        }
    }
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33922번 문제인 책 쌓기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/33922

먼저, 주어진 책들을 가로가 세로 길이 이상인 방향으로 일괄적으로 돌려 생각해도 충분하다는 점을 관찰하자. 가로가 세로 길이 이상인 책 위에 세로가 가로 길이 이상인 책을 얹을 수 있다면 문제 제약에 의해 위의 책을 회전시킨 책도 올릴 수 있으며, 이것이 그 위로 새로 올릴 수 있는 책의 집합을 바꾸지 않기 때문이다.

주어진 책들의 몇몇 쌍에 대하여, 어떤 책을 다른 책 위에 올릴 수 있다는 관계가 성립하며, 이 관계는 poset을 이룬다. 따라서 이 문제는 이 책들의 집합의 poset에서의 최대 antichain의 크기를 구하는 것으로 해결할 수 있다. 같은 antichain에 속한 두 원소는 항상 서로 비교가 불가능해야 하므로, 책을 적절하게 뽑아 적절히 나열했을 때 가로의 길이가 strict하게 증가할 때 세로의 길이 또한 strict하게 증가하게끔 뽑을 수 있은 최대 책의 개수를 구하면 문제가 해결된다.

위의 문제는 LIS를 구하는 것으로 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int N, ans;
int A[200001];
pair<int, int> P[200001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> P[i].first >> P[i].second;
        if (P[i].first < P[i].second) swap(P[i].first, P[i].second);
    }
    sort(P + 1, P + N + 1, greater<>());
    memset(A, 0x3f, sizeof(A));
    A[0] = 0;
    for (int i = 1; i <= N; i++) {
        int L = 0, R = i;
        while (L < R) {
            int mid = (L + R) / 2 + 1;
            if (A[mid] >= P[i].second) R = mid - 1;
            else L = mid;
        }
        A[L + 1] = min(A[L + 1], P[i].second);
    }
    ans = N;
    while (A[ans] == 0x3f3f3f3f) ans--;
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33921번 문제인 아름다운 수열이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/33921

전형적인 0-1 Fractional Programming 문제이다. 0-1 Fractional Programming에 대한 설명은 다음 공부 일지에 서술하였다.

https://measurezero.tistory.com/2371

글쓴이는 구현 연습 겸 이 문제를 Dinkelbach's Algorithm으로 해결했다. 계산 과정에서 64비트 정수 자료형의 오버플로우가 발생할 수 있으므로, 구현 과정에서 128비트 정수 자료형을 사용했다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll N, K, X, Y = 1, XX, YY;
ll A[100001], B[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> B[i]; A[i] = B[i] * B[i];
        A[i] += A[i - 1], B[i] += B[i - 1];
    }
    XX = A[N], YY = B[N];

    while ((lll)X * YY != (lll)Y * XX) {
        X = XX, Y = YY;
        lll val = 0, mx = 0; int qL = 0, qR = 0;
        for (int i = 0, lft = 0; i <= N - K; i++) {
            val += (lll)(A[i] - A[i - 1]) * Y - (lll)(B[i] - B[i - 1]) * X;
            if (val < 0) val = 0, lft = i + 1;
            lll v = val + (lll)(A[i + K] - A[i]) * Y - (lll)(B[i + K] - B[i]) * X;
            if (v > mx) mx = v, qL = lft, qR = i + K;
        }
        if (mx) XX = A[qR] - A[qL - 1], YY = B[qR] - B[qL - 1];
    }

    cout << X / Y << '.'; X %= Y;
    for (int k = 0; k < 10; k++) {
        X *= 10;
        cout << X / Y;
        X %= Y;
    }
}