2020.05.27 problem solving

옛날에 어디 적어두었던 내용들을 공개합니다. 적어둔 시점이 달라서 문체 역시 문제마다 다를 수 있습니다. 유의해주세요. (사실 문체는 적어둔 시점이 같아도 달라지는 경우가 많긴 합니다...)

Codeforces #620 Div2B. Longest Palindrome

문자열의 길이가 같으니까 많은 문자열을 모아두면 됩니다.

모은 문자열의 개수가 짝수라고 가정하면, 해당 문자열, 그리고 그것을 뒤집은 문자열로 매칭되는 쌍을 최대한 많이 모아주면 됩니다. 모든 문자열이 다 다르고, 제한이 작기 때문에, 그리디하게 매칭해 주면 됩니다.

홀수라고 가정하면, 중간에 팰린드롬이 하나 와야 합니다. 모든 문자열이 다르니까 팰린드롬은 매칭에 들어가지 않습니다. 고로 매칭되지 않은 팰린드롬이 있었다면 중간에 끼워넣으면 됩니다.

AMPPZ 2019 A. Assimilation

문제 조건에 의해, 모든 조건은 “침략” 당하거나 “침략 후 동원” 당해야 합니다. 동원의 과정을 보면, 침략에 사용했던 모든 함선을 보상받을 뿐만 아니라 원래 있던 인구만큼의 추가적인 함선을 받을 수 있습니다. 고로 “침략 후 동원” 을 실시할 경우, 초기 자본금만 있으면 항상 이득을 볼 수 있습니다. 반면 어떠한 행성을 침략만 하는 것은 무조건 현재 함대의 개수를 줄이므로 손해입니다. 결국 어떠한 행성을 동원할 지 안 할 지의 여부가 결정되었다면, 맨 처음 동원하기로 결정한 행성들을 전부 동원한 후 나머지 행성들을 침략하는 것이 최적입니다 (도움이 되지 않는 침략을 서두를 이유가 없습니다).

나머지 행성들을 침략할 수 있다는 것은, 지금까지 남은 행성들의 인구 수 합이 현재 함선 개수 이하라는 뜻입니다. 고로, 이 차이를 최대한 빨리 줄이는 전략을 사용하는 것이 좋을 것입니다. X명이 있는 한 행성을 침략+동원하면, 현재 함선의 개수는 +X, 남은 인구수는 -X가 되니, 침략할 수 있는 행성 중 X가 가장 큰 행성을 침략하는 것이 최적 전략이고, 이를 반복하면 O(N^2) 알고리즘을 찾을 수 있습니다. 이를 $O(N\log N)$ 으로 최적화하려면, std::set 을 사용하면 됩니다.

NEERC 2012. Disjoint Regular Expression

주어진 정규식을 적절한 그래프로 변형한 후 문제를 해결할 것입니다. 그래프는 “source” 라는 정점과 “sink” 라는 정점이 있으며, 각 간선에 문자 하나가 적혀 있을 수도, 없을 수도 있습니다. 어떤 문자열이 정규식에 매칭된다는 것이, 이 그래프에서 source -> sink 로 가는 경로 중, 적혀있는 문자들을 모두 이었을 때 해당 문자열이 나오게 할 수 있다는 것과 동치가 되게끔, 그래프를 만들어 보겠습니다. 이 과정은 정규식의 생성 과정을 따라가면서 귀납적으로 진행됩니다 (structural induction).

• 하나의 소문자 c는 source -> sink를 잇는 c가 적힌 문자열이다.
• 선택 (P|Q) 은, P의 그래프와 Q의 그래프를 따로 구한 후, 새로운 source와 sink를 만들어, 이 그래프의 source / sink 를 빈 간선 4개를 사용해 각각 병렬적으로 잇는다.
• 연결 (PQ) 는, P의 그래프와 Q의 그래프를 따로 구한 후, P의 sink에서 Q의 source를 빈 간선으로 잇고, P의 source와 Q의 sink를 새로운 그래프로 둔다. (위의 경우에 대비해서 직렬 연결에 대응)
• Kleene star는, 새로운 정점 V를 만든 후, V -> source, sink -> V 로 가는 빈 간선을 만들고, V를 source이면서 sink라고 정의한다.

