4월 3, 4주차 PS 정리

그나마 Red Army Study와 dlwocks31이랑 연습하면서 푸는 문제들이 있어서 조금 알고리즘 공부하는 시간이 늘었다. 

 

Google Code Jam Round 1B에 참가했고, 319등의 성적을 거뒀다. https://gratus907.com/103

9문제 + Codejam이 있으니 11문제라고 생각하기로 했다. ㅋㅋ

 

레드아미의 경우, 2주차 셋은 개인적으로 괜찮았지만 3주차 셋은 공부하는 의미가 없었다. 

여기 기술된 문제 중 2주차에 해당했던 문제는 Palindrome, Sad Powers, Queue, Red-White Fence의 4문제이고, 3주차의 경우 한 문제도 적지 않았는데, 어쩌다보니 문제가 다 사전지식만 있으면 금방 뚝딱하는 문제거나 끔찍한 구현에 시달리는 문제가 뽑혀서...

 

BOJ 14992, 2017 서강대학교 Sogang Programming Contest - Master H. 개미

난이도 : Solved ac Platinum 5

가중치 있는 트리가 주어지고, 각 노드별로 자기가 가진 값만큼 올라갈 수 있을때 최대 어디까지 갈 수 있는지 판별하는 문제. 나는 문제를 보고 아 이건 Sparse Table 짜야지 ㅋㅋ 하고 짜서 엄청 오래 걸렸는데, 끝나고 dlwocks31에게 DFS Stack을 이용해서 간단하게 푸는 방법을 배웠다. :fan:

간단히 설명하자면, 루트가 주어져 있으므로 트리에서 임의의 두 정점의 거리를 Preprocessing 이후 쿼리당 $O(1)$ 에 처리할 수 있으므로, 몇번째 Parent node까지 올라갈 수 있는지를 빠르게 이분탐색할 수 있다. 이를 이용해서 $O(\log n)$ 에 한 정점의 답을 구할 수 있으므로, 전체 풀이는 $O(n \log n)$ 시간에 동작한다.

---

Codeforces 335B, Palindrome

난이도 : Codeforces 1900

두 가지 경우로 나누어 접근할 수 있다.  

- S에 어떤 문자 `c`가 100번 이상 반복되는 경우 : 그 문자를 100번.  
- 그렇지 않은 경우 : Longest Palindromic Subsequence 는 DP를 이용해 $O(n^2)$ 에 구할 수 있다. 나는 $S$ 자기 자신과 $S$의 reversed string의 LCS를 구하는 방법을 쓰는데, 이러지 않고도 DP로 $O(n^2)$ 에 할 수 있는 것 같다.

Claim : $n >= 2600$ 이면 반드시 Case 1에 들어간다.  
Proof : Pigeonhole Principle에 의해, 거의 자명하다.    

따라서, 전체 풀이를 $2600^2$ 또는 $2600$ 이내에 할 수 있음을 보였다.

---

Codeforces 955C, Round 471 Div2C Sad Powers

난이도 : Codeforces 2000

주어진 구간 $[L, R]$ 에서, $a^p, p > 1$ 형태인 수들의 개수 세기.

조금만 관찰해 보면, $p > 2$ 인 케이스는 전체 $R \leq 10^{18}$ 에서 수백만개 이하임을 알 수 있다. 세제곱수가 $10^6$, 네제곱수가 $10^{4.5}$... 따라서, 이 경우는 모든 제곱수들을 최대 60제곱 좀 넘게까지 ($2^{60}$) 계산해주면 된다. 정확히는, 소수인 $p$들만 따져야 하는데, 이중에서도 $p = 2$를 빼고 따질 것이다. 굳이 신경쓸 필요 없이, 전부 계산하고 unique해줘도 충분하다. 모든 경우를 다 해보고 $L, R$ 이 들어올 때마다 Lower bound, upper bound 를 이용해서 범위에 있는 개수를 빠르게 세면 된다.

$p = 2$ 인 Case는 $[\sqrt{R}] - [\sqrt{L-1}]$ 로 쉽게 계산할 수 있다. 

 

여담으로, C++의 경우 sqrt를 double precision으로 계산하면 sqrt(1e18) 과 sqrt(1e18-1) 같은 수들을 구별할 수 없기 때문에 틀린다. long double precision을 써야 한다. 우웩...

---

Google Codejam 1B에서 내가 푼 두 문제의 난이도가 이정도 된다고 생각한다. CF 1900~2000? 

