[추석맞이 폴란드 스터디] 180922

ko_osaga님이 주최하는 추석맞이 POI 스터디에 참여했다!

목표는 1일 2솔브로 잡았다. 물론 오늘은 쉬운 문제 위주로 풀다 보니 오버페이스를 해버렸지만...

풀이 형식

문제 제목 : POI N / N+1 년의 경우 POI(N+1)으로 표기.

문제 난이도 : 일반적인 Codeforces 난이도 기준. Div2A~B, Div1A~D.

문제 분류 : 그 문제를 푸는 데 필요한 주관적인 KW.

문제 풀이 : (tmi가 포함된) 문제 풀이.

- 문제 요약이 없습니다. 첨부한 링크를 먼저 보고 와주세요.

오늘 푼 문제들 (7 / Total 7)

POI96. Rods  (Div1A)

POI96. Rooks (Div1A)

POI96. Fibonacci Words (Div1B)

POI97. Canoes (Div2B)

POI97. The Number of n-k-special sets (Div2B)

POI97. Monochromatic Triangles (Div1A)

POI97. Lecture Halls Reservation (Div1A)

고민중인 문제들

POI96. Castle

POI04. 스타 대회

---

Spoiler alert!

This section is intentionally left blank.

---

POI96. Rods

Tag : Binary search

현의 길이가 \(l\)이고, 호의 길이가 \(l+d\)인 활꼴이 속한 부채꼴에 관한 문제이다.

부채꼴의 반지름을 \(r\), 중심각을 \(2\theta\)라고 하면 \(r (1 - sin\theta)\)를 구해야 한다.

알고 있는 변수를 활용해서 2개의 식을 얻을 수 있다.

$$ r\theta = 0.5(l+d), \ r\sin \theta = 0.5l $$

안타깝게도 이 식은 깔끔하게 풀리지 않는다. 대신 \(r\)을 소거하면 

\(\frac{\sin \theta}{\theta} = \frac{l}{l+d}\)를 얻을 수 있는데, \(l + d < 1.5l < 1.57l \approx \frac{\pi}{2}l\)이므로 중심각은 예각이고, 이 범위에서 \(\text{sinc} \theta = \frac{\sin\theta}{\theta}\)는 감소함수이다.

따라서 이분탐색을 이용하면 \(\theta\)를 구한 뒤 원하는 식에 그대로 대입하면 된다.

tmi) \(l + d \le 1.5 \times 10^{5}\)이므로 모든 오차는 double 범위에서 충분하다.

tmi2) 실수 범위에서 이분탐색을 할 때는 오차 범위를 한정하기보단 그냥 iteration을 100번 정도 돌리는 게 마음이 편하다. 이걸 안했다가 3틀을 냈다.

---

POI96. Rooks

Tag : Greedy, Heap

룩들이 서로 공격하지 못할 조건은 row, column이 모두 다른 것이다.

그런데 룩들이 '직사각형' 영역에 있으므로, row와 column의 선택은 서로 독립적이다!

따라서 우리는 복잡한 2차원 문제 대신, 1차원에서 row를 배정하는 문제를 2번 풀면 된다.

1차원에서 룩들이 위치할 수 있는 영역은 구간으로 나타난다. 구간이 있는 문제는 일단 시작점/끝점으로 정렬하면 풀리는 게 태반이다. 시도해보자.

\(i\)번 row를 배정할 구간을 선택하는 문제를 생각해보면, 아직 짝이 없는 구간들 중 \(i\)를 포함하면서 끝점이 가장 작은 구간에 \(i\)를 배정하는 것이 최적이 됨을 알 수 있다. 이와 비슷한 아이디어로 풀리는 문제는 USACO17 소건4 가 있다.

n이 3,000이기 때문에 \(n\)번의 배정을 각각 O(n)에 처리해줘도 문제를 풀 수 있고, 이게 세터의 의도인 것 같다. 하지만 우리에게는 모든 O(nlgn) 알고리즘의 영웅, priority_queue가 있다!

모든 구간을 시작점 순서로 정렬하자.

\(i\)번째 row를 배정할 때, 시작점이 \(i\) 이하인 모든 구간을 heap에 때려넣는다.