그래프를 만드는 과정은 문자열 파싱 후 parse tree를 따라가면서 적힌 대로 귀납적으로 하시면 됩니다. 이렇게 하면 대략 정점이 200개 정도 되는 그래프 두 개를 만들 수 있습니다. (이러한 알고리즘을 Thompson’s construction 이라 부르며, regex가 선형 시간에 선형 크기의 NFA로 변환된다는 구성적 증명입니다.)

이제, 두 정규식이 서로소가 아니라는 것은, 두 그래프에서 모두 source -> sink로 갈 수 있게끔 하는 문자열이 존재한다는 것입니다. 고로 최소 길이 문자열을 찾는 것은 최단 경로를 찾는 거에 대응됨을 알 수 있습니다.

이는 0-1 BFS를 사용하여 구할 수 있습니다. 두 그래프 상에서의 정점 위치를 pair로 저장한 후 탐색합니다. 새로운 문자를 붙이고 싶으면 같은 문자가 적혀있는 간선을 따라 두 정점을 모두 옮기고 (가중치 1), 그러고 싶지 않으면 한 정점을 빈 간선으로 옮기는 (가중치 0) 연산을 하면 됩니다. 두 그래프의 간선 개수 역시 정점 개수에 비례하기 때문에, 시간 복잡도는 제곱에 비례합니다.

POI 2012. Prefixuffix

문자열이 주어졌을 때 이를 $ABTBA$ 형태의 패턴으로 분할하고, $|A| + |B|$ 의 길이를 최대화하는 것입니다. 모든 가능한 $A$ 의 후보는 일반적인 실패 함수를 만들어주면, 전체 문자열에서 실패 함수를 계속 따라가면서 $|A| \le n/2$ 인 경우를 마킹해주는 식으로 쉽게 $O(n)$ 에 열거할 수 있습니다.

이제 $A$ 를 고정했을 때 $B$ 를 열거해 봅시다. 일반성을 잃지 않고, 문자열 $S$ 에서 $A$를 앞 뒤로 제거하고 생각해 봅시다. $S_0 = S_{N-k}, S_1 = S_{N-k+1}, \ldots, S_{k-1} = S_{N-1}$ 를 만족하는 최대 $k \le N/2$ 를 찾고 싶습니다.

문자열 $T = S_0 S_{N-1} S_1 S_{N-2} \ldots S_{k-1} S_{N-k}$ 와 같이 쓴다면, 이는 $T$의 최대 짝수 길이 팰린드롬 접두사를 찾는 것과 동일하다는 것을 알 수 있습니다. 이제 $A$를 제거하지 않고 생각해 보면, $T$의 모든 접미사에 대해서, 해당 접미사의 최대 짝수 길이 팰린드롬 접두사를 계산해 주면 된다는 것을 알 수 있습니다. 이 값을 어떻게 계산하면, $A$는 열거를 쉽게 할 수 있으니 전체 문제가 해결됩니다.

이 값은 접미사를 뒤에서부터 보면서 길이를 늘려가면서 계산해 줍시다. 지금 $S[i+1, n-1]$ 접미사에서 문제를 해결했고, $S[i, n-1]$ 접미사로 이를 확장시킨다고 생각해 봅시다. i+1 에서의 최적해 길이가 2p 였다면, i에서의 최적해 길이 역시 많아야 2p+2 입니다. 이는 단순한 귀류법으로 보일 수 있습니다. 고로 2p+2 에서 시작한 후 팰린드롬일 때까지 2씩 포인터를 줄여나가면, 최적 접미사의 끝부분이 이러한 과정에서 많아야 2n의 거리를 움직이기 때문에 전체 계산도 $O(n)$ 이 됩니다.

마지막으로, 문자열의 어떠한 부분문자열이 팰린드롬인지를 빠르게 확인해야 하는데, Manacher algorithm 이나 해싱을 사용하면 $O(n)$ 전처리, $O(1)$ 질의에 판별이 가능합니다. 고로 전체 문제가 $O(n)$ 에 해결됩니다.

NAC 2020 E. Grid Guardian

$N, M$이 모두 홀수이면, 행/열 번호가 짝수인 칸에 배정하면 되고, 그게 유일한 경우입니다. 고로 답은 1입니다.