사실 B는 인터랙티브라서 좀 걱정했는데, 파이썬으로 구현 + 맥북에서 인터랙터 열심히 돌리면서 디버깅이 주효한 전략이었던 것 같다. 앞으로도 인터랙티브는 절대 윈도우에서 하지 않을 생각이다. 아니 인터랙터를 못쓰는데 어떻게해.

---

BOJ 01442, 멋진 수

난이도 : Solved ac Platinum 3

기본적인 개념은...Meet in the middle 이라고 볼 수도 있고, 일종의 Sqrt Decomp라고도 생각할 수 있겠다. 분할 정복이라고 볼 수도 있겠고... 나는 sqrt decomp라는 생각으로 떠올린 풀이기는 하다.

$2^{32}$ 까지의 수를 모두 Good인지 확인하는 것은 불가능하다. 이를 앞뒤 16비트로 분할한다면, 최대 $2^{16}$개씩 건너뛰면서 셀 수 있을 것 같다.

 

좌우 16비트씩을 나눠서, '앞' 과 '뒤' 라고 부르자. '앞'은 65536번에 한번씩만 바뀐다는 사실을 관찰하자. 즉, 연속한 6만여 개의 숫자들은 '앞' 이 같다.

이제, 0부터 65535까지의 수 중 '자체적으로 멋진' 수와, '0으로 패딩하면 멋져지는' 수를 따로 세야 한다. 이렇게 따로 세야 하는 이유는, '자체적으로 멋진' 수와는 달리 패딩이 필요한 수는 뒤 16비트로 올때만 Good Number가 되기 때문이다. 이제, 다음과 같은 사실을 관찰하자.

- Good number가 앞에 오면, 뒤에는 상관 없이 Good이다.

- Good number가 아닌 수가 앞에 오면, 뒤 16비트에 어떤 비트패턴이 와야 Good인지를 미리 모두 구할 수 있다. 이때, 이 경우의 수를 결정하는건 앞 수의 마지막 2비트이다.

- 경우의 수를 DP로 구하고, 65536개씩 건너뛰면서 세면 된다.

사실 나는 DP를 제대로 못 짜서, 연습 중에는 정리를 못했고 결국 약간의 추한 브루트포스(?) 를 더해서 해결했다. 대략 어떤 느낌이냐면, '앞' 이 00으로 끝나면 63939개 있고...이걸 브루트포스로 세서 집어넣었다. ㅋㅋ

---

BOJ 08222, POI 2012 Stage 1, Distance

난이도 : Solved ac Platinum 1

어떤 수 $x$에서 1 단위 시간마다, 소수 $p$ 를 곱하거나 나눌 수 있다 (나누어 떨어질 때만). 이때, 수 $a_1, a_2, \dots a_n$ 까지의 $n$개의 수들에 대하여, 각각 $a_i$ 에서 가장 빨리 도착할 수 있는 수의 인덱스를 찾아야 한다.

각 소인수를 하나의 좌표 차원처럼 생각하면, 100만까지의 소수가 대략 10만개이므로 10만차원 좌표계에 점을 10만개 찍고, 임의의 점에 대해 가장 가까운 (manhatten distance) 점을 찾는 느낌으로 접근할 수 있다.

 

적당히 좌표처럼 생각해 보면, 임의의 수 $x$에 대하여, 1로부터의 거리를 $d(x)$ 라고 하자. 모든 점에 대한 $d(x)$ 값을 에라토스테네스의 체를 응용하여 구하면 $A \log A$에 구할 수 있다. 이때, $g = \gcd(a, b)$ 에 대하여, LCA처럼 생각해 보면 $dist(a, b) = d(a) + d(b) - 2d(g)$ 임을 알 수 있다. 이제 문제를 해결하기 위해, $g$가 정해졌다고 생각해 보자.

먼저 $g$를 약수로 갖는 모든 가능한 $a_i$ 들을 벡터처럼 만들어 놓고, GCD가 $g$라고 정하자. (실제로 GCD가 아니더라도, $g$의 배수이므로 답이 더 나빠지지 않음을 쉽게 알 수 있다). 

이러면 $g$가 이미 정해졌으므로, $d(a)$ 와 $d(b)$ 가 최대한 작아야 거리가 가깝다. 이때, 이미 점 $a$도 정해진 상황이라면 (어차피 각 점에 대해 모두 해봐야 한다), $d(b)$ 가 무조건 작은 쪽을 골라야 한다. 즉, $g$를 약수로 갖는 모든 주어진 수에 대해, $d(x)$ 값을 기준으로 모두 정렬해 놓고, 각 $g$마다 가능한 모든 최소 조합 ($d(x)$ 가 가장 작은 하나와, 그 벡터에 든 나머지 모든 수) 들을 갱신하면서 가면 된다.

