3월 1주차 PS 정리

어쩌다 보니 개강이 미뤄져서(?) 더 생긴 방학 기간에는 아마 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: 

 

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