둘 중 하나만 홀수라고 합시다. 행 개수가 홀수라고 하면, 행 번호가 짝수인 칸에만 배정할 수 있습니다. 이 안에 2개 이상의 연속된 열이 비지 않아야 하는데, 대략 .O.O.O.O|O.O.O.O. 와 같이 어떠한 경계 전후를 기점으로 짝수/홀수 칸에 전부 배정시키면 됩니다. 이러면 경계를 고정시키는 것이 경우를 바꾸는 유일한 수이니, 경계를 고정시키는 수 $N/2+1$ 을 $M/2$ 승하면 됩니다.

둘 다 짝수인 경우, 격자를 2x2 격자로 분할할 수 있습니다. 이 격자 안에 정확히 하나의 장애물을 배정해서, 빈 2x2 격자가 생기지 않도록 해야 합니다.

2x2 소격자에 대해서도, .O.O.O.O|O.O.O.O. 와 같은 룰이 적용됩니다. 왼쪽->오른쪽 순서로 보았을 때, 한번 장애물을 소격자의 왼쪽에 넣기 시작했으면 다시 돌이킬 수 없고, 위-> 아래 순서에서도 같은 논리가 통합니다. 이렇게 되었을 경우, 각 행에 대한 상태는 $O(2^{N/2} \times N/2)$ 개가 됩니다. 현재 각 소격자에서 장애물을 왼쪽/오른쪽에 넣었는지, 그리고 위->아래 로 내려갈 때 경계점이 어느 점을 기준으로 형성되어 있는지, 가 상태입니다.

상태 전이를 할 때는, 다음 상태가 현재 상태의 submask여야 하고, 다음 상태에서의 경계선이 어디 있느냐에 따라서 무조건 오른쪽에 넣어야 하는 소격자가 새롭게 생기는 등의 디테일이 생깁니다. 이러한 디테일을 전부 잘 고려할 경우, 전 상태/현재 상태의 경계선을 고정한 후, 다음 상태의 mask를 고정시키고 submask를 전부 순회하는 식으로 $O(3^{N/2}\times N^2)$ 시간에 다음 행으로 넘어갈 수 있습니다.

아직 문제를 해결하기 충분치 않습니다. 일단, submask를 전부 순회하며 뿌려주지 말고, 다음 상태에 대해서 현재 상태 bitmask의 supermask 상태의 합을 전부 계산해 줍니다. 이는 길이가 2인 $N$차원 공간에서의 부분합이라고 볼 수 있는데, 각 차원 (비트) 에 대해서 부분합 배열을 하나하나씩 만들어나가면 이 값을 알아낼 수 있습니다. 구사과 블로그, 혹은 구데기컵의 하이퍼 수열과 하이퍼 쿼리 문제를 참고하시면 좋습니다. 이렇게 하면 $O(2^{N/2} \times N^3)$ 시간 복잡도가 소모됩니다. 잘 구현하시면 이것만으로 통과하실 수 있습니다.

이후, 다음 행만 고정시킨 후, 이전 행의 상태들을 모두 열거한 이후 이들에 대해서 한꺼번에 부분합을 구해주시면, $O(2^{N/2}N^2)$ 시간 복잡도가 되어 총 시간 복잡도 $O(1.414^N N^2 M)$ 시간에 해결하실 수 있습니다.

2019 GP of Daejeon G. Good Set

문제에는 비트 연산으로 정의되어 있지만, 결국 $U = {0, 1, \ldots, 2^K - 1}$ 은 $V = {0, 1, \ldots, K - 1}$ 의 모든 부분집합과 동일하니, 이제 좋은 집합은 부분집합들의 집합 (set of subsets, family) 이라고 생각한다. 또한. 좋은 집합은 공집합과 전체 집합 ($V$) 를 포함한다고 가정한다. 실제로 이러한 가정이 성립하지는 않지만, 그렇지 않은 경우에는 좋은 집합 안에 들어 있는 모든 부분집합의 교집합과 합집합을 고정하고 문제를 해결하면 된다. 겉으로 보기에는 $3^K$ 배 느려질 것 같으나, 이렇게 해도 거의 시간 차이가 없다는 것을 아래에서 보인다.

