7/27~7/28 연습

어제 올리려고 하다가 9시에 자버렸다 ㅁㄴㅇㄹ...

이번에는 MWT 특집.

---

2011. 암호코드

문제 : icpc.me/2011

간단한 dp인데, 0인 경우를 생각해주지 않으면 가버릴 수 있다. 입력 문자열을 $S$라고 하고, $D[i]$를 $S_1 \cdots S_{i-1}$를 해석할 수 있는 경우의 수라고 두자. 입력이 0으로 시작하지 않는다는 것이 보장되어 있으므로 $D[2]=1$이다. 이제 dp를 앞에서 뒤로 뿌려주자.

$S_i \neq 0$인 경우, $S_i$를 하나의 암호문으로 해석할 수 있으므로 $D[i+1]+=D[i]$.

$S_i \neq 0 \wedge 10S_i + S_{i+1} < 27$인 경우, $S_iS_{i+1}$를 하나의 암호문으로 해석할 수 있으므로 $D[i+2]+=D[i]$.

최종 답은 $D[n+1]$이 된다.

Time Complexity : $O(n)$.

---

3621. 족보

문제 : icpc.me/3621

ㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷ

간단한 수학적 귀납법으로, $P(i)$를 조상이 i명일 때 추가해야 하는 가짜 조상의 수라고 할 때, $P(i)=P(i-d+1)+1$이 성립함을 알 수 있다. 따라서 입력을 통해 $x$의 조상 수를 구해놓고, 0부터 $n$까지 $P(parents(x))$를 구해주면 된다. 아무생각없이 for문 0부터 $n-1$까지 돌리면 나처럼 MWT를 낼 수 있으니 주의하자....

Time complexity : $O(n)$

---

1766. 문제집

문제 : icpc.me/1766

나름 중요한 개념을 담고 있는 문제이다.

"위상 정렬 중 가장 priority가 작은 것을 구하여라!"라는 문제인데, 일반적인 DFS로 위상정렬을 할 경우에는 이를 고려해줄 수가 없다. (탐가네 빡대가리 X렢씨처럼 인접 리스트를 정렬해둔다고 해결할 수 있는 게 아니다) 이는 위상정렬의 클래-식한 버전과 priority_queue를 활용하여 해결할 수 있다.

입력으로부터 각 정점의 in-degree를 구해두자. in-degree가 0인 정점들을 pq에 넣는다. pq가 빌 때까지, top을 그래프에서 제거하면서 in-degree가 0이 되는 정점들을 계속 pq에 넣어주면 된다.

Time Complexity : $O((V+E) lg V)$

---

3825. 은행수

문제 : icpc.me/3825

그냥 가우스 소수 판별 문제인데, 내가 왜 이렇게 코드를 짰는지 이해할 수가 없다..... (정올 시작할 때쯤 틀린 문제)

가우스 정수 $z=(x,y)$에 대해 $x^2 + y^2$를 norm $N(z)$이라고 할 때, norm이 $m^2+n^2$보다 작은 가우스 정수를 모두 돌면서 norm이 $m^2+n^2$의 약수인 수가 5개 이상이면 C, 아니면 P를 출력하면 된다.

[증명]

페르마의 두 제곱수 정리의 확장판에 의해, 어떤 자연수 $X$가 $4k+3$꼴의 소인수를 짝수 개만 가질 경우 $X$는 두 자연수의 제곱합으로 나타낼 수 있다. 즉 $N(Z)=X$를 만족하는 가우스 정수 $Z$가 존재한다.

따라서 $N(a)|N(b)$일 경우, $\frac{N(b)}{N(a)}$ 또한 모든 $4k+3$꼴의 소인수를 짝수개만 가지므로 어떤 가우스 정수의 norm이 될 수 있다. 가능한 a가 (가우스 자연수 범위에서)5개 이상일 경우 가우스 정수 b는 합성수이다.

Time Complexity : $O(T(m^2+n^2))$

[개선_8/4]

사실 시간복잡도를 더 줄일 수 있다. 어떤 가우스 정수 $z$가 합성수라면, $1<N(w)<\sqrt{N(z)}$인 가우스 정수 $w$가 존재한다. 따라서 기존의 norm bound인 $m^2+n^2$를 $\sqrt{m^2+n^2}$로 줄일 수 있다. 실행시간도 4ms에서 0ms로 줄었다!

Improved Time Complexity : $O(T\sqrt{m^2+n^2})$

---

아 어려운 것도 풀어야 하는데...