여전히 말은 어렵고 코드는 쉬운 문제... [코드 보기]

시간 복잡도 분석을 해보면, 각 벡터를 정렬하는 경우 $O(kn\log n + A \log A)$, $k$는 100만 이하의 수가 갖는 최대 약수의 개수, $A$는 가장 큰 수 100만. 이때 $k = 240$이라서, 240 * 10만 * log 10만이다. 이게 돈다는건 약간 의심스러울 수 있지만 컴퓨터를 믿고 내면 제한시간의 절반 이하로 통과하며, 굳이 각 벡터를 정렬할 필요 없이 사실은 매번 $O(n)$ 에 min element만 찾아도 되므로 더 줄일 수 있긴 하다.

---

Codeforces 38G, Beta Round 38-G, Queue

난이도 : Codeforces 2200

대략 문제를 설명하자면, 사람들이 순서대로 $n$명 주어진다. 이들은 각각 '중요도' $a_n$ 과 '양심' $c_n$을 갖는다. 

사람이 주어진 순서대로 들어오는데, 도착한 사람은 일단 앞 사람을 보면서, 자기가 가진 일의 중요도가 내 앞 사람보다 크면 새치기를 한다. 그런데 새치기할때마다 양심이 1씩 줄어들게 되고, $c$ 값이 0이 되면 더이상 새치기할 수 없다. 즉, 최대 $c_i$ 명 이상을 넘을 수 없다. 마지막 사람까지 모두 자리를 찾은 후 사람들이 서는 순서를 구하는 문제.

 

Square root decomposition. $s = \sqrt{n}$ 개의 리스트를 관리한다고 생각하자. 각 리스트는 사람들의 정보를 담은 벡터와 최댓값을 빠르게 처리하기 위한 priority queue 같은 구조를 하나씩 써서 관리할 수 있다.  
새로운 사람이 들어올 때마다, '그 리스트의 최대 중요도가 내가 가진 일의 중요도보다 낮고', '지금 쓸 수 있는 $c$가 이 리스트의 길이보다 길면' 리스트를 통째로 뛰어넘는다. 만약 걸린다면 그 리스트 어딘가에 넣어야 한다는 사실을 알 수 있다.  

각 리스트의 길이를 $s$ 보다 너무 길지 않게 관리할 수 있다면, 최대 $s$개의 리스트를 넘기고 $s$개의 자리 중 하나를 찾아서 insert하는 연산이므로 각 연산당 $O(\sqrt{n})$ 에 수행할 수 있다.  
가끔씩 ($s$번에 한번 정도) 리스트의 길이를 바로잡는 연산을 수행하면 되는데, 이 과정은 $O(n)$ 정도에 할 수 있다. (Priority queue 를 이용해서 관리한다면 $O(n \log n)$) 따라서, 전체 연산을 $O(n \sqrt n \log n)$ 에 할 수 있다.

 

여담으로, Red Army Discussion 중에 Applist가 Splay tree를 이용한 풀이가 있음을 설명해 주었다. 뭔가 이런 놀라운 자료구조가 있음은 알고 있지만, PST같은것도 잘 모르는 내겐 너무 먼 일이라... 아름다운 코드와 풀이를 감상하고 이런 복잡한 연산을 $O(\log n)$ 에 처리하는 자료구조가 있는걸보니 이 판은 망했다는 생각을 잠깐 했다.

---

BOJ 13361, Nordic Collegiate Programming Contest [NCPC] 2016 H High Towers

난이도 : Solved ac Diamond 5

번역명 최고인 대장장이 투르비온

별도 포스팅 : https://gratus907.com/104

---

Codeforces 1251F, Educational Round 75F Red-White Fence

난이도 : Codeforces 2600

난이도가 높고 재밌으므로 별도 포스팅.

https://gratus907.com/106

---

BOJ 16644, 제 1회 키파컵 E번, Easy Problem

난이도 : Solved ac Diamond 1

나는 이번 문제를 통해 이 방법 자체를 처음 익혔다. 소개할게 많고 개인적으로 인상깊으므로 몇단계에 걸쳐서 포스팅할것 같다. 우선은 Mertens Function의 빠른 계산 이라는 주제로 포스팅을 시작할 예정 ㅋㅋ