그리고 heap에서 끝점이 \(i\)보다 작은 모든 구간을 제거한 뒤, heap의 top에 \(i\)번을 배정하면 전체 복잡도 \(O(n \lg n)\)에 문제를 해결할 수 있다.

---

POI96. Fibonacci Words

Tag : DP

오늘 푼 문제 중에서는 제일 재미있었다.

우선 Fib(8)의 길이가 34로 입력 문자열 S보다 길다.

그리고 n > 9에 대해 Fib(n)은 무조건 Fib(8), Fib(9) 중 하나로 시작하고 끝난다.

정확히는 n이 짝수라면 Fib(8)로 시작하고 끝나며, 홀수라면 Fib(9)로 시작하고 끝난다.

자연스럽게 다음의 DP를 떠올릴 수 있다.

D(n) : Fib(n)에 포함되는 S의 개수.

\(n \le 9\)라면 Brute force로 구해도 좋다.

\(n > 9\)에 대해 D(n) = D(n-1) + D(n-2) + g(n-1, n-2)이다.

(g(n-1, n-2) : Fib(n-1), Fib(n-2) 중간에 걸쳐 있는 S의 개수)

그런데 Fib(n-1), Fib(n-2)는 Fib(8) / Fib(9) 중 하나로 시작하고 끝난다. 

일반성을 잃지 않고 Fib(n-1)이 Fib(8)로 끝나고, Fib(n-1)이 Fib(9)로 시작한다고 하면,

Fib(8)의 마지막 글자 k개와 Fib(9)의 마지막 글자 |S|-k개가 |S|를 이루는 k의 개수가 곧 g(n-1,n-2)가 된다.

따라서 대략 \(O(n + |S|^{2})\) 정도의 시간 안에 DP값을 구할 수 있다.

그리고 답의 범위가 최대 \(10^{41}\)까지 커질 수 있으므로 bigint를 써야 한다 ^^

하지만 여기서 만족하면 안된다!

1) O( n + |S| )

우선 n-1과 n-2의 기우성은 무조건 다르다.

따라서 g(n-1, n-2)로 가능한 값은

A = Fib(8) , Fib(9) 사이의 S occurrence.

B = Fib(9) , Fib(8) 사이의 S occurrence.

두 가지 중 하나이다.

A, B의 값도 naive를 피해 구할 수 있다.

C = Fib(8)에서의 S occurrence.

D = Fib(9)에서의 S occurrence.

E = Fib(8) + Fib(9)에서의 S occurrence.

F = Fib(9) + Fib(8)에서의 S occurrence.

이 4개의 값에서 A = E - C - D, B = F - C - D가 구해진다.

C ~ F의 값은 모두 KMP로 구할 수 있고, Fib(9)의 길이는 길어야 3|S|이다.

2) O(lg n + |S|)

D(n)의 값을 몇 개 써보자.

D(10) = D(9) + D(8) + B.

D(11) = 2D(9) + D(8) + A + B.

D(12) = 3D(9) + 2D(8) + A + 3B.

D(13) = 5D(9) + 3D(8) + 3A + 4B.

D(14) = 8D(9) + 5D(8) + 4A + 8B.

D(15) = 13D(9) + 8D(8) + 8A + 12B.

D(16) = 21D(9) + 13D(8) + 12A + 21B.

...

그렇다. D(n)은 D(9), D(8), A, B의 선형 결합으로 나타낼 수 있다!

D(9), D(8)에 붙는 계수는 피보나치 수 \(F_{n}\), A, B에 붙는 계수는 \(F_{n} - (n \mod 2)\)의 꼴을 가진다.

\(F_{n}\)을 \(\lg n\)에 구해주면 전체 문제를 \(O(\lg n + |S|)\)만에 풀어낼 수 있다!

생각만 해내고 너무 구데기라서 마음 속에 묻어두기로 했는데, 실제로 이걸 의도한 문제가 있었다...  

---

POI97. Canoes

Tag : Naive, Two pointer(?)

문제 자체는 정말 한없이 쉽지만, 평소에 잘 안 쓰던 구현 방식이어서 메모해 두기로.

풀이는 한 문장이다. 무게로 정렬하고, 가장 무거운 사람부터 남아 있는 가장 가벼운 사람과 태우거나, 안 되면 혼자 태운다. O(nlgn) / O(n + w).