어떠한 방향 그래프가 추이적 (transitive) 이라는 것은, 모든 정점 $u, v, w$ 에 대해서, $u \rightarrow v, v \rightarrow w$ 를 잇는 방향 간선이 있으면 $u \rightarrow w$ 를 잇는 방향 간선이 있음을 뜻한다. 이제 $V$ 를 정점 집합으로 하는 모든 추이적 방향 그래프와, 좋은 집합과의 일대일 대응이 있음을 보인다. 이러한 일대일 대응이 있으면, 이제 좋은 집합 대신 추이적 방향 그래프를 세어도 된다.

이제 일대일 대응을 찾는다. 어떠한 좋은 집합 T 에 대해서, u를 포함하는 집합들이 모두 v를 포함할 때 $u \rightarrow v$ 를 잇는 간선이 있는 그래프를 $f(T)$ 라고 하자. 간선이 있을 조건은 $(u\text{를 포함한다)} \rightarrow (v\text{를 포함한다})$ 가 모든 집합에 대해서 성립한다는 것과 동치이다. 고로 명제의 추이성에 따라서 $f(T)$ 는 추이적 방향그래프이다.

어떠한 추이적 방향 그래프 G에 대해서, 정점 부분집합 $A$ 에 있는 어떤 정점에서도 $A^C$ 를 향하는 간선이 없을 때 $A$ 를 포함하는 부분집합족 (family of subsets) 을 $g(G)$ 라고 하자. $A, B \in g(G)$ 일 때, $A \cap B, A \cup B \in g(G)$ 임을 간단한 케이스 분석으로 보일 수 있다. 고로 g(G) 는 좋은 집합이다.

일대일 대응을 보이기 위해서는, 추이적 방향 그래프 X와 부분집합 Y에 대해서, g(X) = Y, f(Y) = X가 동치임을 보이면 된다. 즉, $f(g(X)) = X, g(f(Y)) = Y$ 를 보이면 된다. 이를 보인다.

• Lemma 1. 만약 $f(Y)$ 에서 $u \rightarrow v$ 로 가는 간선이 없다면, $Y$ 에는 $u$ 를 포함하고 $v$를 포함하지 않는 부분집합이 존재한다.

  • Proof. 대우를 취하면 정의상 자명하다.

• Lemma 2. 만약 $f(Y)$ 에 $X \rightarrow X^C$ 로 가는 간선이 없다면, $X \in Y$ 이다.

  • Proof. 모든 $i \in X$ 에 대해, Lemma 1에 의해 $X^C$ 의 원소 중 하나를 포함하지 않고 i의 원소를 포함하는 집합을 찾을 수 있다. 좋은 집합의 성질에 따라, 이들의 교집합을 취하면 i를 포함하는 $X$의 부분집합을 찾을 수 있다. 이들의 합집합을 취하면 된다.

• Theorem 1. 모든 좋은 집합 T에 대해서, $g(f(T)) = T$ 를 만족한다.

  • Proof. $A \in T$ 이면, T의 밖으로 나가는 간선은 존재할 수 없다. 고로 $A \in g(f(T))$ 이다. $A \in g(f(T))$ 이면 $f(T)$ 에서 $T$의 밖으로 나가는 간선이 존재하지 않는다. 고로 Lemma 2에 의해 $A \in T$ 이다.

• Theorem 2. 모든 추이적 방향 그래프 G에 대해서, $f(g(G)) = G$ 를 만족한다.

  • Proof. $u \rightarrow v$ 간선이 있다면, u를 포함하고 v를 포함하지 않는 집합은 $g(G)$ 에 존재하지 않는다. 고로 $f(g(G))$ 에도 $u \rightarrow v$ 간선이 있다. $f(g(G))$ 에 $u \rightarrow v$ 간선이 있다면, $g(G)$ 에는 u를 포함하고 v를 포함하지 않는 집합이 없다. $g(G)$ 에서 u를 포함하는 최소 크기의 집합을 찾고 이를 X라 하자. 가정에 따라서 ${u, v} \subseteq X$ 이다. 또한, $X$의 비지 않으며 $X$가 아닌 부분집합에서는, 해당 부분집합에서 나가는 간선이 G에 무조건 존재한다. 이제 G에서, 너비 우선 탐색을 하듯이, 특정 집합 $S = {u}$ 에서 시작해서 S를 확장시켜 나가자. 각 확장 과정에서, $X$ 상에 있는 $S$ 의 임의의 정점과 연결된 정점을 추가해 나간다. 이 과정은 모든 정점을 추가할 때까지 멈추지 않으며, 고로 이 과정을 통해서 $u \rightarrow v$ 로 가는 경로를 찾을 수 있다. 추이성에 따라서 경로의 존재성은 간선의 존재성과 동치이다.

