Petrozavodsk 특집. 이 캠프에서 풀 수 있는 문제는 당연히 수학 문제밖에 없다.
$i$에 대한 답을 구하려면, $l \le i \le r$에 대하여 $\frac{\sum_{k=l}^r a_k}{r-l+1}$을 최대화하면 된다.
분수식의 최적화를 하려면 이분탐색을 쓰는 게 좋으니, 이분탐색을 걸어주자. $\frac{\sum_{k=l}^r a_k}{r-l+1} \ge x$인 $l \le i \le r$이 존재하는지 보자.
즉, $\sum_{k=l}^r (a_k-x) \ge 0$인 $l \le i \le r$이 존재하는지 확인하면 된다.
이를 위해서, $\sum_{k=1}^{l-1} (a_k-x)$와 $\sum_{k=r+1}^n (a_k-x)$를 각각 최소화하면 된다.
$f_{1, k}(x) = \sum_{i=1}^k a_i - kx$, $f_{2, k}(x) = \sum_{i=k}^{n} a_i - (n+1-k)x$를 정의하자.
$f_{1,1}(x), f_{1,2}(x), \cdots , f_{1, i-1}(x)$ 중 최소값을 구하고, $f_{2, i+1}(x), f_{2, i+2}(x), \cdots , f_{2, n}(x)$ 중 최소값을 구하면 된다.
이는 이 문제를 풀듯이 Segment Tree + Convex Hull Trick으로 해결할 수 있다. 기울기가 단조적임을 이용하자.
시간 제한이 많이 빡세서 여러 추한 최적화를 해서 맞았다. 사실 이게 정해가 아닌 것 같고 그냥 내가 뚫은 것 같다 ㅋㅋ
비벼서 푸는 것이 충분히 가능한 문제다. 증명하고 풀려면 조금 빡세다. Lifting The Exponent Lemma를 이용하면 된다.
문제 풀이의 시작에 대해 힌트를 조금 주자면, 먼저 답의 소인수는 $d$의 소인수여야 함을 보이자.
그 다음, $d$의 소인수 $p$를 잡고 $a$가 $p$의 배수인 경우와, 아닌 경우를 나누어서 위 보조정리를 적용해보자.
주어진 $x \le y$에 대하여 가능한 최솟값을 먼저 $x, y$에 대한 식으로 구하면, $\lfloor \frac{x+y}{x+1} \rfloor$를 얻는다.
그 다음, 가능한 문자열의 개수를 동적계획법으로 구하면 된다. 이 과정에서 여러 최적화를 동원할 수 있다.
미리 "가능한 최솟값"을 기준으로 쿼리를 정렬해놓으면, 필요할 때마다 동적계획법을 돌려주면 된다.
답 $k$를 고정했을 때, 가능한 $x$의 범위가 $x \le \frac{2n}{k}$이므로, 조화수열 형태의 시간복잡도를 얻는다.
BOJ 18666 AtCoder Quality Problem
이 문제를 풀면 접근이 쉬워진다. $dp[S][c]$를 집합 $S$와 그 부분집합들을 모두 색칠하되, $S$를 $c$로 색칠할 경우 최소 비용이라고 정의하자. $S$를 빨간색으로 칠한다면, [$S$의 부분집합 중 파란색으로 칠해진 가장 큰 집합 $V$]은 유일하게 결정된다. (존재하지 않는 경우 포함) 이제 $V$에 존재하지 않는 원소를 갖는 $S$의 부분집합은 전부 빨간색으로 칠해지게 된다. 이를 이용하여, $\mathcal{O}(3^n)$ 동적계획법을 설계할 수 있다. 이를 최적화하려면, SOS DP를 활용하면 된다.
재밌는 문제였지만 AtCoder Quality인지는 잘 모르겠다 ㅋㅋ
키타마사법을 제대로 이해하고 쓰는지 묻는 문제다.
키타마사법을 제대로 이해했다면, 문제를 단순한 가우스 소거법 문제로 변형할 수 있다.
Berlekamp-Massey 구현체와 (또는 키타마사 구현체) 대충 예전에 짜놓은 가우스 소거 구현체가 있으면 5분 안에 코드를 짤 수 있다.
BOJ 18555 Modulo-magic Squares
선형대수학 문제니까 선형대수학 문제처럼 풀면 된다.
가우스 소거를 해야 하는데, 이걸 손으로 하기도 그렇고 코드를 짜기도 귀찮으니 Sage를 이용했다.
$\mathbb{Z}$를 ring으로 설정하고 가우스 소거를 해야지 각 $m$에 대해서 써먹을 수 있는 결과를 얻을 수 있음에 주의하자.
아무튼 열심히 계산을 시키고 패턴을 찾아보면 비벼서 풀 수 있다. 증명은 특별히 시도해보지 않았다.
트리의 Centroid를 생각하면 된다. 각 간선 $e$가 크기 $k, n-k$의 컴포넌트를 잇는다고 하자.
그러면 Centroid는 둘 중 크기가 큰 컴포넌트에 속하므로, 이 간선은 거리의 합에 $\operatorname{min}(k, n-k)$만큼 값을 더한다.
이제 대칭성을 극단적으로 활용해서, 1번 정점과 2번 정점 사이의 간선이 있는 경우, 그때 이 간선이 기여하는 값을 계산해보자.
1번 정점쪽의 컴포넌트 크기를 $k$, 2번 정점쪽의 컴포넌트 크기를 $n-k$라고 하자.
1번 정점쪽의 컴포넌트에 속하게 될 정점의 집합을 고르는 방법은 $\binom{n-2}{k-1}$개가 있다.
1번 정점쪽의 컴포넌트를 만드는 방법은 Cayley's Formula에 의해 $k^{k-2}$다.
마찬가지로 2번 정점쪽 컴포넌트를 만드는 방법 역시 $(n-k)^{n-k-2}$다.
이제 이 간선이 기여하는 값은 $\operatorname{min}(k, n-k)$다. 이제 이를 정리해서 계산하면 답을 얻을 수 있다.
그런디 넘버를 계산하면, 결국 $(a_1 \pmod {x+1}) \oplus (a_2 \pmod{x+1}) \cdots \oplus (a_n \pmod{x+1})$를 계산하는 문제가 된다.
$1, 2, \cdots , n$ 중 홀수번 등장하는 집합을 $S$라고 정의하자. $t(x+1) \le v < (t+1)(x+1)-1$인 $v \in S$에 대하여 $(v-t(x+1))$의 XOR 값을 로그 시간에 계산할 수 있으면, $\mathcal{O}(n \log^2 n)$에 문제를 해결할 수 있다. 이를 위해서, $\displaystyle f(i, 2^k) = \oplus_{i \le x < i+2^k, x \in S} (x-i)$라고 정의하자.
이 함수는 Sparse Table과 비슷한 방식으로 계산될 수 있고, 우리가 원하는 값들 역시 이를 이용하여 로그 시간에 계산할 수 있다.
계산하는 과정이 굉장히 절묘하다. XOR의 성질과 Sparse Table의 성질이 절묘하게 잘 맞아떨어지는 것 같다.
Nim 게임의 결과는 XOR로 계산할 수 있다. 그래프의 Cycle 역시 XOR로 생각할 수 있다.
간선에 대응하는 벡터를 간선이 잇는 두 정점의 번호에 1, 나머지에는 0으로 두면 된다.
간선의 집합이 Cycle인 것은 간선에 대응하는 벡터들을 XOR하면 zero vector가 나오는 것과 같다.
Nim 게임에서 후공이 승리하는 것은 간선 위에 놓인 돌의 개수를 XOR하면 0이 나오는 것과 같다.
그러니 각 간선에 대하여 그 간선이 잇는 두 정점의 번호 및 간선 위에 놓인 돌의 개수에 대한 정보를 길이 $n+60$의 벡터로 만들 수 있다.
이제 good graph인 것은 결국 선택한 간선들에 대응되는 벡터들이 서로 선형독립인 것이다. ($\mathbb{F}_2$에서 본다)
결국 이 문제는 "maximum weight linearly independent subset"을 구하라는 문제다.
이 시점에서 구글 검색을 좀 해봤더니 대충 "matroid", "greedy" 같은 키워드가 나왔다. :(
어쨌든 이 문제는 그리디 알고리즘과 가우스 소거로 해결할 수 있다. 매트로이드를 한 번 공부해봐야 하나 싶다.
BOJ 18610 Yet Another Convolution
식 조작을 위해서 Iverson Bracket을 이용하겠다.
각 $k$에 대해서 $c_k$를 구하는 문제를 풀자. 이제 index가 $k$의 배수인 값들만 보면 된다.
이제 $\text{gcd}(i, j)=1$, $1 \le i, j \le \lfloor \frac{n}{k} \rfloor$인 경우 $|a_{ik}-b_{jk}|$의 최댓값을 보면 될 것이다.
그러니 $c_1$을 빠르게 구하는 방법을 고안하면, 이를 이용하여 $c_1, c_2, \cdots c_n$을 전부 구할 수 있다. $c_1$을 구하자.
답에 대한 이분탐색을 하자. $|a_i-b_j| \ge C$인 $\operatorname{gcd}(i, j)=1$이 존재함을 판별하면 된다.
이를 위해서는 $X = \displaystyle \sum_{1 \le i, j \le n, |a_i-b_j| \ge C} \sum_{d|\operatorname{gcd}(i,j)} \mu(d) > 0$임을 판별하면 된다. 이는 $\sum_{d|n} \mu(d) = [n=1]$을 이용한 것이다.
$i$를 고정하고, $a_i$가 $X$에 추가하는 값을 구하자. 그러면 $\sum_{d|i} \mu(d) \cdot \left( \sum_{j=1}^n [|a_i-b_j| \ge C] \cdot [d|j] \right)$가 $X$에 추가가 된다.
$\sum_{j=1}^n [|a_i-b_j| \ge C] \cdot [d|j]$는 결국 $|a_i-b_j| \ge C$이고 $d|j$인 $j$의 개수다.
$a_1, a_2, \cdots , a_n$을 정렬하고, $b_1, b_2, \cdots b_n$을 정렬하자. $a_i$의 기존 index를 $ida_i$, $b_i$의 기존 index를 $idb_i$라 하자.
이제 $a_i$가 $X$에 기여하는 값을 $\sum_{d|ida_i} \mu(d) \cdot \left( \sum_{j=1}^n [|a_i - b_j| \ge C] \cdot [d|idb_j] \right)$로 다시 볼 수 있다.
이제 $|a_i-b_j| \ge C$를 만족하는 $j$는 구간 두 개로 나타낼 수 있다. 이 구간들은 $i$에 대하여 단조적이다.
그러니 투 포인터를 이용하여, $|a_i-b_j| \ge C$이고 $d|idb_j$인 $j$의 개수를 빠르게 계산할 수 있다.
모든 계산을 효율적으로 하기 위해서는 약수의 집합, 뫼비우스 함수의 값 등을 전처리해야 한다.
입시 대비할 때 비슷한 문제를 풀어서 빠르게 해결할 수 있었다. $D = \operatorname{min}(d_1, d_2, \cdots, d_n)$이라 하자.
시간 $x$에서 (단, $x \le D$) 아직도 버스를 타지 못했을 확률은 $P(x)=\prod_{i=1}^n \left( 1 -\frac{x}{d_i} \right)$다.
그러니 버스를 탈 시간에 대한 확률분포함수는 $-P'(x)$가 된다. 그러니 답은 $\int_0^D -xP'(x) dx$다.
$P(x)$는 분할-정복 + FFT로 어렵지 않게 계산할 수 있다. 답을 저 형태로 구해도 되고, 부분적분을 해서 식을 $\int_0^D P(x) dx$로 변형한 다음 구해도 된다.
BOJ 18609 Square Root Partitioning
맨 처음에는 이 글 같은 걸 생각해서 뇌절을 열심히 했는데, 최근에 이 문제처럼 해싱하는 문제를 너무 많이 봐서 풀 수 있었다.
적당히 큰 소수 $P$를 잡자. $P \equiv 3 \pmod 4$이도록 잡아주면 더욱 좋다. $a_i \pmod P$를 계산하는 것은 쉽다.
이제 $\sqrt{a_i}$를 직접 다루는 대신, $x^2 \equiv a_i \pmod P$의 해 $x$를 $\sqrt{a_i}$라고 생각하자.
결국 $ \pm$를 적당히 잘 고르는 문제인 만큼, 해를 $x$, $-x$ 중 무엇을 생각하던 상관이 없다.
$P \equiv 3 \pmod 4$이므로, $x^2 \equiv a_i \pmod P$를 빠르게 푸는 것은 어렵지 않다.
Tonelli-Shanks Algorithm을 돌려도 충분히 빠르게 결과가 나올 것이다. $v_2 (P-1)=1$이기 때문이다.
여기서 문제는 $x^2 \equiv a_i \pmod P$가 근이 없을 수 있는데, 이때는 $P \equiv 3 \pmod{4}$이므로 $x^2 \equiv -a_i \pmod P$가 근이 있다.
이제 $\sqrt{a_i}$를 복소수 $x \cdot i$라고 생각하자. 이제 $\sqrt{a_i}$를 간단한 형태로 "구했다".
본 문제를 푸는 것은 간단한 meet in the middle 알고리즘으로 할 수 있다. 솔직히 왜 맞는지 모르겠다.
일반성을 잃지 않고, 주어진 그룹이 전부 1번 팀에 속하게 될 확률을 구해보자.
핵심 아이디어는 "처음으로 1번 그룹이 꽉차는 시점", "처음으로 2번 그룹이 꽉차는 시점"으로 경우를 나누는 것이다.
이걸 하면 간단한 조합론적 카운팅으로 식을 세울 수 있다. 문제는 이를 빠르게 계산하는 것이다.
식을 잘 세우면 결국 $\sum \frac{1}{2^k} \binom{k}{n-1}$와 주어진 사람의 수 $k_i$에 대하여 $\sum \frac{1}{2^k} \binom{k}{n-k_i-1}$을 주어진 $k$의 구간에 대하여 빠르게 계산해야 한다는 결론이 나온다.
이 식을 빠르게 계산하는 방법은 잘 모르겠고 (식을 잘 조작하면 $\sum_{i=l}^r \binom{n}{i}$를 빠르게 계산하는 것과 동치다) 이 문제에서는 가능한 $k_i$의 종류가 대충 800개 이하이므로 (합이 20만 이하니까) 이를 이용해서 $\mathcal{O}(n \sqrt{\sum k_i})$로 문제를 해결할 수 있다. 여러모로 재미없는 문제였다. 구현이 좀 힘들었다.
조건이 무섭게 생겼는데, 이를 해석하면 각 연결 컴포넌트의 크기가 6 이하란 것이다. 귀류법으로 크기 7 이상인 연결 컴포넌트가 있다면, $A$를 적당히 잡아서 임의의 $a, b \in A$에 대하여 $A$에 속한 정점만을 통해서 $a$에서 $b$로 가는 경로가 존재하도록 할 수 있다. 그러니 모순을 얻는다.
그러니 각 컴포넌트의 채색다항식을 "상태 압축" 백트래킹 + Lagrange Interpolation으로 얻을 수 있다. Project Euler 194, 544를 참고하면 좋을 것 같다. 이제 답을 구해야 하는데, 정점의 개수가 6 이하인 그래프 중 서로 non-isomorphic한 것의 개수가 200개 정도니 200개 이하의 서로 다른 채색다항식 $p$에 대하여 $p(1), p(2), \cdots p(n)$을 naive하게 계산하면 된다. Project Euler에서 배운 것을 많이 써먹을 수 있었던 문제였다.
BOJ 18661 The One Polynomial Man
식의 성질을 찾으려고 너무 집착하다가 말렸다. 중요한 것은 식이 동차식이라는 것 뿐이다.
이 경우, $a=0$, $b=0$인 경우를 제외하면 중요한 것은 $a, b$ 자체가 아니라 $a \cdot b^{-1} \pmod{p}$만이 중요하다.
그러니 $a=0$이나 $b=0$인 경우를 먼저 처리하고, 조건을 만족하는 $a \cdot b^{-1}$의 값을 모두 구하자.
여기까지는 (역원을 미리 전처리한다면) $\mathcal{O}(p)$에 가능하다. 이제 각 $t$에 대하여 $a \cdot b^{-1} \equiv t \pmod{p}$인 $a, b \in S$의 개수를 빠르게 구하는 방법을 구하자. 양변에 "로그"를 취하면 이는 FFT로 해결할 수 있는 문제의 형태임을 알 수 있다. $\pmod{p}$ 합동식의 입장에서 로그를 취하는 방법은 원시근 $g$를 잡는 것이다. 이제 모든 것을 적당히 정리해주면 $\mathcal{O}(p \log p)$에 문제를 해결할 수 있다. 문제가 더러워 보이는 것을 제외하면 재밌었다.
식 형태가 convolution이고, 여러모로 상황이 XOR, AND, OR-convolution과 비슷하다는 것을 알 수 있다.
FWHT의 근본은 결국 비트별로 변수를 쪼갠다음 각 변수마다 적당히 convolution을 해서 합치는 것이다.
여기서도 비슷하게 할 수 있다. 하지만 convolution 각을 재기가 까다로운데, 기존 FFT, FWHT처럼 "다항식에 값을 대입한다"라는 생각보다는 행렬변환 -> 단순 "pointwise" 곱셈 -> 행렬변환을 통해서 convolution을 해야겠다는 생각을 해야하기 때문이다. 게다가 단순히 $0, 1, 2$의 개수를 가지고 식을 세우려 하면 터지고, 식을 하나 추가해야 convolution을 할 수 있는 형태의 식이 나오게 된다. 여러모로 빡센 문제. 코드는 FWHT에 살짝 변형을 주면 된다.
그런데 FWHT처럼 구현했는데 맞는 이유는 솔직히 잘 모르겠다. 그냥 [각 "비트"별로 convolution을 하는 방법을 고안한 다음 FWHT처럼 짜면 되겠지]라고 생각해서 짰는데, 생각해보니까 FWHT는 multivariable polynomial처럼 생각하면 이해는 되는데 지금 하는 거는 그거랑은 또 달라서... 좀 생각해봐야 할 것 같다. 에디토리얼 찾아봐야 할 듯. Kronecker Product에 뭔가 큰 그림이 있는 것 같기도 하고 ㅋㅋ FWHT 구현 원리부터 다시 봐야겠다.
"Product of Finite Chain"을 최소 개수의 Chain으로 분할하라는 문제다.
Dilworth's Theorem을 생각하면, 최대 크기의 antichain을 구하라는 문제다.
그런데 이 문제는 Romania TST 1997에서 (간단한 버전) 등장했고, Bruijn의 결과 역시 알려져 있다.
결국 $0 \le x_i < p_i$이면서 $\sum_{i=1}^n x_i = \lfloor \frac{1}{2} \sum_{i=1}^n (p_i -1) \rfloor$인 정수해의 개수를 구하면 된다.
포함-배제를 사용하면 $\mathcal{O}(2^n \cdot n)$ 풀이를 얻을 수 있다. 이는 당연히 비효율적이다.
하지만 meet in the middle 방식을 사용하면, 시간복잡도를 $\mathcal{O}(2^{n/2} n^2)$으로 줄일 수 있다.
포함-배제 식을 제대로 세웠다면, meet in the middle을 통해서 최적화를 하는 과정은 복잡하지 않다.
이항 계수를 이항 계수로 보지 말고, 단순히 다항식으로 보면 도움이 많이 될 것이다.
예전에 koosaga 블로그에서 키워드 Berlekamp-Massey를 봐서 빠르게 풀 수 있었다. 그때는 내가 이걸 진짜 풀 줄 몰랐지...
$p_k$을 $k$번째 시행에서 처음으로 $n$번 정점에 도착할 확률이라고 하자. "처음으로"라는 조건을 그래프로 모델하려면, $n$번 정점에 도착하면 무조건 가상의 $n+1$번 정점으로 가고, $n+1$번 정점에서는 $n+1$번 정점으로만 갈 수 있도록 하면 된다.
Random Walk하면 Markov Chain이고 결국에는 행렬이다. 그러니 $p_k$는 선형점화식을 따른다.
행렬의 크기가 $n$ 근처니 결국 점화식의 크기도 $n$ 근처다. 즉, 초기항 $2n$개 정도를 직접 $\mathcal{O}(nm) = \mathcal{O}(n^2)$ (planar graph에서 $|E| \le 3|V|-6$)에 구한 다음, Berlekamp-Massey를 돌려서 선형점화식을 구할 수 있다. 이제 우리의 목표는 $\sum_{k=0}^\infty kp_k$를 계산하는 것이다.
이는 생성함수를 이용하여 할 수 있다. $f(x) = \sum_{k=0}^\infty p_k x^k$라고 하자.
$p_k$의 점화식을 알고 있기 때문에, 이를 활용하여 $f(x) = \frac{P(x)}{Q(x)}$가 성립하는 다항식 $P, Q$를 구할 수 있다.
목표는 $f'(1)$과 같고, $P, Q$를 계산하고 미분하는 것은 어렵지 않게 $\mathcal{O}(n^2)$에 할 수 있다.
이 문제도 이 글을 읽다가 키워드를 알게 되었다. 결론부터 말하면 답은 $p(n+1)-1$이고, Pentagonal Number Theorem으로 이를 계산할 수 있다.
증명을 하기 위해서 perfect matching에 대한 자료를 찾아보다가, Tutte-Berge Formula를 찾았다.
이를 이용하여 증명을 할 수 있다. $G$가 조건을 만족하려면 $G$의 최대 매칭의 크기는 $n-1$이어야 한다.
그러니 $|U|-\operatorname{odd}(G-U)+2n = 2n-2$인 정점의 집합 $U \subset V$가 존재한다.
즉, $\operatorname{odd}(G-U) = |U|+2$인 $U$가 있다. $G$에 임의의 $G$에 없는 간선을 추가한 뒤에는 이 $U$에 대해서도 $\operatorname{odd}(G-U) = |U|$가 성립해야 한다.
즉, $G$에 없는 간선은 전부 크기가 홀수인 컴포넌트 두 개를 잇는 간선이어야 한다. 이는 정말 강력한 조건이고, 여기서 정말 많은 정보를 얻어낼 수 있다.
우선 $G-U$의 각 컴포넌트는 전부 크기가 홀수여야 한다. 크기가 짝수인 컴포넌트가 있으면, "크기가 홀수인 컴포넌트 두 개를 잇는 간선"이 아니면서 $G$에 존재하지 않는 간선이 존재하게 되므로 모순이다. 비슷한 이유로, $G-U$의 각 컴포넌트는 전부 clique여야 한다. clique가 아니면, 컴포넌트 내부에서 그을 수 있는 간선이 있으므로 모순이다. 또한, 삭제한 정점의 집합 $U$에 속한 정점들은 차수가 $2n-1$이어야 한다. 차수가 $2n-1$이 아니면, 새로 그을 수 있는 간선이 존재하게 되기 때문이다. 이제 이를 종합하면, 원하는 그래프를 전부 classify 할 수 있다.
결론은 $G$가 차수 $2n-1$인 정점 $k$개와, 크기가 홀수이고 서로 "독립적인" clique $k+2$개로 분할된다는 것이다.
$k$를 고정하고 생각하면, 이때 $G$로 가능한 그래프의 개수는 홀수 $k+2$개의 합으로 $2n-k$를 만드는 경우의 수다.
이는 식을 잘 조작하면 $k+2$개의 자연수의 합으로 $n+1$을 만드는 경우의 수가 된다.
이를 각 $k \ge 0$에 대하여 더하면, $p(n+1)-1$이 답임을 알 수 있고, 증명이 끝난다.
BOJ 18559 Call It What You Want
문제 디스크립션이 무서워 보이지만, 결국에는 필요한 정보를 정말 다 준 디스크립션이다.
$\prod_{d|n} \Phi_d(x) = x^n-1$이고 $\Phi_d(x)$ 각각이 irreducible polynomial이므로, 문제는 결국 $\Phi_d$를 구하라는 것이다.
첫 아이디어로 가능한 것은 $\Phi_n(x) = \frac{x^n-1}{\prod_{d|n, d \neq n} \Phi_d(x)}$를 써서 계산하는 것인데, 이 방법은 간단하지 않은 다항식 나눗셈을 많이해야 하므로 비효율적이다.
여기서는 뫼비우스 반전을 생각할 수 있다. 결국 양변에 로그를 취한 다음 뫼비우스 반전을 적용하면, $\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}$를 얻는다. $x^d-1$ 형태의 다항식은 곱하기도 나누기도 간단하니, 계산을 효율적으로 할 수 있다. 특히, $\mu(n/d) \neq 0$인 경우에만 연산을 하면 되므로 연산 횟수도 생각보다 적다. 계산을 할 때, 먼저 곱할 다항식을 다 곱한 후 나눌 다항식을 나눠주는 게 좋다. 출력 형식을 맞춰주는 것은 적당히 정렬 하면 된다.
문제를 적당히 해석한 뒤 Jimp Number가 정확히 어떤 자연수인지 classify 하는 것은 귀찮지만 어렵지는 않다.
결국 문제는 $n$ 이하 소수의 개수와, $n$ 이하 $4k+3$ 꼴 소수의 개수를 구하는 문제로 전환된다.
$n$ 이하 소수의 개수를 동적계획법으로 $\mathcal{O}(n^{3/4})$에 구하는 방법을 알고 있다면, 이를 간단하게 확장하여 $n$ 이하 $4k+3$ 꼴 소수의 개수를 구하는 $\mathcal{O}(n^{3/4})$ 알고리즘을 설계할 수 있다. 사실 앞에 $\phi(4)=2$라는 상수가 붙는다. 아무튼 이걸 짜면 아슬아슬하게 통과가 된다.
결국 Project Euler 611의 하위호환. 이 문제가 classify 난이도 및 케이스 분석 면을 봤을 때 훨씬 더 어려운 문제 같다.
사실 위에서 언급한 동적계획법은 top-down과 bottum-up 방식을 모두 활용한 뒤, offline query + fenwick tree를 이용하여 $\mathcal{O}(n^{2/3})$으로 최적화가 가능하다. 아니면 아예 Meissel-Lehmer Algorithm를 이용할 수도 있다. 확장이 잘 되는지는 모르겠다. 이런 방법들을 구현해야만 풀 수 있는 문제였다면 훨씬 더 어려운 문제가 되었을 것 같다. 정해는 offline query + fenwick tree로 최적화 하는 방법을 사용하는 것 같다. 이것도 한 번 짜보기는 해야될 듯.
다른 풀이로는 segmented sieve를 조져서 DB를 제작하는 풀이가 있었다고 한다. 엌ㅋㅋㅋㅋㅋㅋㅋㅋ
'PS > 수학 계열 PS' 카테고리의 다른 글
| 4월의 PS 일지 - Part 4 (1) | 2020.04.25 |
|---|---|
| Project Euler 500문제 및 문제 추천 (0) | 2020.04.12 |
| JAG Summer Camp 2018 Day 2 (0) | 2020.02.19 |
| Project Euler 450문제 (0) | 2020.02.08 |
| 1월 PS 정리 - Part 2 (0) | 2020.01.26 |