$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

4월 3, 4주차 PS 정리::::Gratus' Blog

4월 3, 4주차 PS 정리

알고리즘 문제풀이/PS_Weekly 2020. 5. 1. 04:13

그나마 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의 빠른 계산 이라는 주제로 포스팅을 시작할 예정 ㅋㅋ

'알고리즘 문제풀이 > PS_Weekly' 카테고리의 다른 글

7월 2 ~ 4주차 PS 정리  (0) 2020.07.26
6월 ~ 7월 1주차 PS 정리  (0) 2020.07.04
4월 3, 4주차 PS 정리  (0) 2020.05.01
4월 1, 2주차 PS 정리  (0) 2020.04.17
3월 3, 4주차 PS 정리  (0) 2020.03.31
3월 2주차 PS 정리  (0) 2020.03.09


admin