남아 있는 사람의 배열들을 deque처럼 생각할 수 있다. pop_back()을 계속해 가면서, 가장 가벼운 사람과 짝을 지을 수 있다면 추가적으로 pop_front()를 한 번 실행해주는 셈.

---

POI97. The number of n-k-special sets

Tag : DP, BigInt (>___<)

정말 누가 봐도 DP로밖에 풀 수 없는 문제같다. 식을 세워보자.

집합이 '인접한 원소'를 포함하지 않으므로 DP 정의 안에 n이 명시적으로 들어가야 할 것 같다.

합이 정확히 k인 집합의 개수를 구하는 건 오래 걸릴 것 같고, 합이 최대 O(n^2)니까...더러울 것 같다.

따라서 D(i,j) := (i를 최대원으로 가지면서 합이 j 이상인 집합의 개수)로 정의하면 생각보다 깔끔한 식이 나온다.

D(0,0) := 1 (by convention)

D(1,0) = 1, D(1,1) = 1

i > 1에 대해, D(i,j) = D(i-2, j-i) + D(i-3, j-i) + ... + D(0, j-i). (i > j인 경우 D()의 두 번째 parameter는 0)

이걸 그냥 풀어도 \(O(n^2k)\)로 AC를 받을 수 있다. 옛날 폴란드는 이렇게 혜자였구나...

하지만 S(i,j) := D(0,j) + ... + D(i,j)를 정의하면 S(i,j) = S(i-1, j) + S(i-2, j-i)라는 식을 얻을 수 있다. 시간복잡도도 \(O(nk)\)로 줄어든다. 

tmi) 스털링 수랑 닮아 보이지만 전혀 아니었다.

이 경우 답도 S(n,j)로 깔끔하게 얻을 수 있다.

하지만 이걸 아무 생각없이 C++로 짜면 WA가 나온다.

n = 100, k = 0인 경우를 생각하면 답은 \(F_{102}-1 \approx 9 \times 10^{20}\)으로 unsigned long long을 넘는다.

따라서 bigint를 구현하거나 내장 bigint를 지원하는 언어를 사용해야 한다. __int128로는 AC가 나올 것 같다.

---

POI97. Monochromatic Triangles

Tag : Math, Double counting

마르고 닳도록 울궈먹어지는 웰노운 문제인데, 그 시작이 여기인가보다.

수올 경력 1년인 탐레프도 아는 수학 - 웰노운이다.

삼각형의 유형은 RRR, RRB, RBB, BBB의 4개로 분류할 수 있다. 이 중에서 우리는 (RRR의 개수) + (BBB의 개수)를 구하고 싶다.

S = {(u, v, w) | u - v가 R, u - w가 R}을 생각하자.

이 경우 S의 원소는 \(\sum_{v} \text{Comb}(\deg (v), 2)\)가 된다.

그런데 S는 정확히 3개의 RRR 삼각형, 1개의 RRB 삼각형을 표현함을 알 수 있다.

따라서 3(RRR) + (RRB) = \(\sum_{v} \text{Comb}(\deg (v), 2)\)가 성립한다.

비슷한 집합을 2개 더 생각하면

2(RRB) + 2(RBB) = \(\sum_{v} \text{Comb}(\deg (v), 1)\text{Comb}(n - 1 - \deg (v), 1) \)

3(BBB) + (RBB) = \(\sum_{v} \text{Comb}(n - 1 - \deg (v), 2)\)

의 관계식을 얻을 수 있다. 이를 정리하기만 하면 (RRR) + (BBB)의 값을 얻을 수 있다.

---

POI97. Lecture Halls Reservation

Tag : DP

잘 알려진 '회의실 배정' 문제인데, 정확히 구간의 길이만큼 가중치가 있다.

그리디로는 어떻게 가지고 놀아봐도 잘 안된다. DP 전략을 사용하자.

모든 구간을 끝점으로 정렬하고, DP식을 다음과 같이 정의하면 된다.

D(i) : 1..i번 강의의 집합에 대해 얻을 수 있는 최대 이익

i번째 강의의 진행 여부에 따라 DP를 나누어 풀자.

D(i) = D(i-1) + D( (i번 강의와 겹치지 않는 최대 강의 index) ).

복잡도는 \(O(n \lg n)\)이다.