$$\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)}$$

3월 1주차 PS 정리::::Gratus' Blog

3월 1주차 PS 정리

알고리즘 문제풀이/PS_Weekly 2020. 3. 7. 19:06

어쩌다 보니 개강이 미뤄져서(?) 더 생긴 방학 기간에는 아마 1주일에 한번, 학기중에는 2주? 시험기간에는 한달정도 간격으로 푼 문제들에 대한 정리를 업로드 해보려고 한다. 한문제씩 쓰기는 좀 작은 문제들도 적을 수 있고... 여전히 한문제 한문제가 어려운 경우에는 별도 포스팅하고 링크만 찍을 예정.

 

기본적으로 풀이를 서술할 거기 때문에, Spoiler Alert는 뭔가 풀이가 좀 김새는 경우(?) 거나, 그런 것만 추가로 달았다. 어차피 포스팅 전체가 문제 풀이의 스포일러기 때문에..ㅋㅋㅋ

 

10문제, 대충 SAC 난이도 순으로 정렬했다. 

 

BOJ 11620, CERC 2015 H Hovering Hornet

난이도 : Platinum 4

보이는 주사위 눈 수의 기댓값은, 눈이 $k$개인 면을 볼 수 있을 확률 $p(k) * k$의 합이고, $p(k)$ 는 전체 부피 중 그 눈이 보이는 부분의 부피의 비율이다. 

예를 들어, 그림의 칠해진 면에서 주사위의 왼쪽을 볼 수 있다. 이렇게 네번 자르면 된다.