이제 좋은 집합에 대한 백트래킹이 아니라 추이적 방향 그래프에 대해서 백트래킹을 하면 되는 것으로 문제를 환원하였다. 또한, 특정한 집합이 좋은 집합 안에 들어가야 한다는 조건은, 특정한 간선을 사용하면 안 된다라는 조건으로 환원할 수 있기 때문에 문제를 해결하는 데 큰 어려움이 되지 않는다.

선택할 가지 수가 $2^k$ 에서 $k(k-1)$ 로 줄었지만, 여전히 백트래킹을 단순히 돌리기에는 너무 많은 가지수이다. 한편, 추이적 방향 그래프 자체가 많지 않다면, 정확히 추이적 방향 그래프만 나열될 수 있도록 가지치기를 하는 것이 좋을 것이다. 우리는 답이 나오는 최악의 경우를 쉽게 예측할 수 있으니 (“7 0”) 프로그램의 정당성 역시 보일 수 있다.

가지치기를 하는 것은, 추이성의 정의를 사용하면 된다. 만약 $s \rightarrow e$ 라는 간선을 더할 지 말지 선택을 해야 하는 상황이라고 하자. $s \rightarrow i, i \rightarrow e$ 로 가는 간선이 모두 존재한다면, 이 간선은 무조건 더해야 한다. 한편, $e \rightarrow i$ 로 가는 간선이 존재하는데 $s \rightarrow i$ 로 가는 간선은 이전에 사용하지 않기로 결정했다면, 이 간선은 절대 더할 수 없다. 마지막으로, 간선을 추가하는 순서를 $max(s, e)$ 가 증가하는 순서대로 넣어주자.

이러한 상황을 판단해서 백트래킹을 진행할 경우, 최악의 데이터에서 대략 3-4초 정도의 수행 시간이 걸린다. 최적화를 위해서는, 최악의 데이터 몇개에 대해서 예외 처리로 답을 바로 출력하게 하거나, 가지치기 과정에서 위 판단을 bitmask를 사용해서 최적화하는 방법등이 있다. Bitmask를 사용한 최적화를 추가하면, 0.5초 정도에 최악의 데이터를 처리할 수 있다.

마지막으로, 답의 크기가 n = 6일때 대략 32만, n = 7일때 대략 1317만으로, 굉장히 빠른 속도로 증가한다. 고로 모든 $3^K$ 개의 부분집합을 판단한다고 하더라도, 최악의 부분집합이 판단되는 경우는 매우 작고, 자주 판단되는 부분집합들은 크기가 작으니 빠르게 판단되어, 크게 상관이 없다.

2020 GP of Zhejiang. Junk Problem

XOR 연산은 $Z_2^{n}$ space에서의 덧셈 연산입니다. 이 덧셈 연산 결과가 서로 다른 $K$ 개의 벡터를 찾아야 하고, 차원의 크기는 $\log N$ 이하여야 합니다. $Z_2$는 익숙하지 않으니, 실수에서 이러한 성질을 만족하는 벡터를 찾아봅시다. $(i, i^2)$ 와 같은 2차원 벡터를 생각해보면, 두 벡터의 덧셈 결과인 $(i+j, i^2 + j^2)$ 는 모두 서로 다름을 알 수 있습니다. 어떠한 두 수의 합과 제곱의 합을 알면, $2ij = (i+j)^2 - i^2 - j^2$ 이니 곱을 알 수 있고, 합과 곱을 알면 근의 공식을 사용하여 각 숫자를 알 수 있습니다. 고로 두 결과가 같을 수 없고, 위와 같은 것이 성립합니다.

이 통찰을 최대한 유지해서 원래 문제로 돌아와 봅시다. $2 \log K$ 정도의 차원이 허용되니, $K < 2^q \le 2K$ 를 만족하는 최소의 정수 $q$ 를 찾은 후, 모든 $1 \le i < K$ 에 대해 $a_i = i \times 2^q + f(i)$ 와 같은 형태로 끼워넣는 것을 생각해 볼 수 있습니다. 덧셈이 정확히 되지 않으니 완벽하다고 할 수는 없지만, 그래도 두 개의 컴포넌트는 계산 과정에서 완벽히 분리됩니다.

