이제부터 풀이는 매우 간략하게 올리기로 결정했다.
이 글에 나온 이 문제의 풀이를 참고하라. 분할 정복 등의 풀이가 있는 것으로 알지만, 필요 없다.
전체의 각 부분집합 \(X\)에 대하여, \(a(X)\)를 [\(X\)의 원소를 하나도 포함하지 않도록 박스를 고르는 경우의 수]라고 하자.
그러면 포함배제의 원리를 이용하여 답을 \(a(X)\)에 대한 식으로 간단하게 쓸 수 있다.
한편, \(b(X)\)를 [\(X\)의 원소를 하나도 포함하지 않는 박스의 수]라고 하면 \(a(X)=2^{b(X)}\)가 성립한다.
이제 목표는 \(b(X)\)의 값을 전부 구하는 것이고, 이는 SOS DP를 이용하면 쉽게 계산할 수 있다.
이런 카운팅 문제는 보통 (원순열처럼) 가능한 경우의 수를 naive하게 센 다음 중복을 제거하는 방식으로 해결한다.
naive하게 세는 방법은 \([1,k]\) 부분과 \([k+1,n]\) 부분이 각각 palindrome이 되는 문자열의 개수를 전부 더하는 방법이다.
중복이 되는 경우는 어떤 경우일까? 두 정수 \(p, q\)가 존재하여, \([1,p],[1,q],[p+1,n],[q+1,n]\)이 모두 palindrome이 되는 문자열은, 중복되어 세질 것이다. 이런 문자열들은 주기가 있는 문자열이라는 것을 어렵지 않게 파악할 수 있다.
이를 기반으로, 중복되어 세질 문자열 \(S\)를 잡고 \(S=RRR\cdots R\) 형태로 써보자. 단, \(R\)을 minimal하게 잡자.
그러면 \(R\)이 어떠한 형태를 가져야 하는지 알 수 있고, 이때 \(S\)가 얼마나 중복되어 세지는 지 파악할 수 있다.
이 과정을 모두 마쳤다면, 답에 대한 일종의 점화식을 설계할 수 있을 것이다. 코드는 매우 간단하다.
\(k=2\)인 경우를 먼저 설명한다. 모든 연산을 \(\pmod{2}\)로 하자. 문제에서 주어진 벡터들을 행으로 갖는 행렬 \(A\)를 생각하자.
조건을 만족하는 \(p, q\)가 아예 없다면, \(AA^T\)는 대각성분을 제외하고 전부 \(1\)일 것이다.
또한, \(AA^T\)의 실제 대각성분은 쉽게 계산할 수 있다. 즉, 조건을 만족하는 \(p, q\)가 존재하는지 여부를 판별하는 것은 다음 문제와 같다.
문제: 이미 모든 entry를 알고 있는 행렬 \(C\)가 있다. \(AA^T = C\)인가?
이 문제는 단순히 \(AA^T\)를 계산하는 방법보다 더 빠른 방법이 있다. Freivald's Algorithm을 참고하라.
이제 조건을 만족하는 \(p, q\)가 존재하는지 판별할 수 있고, 이를 확장하면 존재하는 경우 \(p, q\)의 예시도 구할 수 있다.
여기까지 잘 이해했다면, \(k=3\)인 경우에는 상황이 간단하지 않다는 것을 쉽게 파악할 수 있을 것이다.
\(a \not\equiv 0 \pmod{3}\)이면 \(a^2 \equiv 1 \pmod{3}\)임을 활용해보자. 이 아이디어는 나도 생각 못했다 :(
핵심 관찰은 \(d_i(a) = \sum_{j} [\text{min}_{k \in [i, j]} a_k = a_j]\)가 성립한다는 것이다.
\(i>j\)인 경우 구간은 \([j, i]\)로 바뀌며, \([P]\)는 \(P\)가 참이면 1, 거짓이면 0이다.
이제 문제는 \(a_j = \text{min}_{k \in [i, j]} a_k\)이며 inversion의 개수가 \(K\)인 permutation의 개수를 세는 것이다.
이 문제를 해결하려면, inversion의 개수에 대한 generating function과 그 유도를 알고 있어야 한다.
generating function이 무엇인지는 Wikipedia 자료를 참고하라.
이런 전형적인 순열에 대한 문제를 풀어봤다면, 다음을 쉽게 증명할 수 있을 것이다.
\(inv_i\)를 \(i<j\)이고 \(a_i > a_j\)인 \(j\)의 개수라고 하자. 자명하게 \(0 \le inv_i \le n-i\)다.
이제 저 조건을 만족시키면서 \(inv_1, inv_2, \cdots , inv_n\)을 고정하면, 이에 대응되는 permutation이 유일하게 존재한다.
여기서 우리는 inversion의 개수에 대한 generating function이 \(\prod_{i=0}^{n-1} (1+x^1+ \cdots + x^i)\)임을 알 수 있다.
이 아이디어를 확장하면, 위 문제도 해결할 수 있을 것이다. 무엇을 어떻게 고정할지 고민해보자.
그림을 대칭시켜서 보는 아이디어는 굉장히 유명하다. 그러면 모든 것을 \(\pmod{2w}\), \(\pmod{2h}\)로 볼 수 있다.
이제 다각형의 한 변과 공이 부딪힐 조건을 생각해보면, \(L \le ax \pmod{m} \le R\) 형태의 식을 얻을 수 있다.
\(a, m, L, R\)이 주어졌을 때 \(L \le ax \pmod{m} \le R\)의 최소해 \(x\)를 구해야 하는데, 여러 방법이 있다.
방법 1: 전형적인 "유클리드 알고리즘처럼 문제 환원하기" - 이 문제와 이 글 참고
\(a, m, L, R\)에 대한 문제를 작은 문제로 환원할 수 있다. \(a-m \pmod{a}, a, L \pmod{a}, R \pmod{a}\)에 대한 문제로 환원해보자.
방법 2: Binary Search + Lattice Point Counting Algorithm (koosaga님에게 들은 풀이)
주어진 문제를 \(ax+my \le mT+L-1\)인 Lattice Point의 개수와 \(ax+my \le mT+R\)인 Lattice Point의 개수가 달라지는 최소의 \(T\)를 계산하는 문제로 바꿀 수 있다. 이는 Binary Search가 가능한 형태임을 알 수 있고, 남은 것은 삼각형 형태의 영역에서 Lattice Point의 개수를 세는 것이다.
물론, 여기서 Lattice Point는 \(x, y \ge 0\)이고 \(x, y\)가 모두 정수인 \((x,y)\)를 말한다.
이 문제는 다시 "유클리드 알고리즘처럼 문제 환원하기" 테크닉을 사용하여 해결할 수 있는 문제다. 직접 해보자.
나머지는 그냥 깡구현이다. 여러모로 많은 것을 배울 수 있던 문제였다. Project Euler 700번도 이 방식으로 풀 수 있다.
BOJ 14343 Gallery of Pillars (Large)
핵심 관찰은 특정 pillar가 보인다면, pillar의 중심도 무조건 보인다는 것이다. 직관적으로 자명하고, 증명도 어렵지 않다.
이제 특정 점이 보일 조건을 수식으로 쓰자. 점에서 직선 사이의 거리 등을 활용하면 간단하다.
결론적으로 이 문제는 \(x^2+y^2 \le r^2\) 형태의 원 내부에서 \(\text{gcd}(x,y)=1\)인 정수점의 개수를 세는 문제로 환원이 된다.
이 문제는 이 글에 나와있는 요 문제와 비슷한 느낌을 갖는다. 하지만 제한이 조금 더 빡세졌다.
하지만, 뫼비우스 반전을 이용하면 이 문제 역시 크게 어렵지 않게 해결할 수 있다. 좋은 문제인지는 잘 모르겠다.
당연히 Burnside's Lemma를 이용하는 문제고, 이 문제는 이 문제집을 본 이후로 내게 숙제로 남아있었다.
Burnside's Lemma를 완전하게 (즉, Group Action에 대한 정리로) 이해해야 해결할 수 있는 문제인만큼, 난이도가 상당하다.
우선 문제를 Burnside's Lemma의 언어로 번역하기 위해, 정확하게 어떤 Group이 Act하고 있는지를 생각해보자.
당연히 돌려서 같은 경우/뒤집어서 같은 경우가 같은 것으로 취급되니, Dihedral Group \(D_n\)이 등장한다.
이제 색을 서로 교환해서도 같은 경우로 취급되는데, 이것은 Symmetric Group \(S_k\)로 생각할 수 있을 것이다.
조금 더 생각을 해보면, 우리는 direct product \(D_n \times S_k\)를 우리의 Group으로 설정할 수 있을 것이다.
이제 Burnside's Lemma의 흐름을 따라가면, 각 \((g, \sigma) \in D_n \times S_k\)에 대해서 left invariant의 개수를 세면 된다.
\(D_n\)의 각 원소 \(g\)가 만드는 cycle 구조와, \(S_k\)의 각 원소 \(\sigma\)의 cycle 구조를 생각해보자.
이를 잘 생각해보면, (특히, 이 문제보다 쉬운 Burnside's Lemma 활용 문제를 많이 풀어봤다면) 답을 어렵지 않게 구할 수 있을 것이다.
계산을 하다가 막힌다면, \(D_n\)과 \(S_k\)의 Cycle Index를 참고하는 것을 추천한다.
더 어려운 Burnside's Lemma 활용 문제를 풀고 싶다면, Project Euler 626, 651을 풀자.
UPD 1: 651번은 풀었다. 사전지식이 하나 더 았어야 651번을 풀 수 있다. 그래도 이 문제가 더 어려운듯?
UPD 2: 626번도 풀었다. Group 잘 설정한 뒤에도 여러 난관이 있는 아주 재밌는 문제다. 626, 651 모두 추천한다.
BOJ 14347 Radioactive Islands (Large)
결국에는 "경로에 대하여 어떤 함수를 적분한 것"을 최소화하는 경로를 찾는 문제다.
수학 책을 좀 읽었거나 (서울대 기준) 미적분학 2+ 책을 열심히 읽었다면, 변분법을 생각할 수 있을 것이다.
변분법을 생각하면, \(x, f(x), f'(x)\)를 알 때 \(f''(x)\)를 계산할 수 있을 것이다. 계산은 알아서 열심히 하자.
초기 \(x, f(x)\)의 값과 최종 \(x, f(x)\)의 값을 알고 있으니, 초기 \(f'(x)\) 값을 정하고 적당히 이분탐색을 하면 될 것이다.
선형대수학, 현대대수학과 일부 알고리즘 지식을 총동원해서 풀어야 하는 문제다.
풀이를 설명하는 대신, 필요한 사전지식을 전부 나열한다. 이를 공부하고 합치는 것은 문제를 푸는 사람의 몫인 것 같다.
- Annihilator와 Minimal Polynomial
- Minimal Polynomial을 어떻게 계산할 것인가 (내가 지금까지 본 방법은 두 가지가 있다)
- 어디서나 쓰이는 "학부 대수학의 반" - \(\mathbb{Z}\)의 subgroup은 \(n\mathbb{Z}\) 형태 뿐이다.
- 학부 대수학의 반은 직접 사용되지는 않으나, 풀이를 설계하고 이해하는데 도움이 된다.
- Frobenius Endomorphism
- Lemma: \(x^{q^n}-x\)은 degree가 \(n\)의 약수인 모든 monic irreducible polynomial in \(\mathbb{F}_q\)의 곱이다.
- 개인적으로는 bitset을 오랜만에 사용해서, 이것도 공부해서 풀었다.
'PS > 수학 계열 PS' 카테고리의 다른 글
| JAG Summer Camp 2018 Day 2 (0) | 2020.02.19 |
|---|---|
| Project Euler 450문제 (0) | 2020.02.08 |
| 12월 말 PS 정리 - Part 2 (0) | 2019.12.25 |
| Project Euler 400문제 (0) | 2019.12.13 |
| Project Euler 350문제 (0) | 2019.12.02 |