이제 정사각형을 직선이 자르는 점들의 위치에 따라서, 삼각형, 사각형, 오각형의 넓이를 구하는 외적 공식을 때려넣고 직선과 선분의 교차점 찾기를 코딩하면 된다. 나는 엄청 오래 걸렸다 :( 

 

BOJ 17184, Baltic OI 2019 B Nautilus

난이도 : Platinum 4

메시지를 보고, 메시지의 $t$ 번째 글자가 $W$ 라고 하자. 즉, $t-1$ 시간에 어디 있었든 간에 왼쪽으로 이동했다는 의미이므로, $t$ 시간에 $W$ 가 말이 되려면, $t-1$ 시간에는 적어도 '왼쪽에 갈 수 있는 공간이 있는 칸' 에 있었어야 한다.

이런 식으로 $R \times C$ 칸의 테이블을 $M$번 갱신하는 풀이는 쉽게 찾을 수 있다. 

이제, $RCM = 125*10^7$ 이므로 이를 더 줄여야 하지만, 도저히 생각이 안 나서 에디토리얼을 봤는데 정해라고 써있는게 std::bitset이었다. :( bitset을 이용해서 빠르게 행 단위로 처리하면 된다.

 

BOJ 17793, BAPC 2019 Lucky Draw

난이도 : Platinum 2

이런 게임에서 무승부가 날 확률은, 임의의 어떤 플레이어 1번이 승리할 확률이 $p$ 라고 할 때, $1 - np$ 이다. 다시 말하면, 누군가 혼자 살아남을 확률을 $p$ 라고 잡아야 하고, 이 경우 턴마다 달라지므로 누군가 한명이 $t$ 턴 후에 혼자 남아 아웃될 확률 $p(t)$ 에 대해 

$$1 - n\sum_{t = 1}^{\infty} p(t)$$ 의 값을 Evaluate 하는 문제가 된다. 

이때, 한명이 $t$턴 후에 승리한다는 것은, 다시 서술하면, [Player 1은 $t$턴만에 아웃, 나머지 모든 플레이어는 $t-1$ 턴 안에 모두 아웃] 이다. 어떤 플레이어가 $t$ 턴 후에 아웃될 확률을 $f(t)$ 라고 하면, $t-1$ 턴 이전에 아웃될 확률은 $f(t)$ 들의 부분합이고, 

$$1 - n\sum_{t = 1}^{\infty} p(t) = 1-n \sum_{t = 1}^{\infty}f(t)\left(\sum_{s = 1}^{t}f(s)\right)^{n-1}$$이 식만 계산하면 된다. 

 

무한대가 들어가지만, 생각해보면 아무리 시작할때 파라미터가 좋게 주어져도 체력이 깎일 확률이 10% 정도는 있고, 충분히 많은 턴이 지나면 $f(t)$ 가 0으로 수렴한다. 넉넉하게 1만 턴 정도까지를 실제로 계산하면, 그 이후의 $f(t)$ 값이 0에 가깝기 때문에 답에 영향이 없다. 

 

BOJ 10531, SWERC 2014 C Golf bot 

난이도 : Platinum 2

FFT 연습 문제.

배열 $A$ 가 주어지고, 두 인덱스 $i, j$ 를 골라 $A_i + A_j$ 로 만들 수 있는 수들이 몇 개인지 세는 문제. 특히, 이 문제의 경우 다른 배열 $B$ 가 주어져서, $B$에 있는 수들 중 이런 방법으로 만들 수 있는 수의 개수를 세야 한다.

$B$의 각 원소에 대해서 $O(n^2)$ 탐색을 하는 것이 가장 naive한 방법이지만, 생각해 보면 어차피 $A$의 각 원소가 어떤 수 $K$ 이하라면, 합은 $2K$ 이하이다. 먼저 $A$의 모든 가능한 합을 Generate 해 보고, $2K$개의 Boolean 배열에 집어넣는 방법을 쓰면 $O(n^2)$ 에 전체 문제를 풀 수 있다. 하지만, 이 문제의 경우 $n = 200, 000$ 이므로 복잡도를 더 내려야 한다.

$A_i$ 를 다항식으로 보고 자기 자신과 Convolution을 수행하면 $O(n^2)$ 풀이의 결과와 정확히 똑같은 배열을 얻을 수 있고, $B$를 돌면서 원하는 차수의 계수가 0인지 아닌지만 판정해 주면 된다. 

 

BOJ 17134 르모앙의 추측

난이도 : Platinum 2

FFT 연습 문제 2

10만 개의 테스트케이스가 들어올 때마다 정답을 계산하지 말고, 모든 가능한 수 100만까지에 대한 정답을 전부 한번에 미리 구해 놓자. 구체적으로, $A$가 모든 홀수 소수들의 배열이고, $B$가 모든 짝수 세미소수들의 배열일 때 인덱스 $i, j$ 를 적당히 골라 $A_i + B_j$ 로 나타낼 수 있는 모든 수들을 표시해 놓으면 된다.

이 과정은 앞 문제와 똑같이 FFT로 수행할 수 있으며, 이를 위해서는 각 소수 / 세미소수를 벡터에 집어넣는게 아니라 그 자리에 표시만 해주는 식으로 생각해야 한다. 대략 100만차 다항식을 한 번 곱셈하는 것으로 전체 문제를 해결할 수 있고, 2초면 적당히 빠른 FFT 구현체를 쓴다면 어렵지 않다. 

BOJ 17104 골드바흐 파티션 2 도 거의 같은 풀이지만, 제한시간이 0.5초이기 때문에 100만차 다항식을 곱셈하기는 쉽지 않다. 17104는 추가적으로 관찰을 통해 곱하는 다항식의 차수를 줄여야 하는 문제이다. (더 빠른 FFT 구현을 쓰면 그냥 100만차 다항식 곱할 수 있나? 그건 잘 모르겠다) 

더보기

std::bitset 을 쓰면 17134처럼 100만차 다항식 곱해도 되는 것 같다.

BOJ 13575 보석 가게

난이도 : Platinum 1

FFT 연습 문제 3

앞 두 문제와 매우 비슷하게, $A$ 배열이 주어지고, 이들 중 몇개를 골라 합이 될 수 있는 모든 수를 찾는 문제이다.

당연히 풀이도 비슷하게 일단 FFT를 써서 다항식을 곱해야 하는데, 그냥 곱하면 1000차 다항식 곱셈 다음에는 2000차 다항식 곱셈이고, 3000차 * 1000차 다항식 곱셈이고.. 이런 식으로는 너무 느리다.

결국 우리가 원하는 다항식은 $f(x)^k$ 이므로, $x^k$ 를 로그 시간에 구할 때처럼, exponentiation by squaring 을 써서 빠르게 곱할 수 있다. 이 경우, 총 $\log k$ 번 다항식 곱셈을 해야 하고, 각 곱셈이 아무리 커도 $n^2$차 정도이므로, 넉넉하게 들어올 수 있다. 

 

BOJ 01792, Polish OI 2007 Stage 1 공약수 (Queries)

난이도 : Platinum 1

$1 \leq x \leq a$, $1 \leq y \leq b$ 에서 $\gcd(a, b) = d$ 인 순서쌍의 개수를 세야 한다.

먼저, 자명하게 일단 $a/d \times b/d$ 를 하면, $d$의 배수인 순서쌍의 개수를 알 수 있다. 이제 $2d$ 가 최대공약수인 경우, $3d$ 가 최대공약수인 경우, ... 를 처리해야 하는데, 이들을 포함배제의 원리를 이용해서 처리해야 한다.

구체적으로는, 다음의 식을 Evaluate 하는 것으로 문제를 해결할 수 있다. 여기서 $p, q = a/d, b/d$ 이고, 나눗셈은 정수 나눗셈만 생각하기로 하자. (일반성을 잃지 않고 $p > q$) 

$$\sum_{d = 1}^{\min(p, q)} \frac{p}{d} \times \frac{q}{d} \times \mu(d)$$

이 식을 그대로 계산하는 것은 시간 안에 들어오기 힘들지만, 관찰해 보면 서로 다른 $\frac{q}{d}$ 의 값이 매번 모든 $d$에 대해 바뀌지 않는다. 따라서, 이를 잘 적용해서 $\sqrt{q}$ 개 정도의 값에 대해서만 계산하고, $\mu$ 의 prefix sum 인 $M$ 함수를 미리 적당히 계산해서 $\sum_{i = s}^{t} \mu(i)$ 를 $O(1)$ 에 계산하면 전체 복잡도를 내릴 수 있다.   

BOJ 08875, IOI 2013 Robots

난이도 : Diamond 5

별도 포스팅 예정(?) 시간이 있다면 포스팅할 수도 있고 아닐 수도 있다. 

간단하게만 설명을 하자면, Parametric search를 하되, 각 확인 작업을 빠르게 ($O(n \log n)$ 정도) 에 하는 방법이 필요하다. 두 로봇을 따로 생각해 주면 코딩은 어렵지 않다. Weak robot 입장에서, 자기가 할 수 있는 한 Small robot 이 하기 힘든 일을 미리 해주면 좋을 것 같다는 생각을 해볼 수 있고, 증명도 그럭저럭 할만 하다.

 

BOJ 15310, 경기과학고 나는 코더다 2017 송년대회 F번 아티스트

난이도 : Diamond 2

별도 포스팅 (https://gratus907.com/95)

BOJ 05257, Balkan OI 2011 5번 TimeisMoney

난이도 : Ruby 5

바로 위의 15310 아티스트와 매우 비슷한 풀이로 통과할 수 있었다. 데이터가 약한가? 그건 잘 모르겠지만, oj uz에서는 한번에 맞았는데 BOJ에선 틀리길래 다시 내 봤더니 맞더라(...) 랜덤 때문인 것 같다.

아티스트와 똑같이 $ax + by$ 최적화를 하는데 (사실 아티스트를 풀기 위해 했던 마지막 추가 케이스들도 안 했다) 이경우 한번에 해야할 정렬이 무려 1만 개라서 SA를 충분히 많이 못 돌린다. 그래도 왜인지 잘 모르겠지만 400ms에 맞던데, 혹시 데이터가 추가되면 일단 아티스트 SA 코드를 그대로 박고 1.95초동안 돌려보면 맞지 않을까? :blobthumbsup: 

 

이 두 문제의 정상적인 풀이는 언젠가 에디토리얼이 이해가 갈 때 다시 코딩해 볼 생각이다. 

 

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

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
3월 1주차 PS 정리  (0) 2020.03.07


admin