이제 $i \oplus j, f(i) \oplus f(j)$ 를 알면 $i, j$ 를 유일하게 복원할 수 있는 함수 $f$ 를 생각해 봅시다. 예를 들어 앞서 경우를 그대로 가져오면 $f(i) = i^2$ 가 될 것입니다. 하지만, $Z_2^n$ space라고 생각하면, 곱셈을 어떻게 해야 하는 지 명확하지 않습니다. 단순한 dot product를 취해주면 (AND 연산) 원하는 성질이 하나도 보존되지 않기 때문입니다.

덧셈이 XOR 연산이며 곱셈 연산이 정의되고, 실수와 비슷한 성질을 대부분 보존하는 방법은 무엇일까요? 덧셈이 XOR 연산이 아닌데, 곱셈이 정의되고 실수와 비슷한 성질이 보존되는 대표적인 곳은 $Z_p$ 가 있습니다 (나눗셈이 됨을 활용해서 기댓값을 $\mod p$ 로 구하는 문제를 많이 풀어보셨을 것입니다.) 덧셈을 XOR 연산으로 만들기 위해서는, binary field $GF(2^q)$ 를 정의하면 됩니다.

Binary field는 $q$ 차 기약다항식 하나로 표현할 수 있습니다. Binary field의 원소는 $q$ 차 미만이며 modulo 2 위에서 정의되는 모든 다항식입니다. (고로 $2^q$ 개의 원소를 가집니다.) 이제 각 원소의 덧셈, 뺄셈, 곱셈은 일반적인 mod 2 상의 다항식 연산처럼 하면 되고, 단지 정해놓은 기약다항식으로 modulo만 취해주면 됩니다. 앞서 소수를 모듈러로 한 것을, 기약다항식을 모듈러로 한 것으로 바꿨다고 생각하시면 됩니다. $q$ 차 기약다항식은 여러 방법으로 찾을 수 있지만, 사실 문제 제한 상 $q \le 12$ 만 신경쓰면 되니 https://www.partow.net/programming/polynomials/index.html 같이 구글링으로 해결하신 후 하드코딩하시면 편합니다.

이제 일반적인 연산이 전부 정의되는 finite field지만, $f(i) = i^2$ 를 쓸 수는 없습니다. $2ij = (i+j)^2 - i^2 - j^2$ 인데 modulo 2라서 $ij$ 를 구할 수 없기 때문입니다.

하지만, $f(i) = i^3$ 으로 해 주시면, $(i^3+j^3) = (i-j)(i^2+ij+j^2) = (i-j)((i+j)^2-ij) = (i+j)((i+j)^2 - ij)$ 가 성립합니다. 고로 합과 세제곱의 합을 알면 곱이 유일하게 결정됩니다. Finite field에서 이차방정식은 최대 2개의 근을 가지니, 아까와 같은 이유로 문제가 해결됩니다.

거의 문제를 푼 것 같으니 앞으로 돌아와서, 크기가 $N$이하인지 확인해 봅시다. $a_i = i \times 2^q +f(i) \le (K+1)\times 2^q \le 2K(K+1) \le N+2K$ 입니다. $2^q < 2K-1$ 라고 하면 사실 $N$ 이하입니다. 그리고 $2^q = 2K-1$ 일 수 없습니다. 고로 $2^q = 2K$ 일 때가 문제가 됩니다. 이 경우에만 답이 $N$을 넘어가 틀리게 됩니다. 이 경우에는, $N$을 넘어가는 숫자가 하나밖에 없다는 점을 사용하시면 약간의 아이디어로 이 점을 해결할 수 있습니다 (이는 연습문제로 남깁니다.)

이 문제의 풀이를 이해하면서 여러 개념들을 공부하게 되었습니다. 제가 익숙하게 다루는 분야가 아닌지라 미숙하게 서술된 부분이 있을 것 같습니다. 글이 자연스럽게 직관을 보이는 형태로 서술되었는지, 혹시 사실을 다루는 부분에서 틀린 내용이 있다던지 하면 댓글로 적어주세요. 읽으면서 저도 공부하겠습니다.