4월의 PS 일지 - Part 5

연습을 계속하고 있다. 21/26 문제를 해결하는 것으로 일단 종료. 4월에 시작한 연습이니까 4월 카테고리에 넣는다.

남은 문제들은 다 너무 어려워서 못 풀겠다. 일단 수학 PS는 질리도록 했으니 다른 것부터 하는 게 좋을 듯.

4월 30일

BOJ 5627 박테리아 (T, Diamond III)

박테리아의 위치와 방향을 하나의 노드로 생각하면, 박테리아의 움직임은 일종의 functional graph로 모델링할 수 있다.

이제 한 박테리아가 덫이 놓인 칸을 방문하는 것은, 방향에 따른 총 4개의 노드 중 하나를 방문하는 것과 같다.

박테리아는 각 노드를 아예 방문하지 않거나, 한 번 방문하거나, 첫 방문 후 주기적으로 (사이클의 길이에 따라) 방문하게 된다.

그러니 이 정보를 각 박테리아와 각 4개의 노드에 대해서 계산한 다음, 이를 합쳐주면 된다.

합치는 것은 기본적으로 중국인의 나머지 정리를 활용하되, 한 번 방문하는 경우를 조심하며 처리해야 한다.

또한, 실제 첫 방문 시간이 방문 주기보다 클 수 있다는 점을 유의해야 한다. 여러모로 구현에 조심할 게 많다.

다행히도 제한은 여유가 있어서 넉넉하게, 안전하게 구현해도 0ms AC를 받을 수 있다.

BOJ 12735 Boat (R, Diamond III)

멋진 조합문제. 좌표압축이 굉장히 필요해보이는 문제다. 좌표압축을 하면, 각 구간은 사실상 "같은 성질"을 만족하는 값들로 구성되어 있다.

$dp[x][y]$를 $x$번째 사람까지 선택이 끝났고, 현재 선택한 최댓값이 속하는 구간의 번호가 $y$ 이하인 경우의 수라고 하자.

$x$번째 사람이 선택하지 않는 경우, 현재 선택한 최댓값이 속하는 구간의 번호가 $y$가 아닌 경우는 이전에 처리한 DP 값으로 계산할 수 있다.

이제 남은 건 $x$번째 사람이 선택하고, 선택한 최댓값이 속하는 구간의 번호가 $y$인 경우다.

중복 카운팅을 막는 최적의 방법은, "처음으로 $y$번째 구간에서 값을 선택한 위치"를 고정하는 것이다.

이를 $k$라고 하자. 그러면 우선 $k-1$번째 사람까지 선택한 최댓값은 $y-1$ 이하가 되고, $dp[k-1][y-1]$이 나온다.

또한, $k$번째 사람, $x$번째 사람은 $y$번째 구간에서 값을 선택해야 하며, 나머지는 자유다.

하지만, $k$번째에서 $x$번째 사람들이 선택한 값은 증가수열을 이루어야 한다.

$k$번째부터 $x$번째 사람 중 $y$번째 구간에서 값을 선택할 수 있는 사람의 수를 $t$라 하자. (단, $k, x$번째 사람은 제외)

그러면 이 경우 $k$번째부터 $x$번째 사람이 선택할 수 있는 값의 경우의 수는 얼마가 될까?

우선 $t$명 중 $i$명이 실제로 값을 선택한다고 하자. 그러면 $k, x$를 포함해서 $i+2$개의 값을 골라야 하고, 이들은 증가해야 한다.

$y$번째 구간의 길이가 $L$이라면, 결국 $\displaystyle \sum_{i=0}^t \binom{t}{i} \cdot \binom{L}{i+2}$가 원하는 값이 된다.

이는 Vandermonde's Identity를 생각하면 쉽게 계산된다. $\displaystyle \sum_{i=0}^t \binom{t}{i} \cdot \binom{L}{L-i-2} = \binom{t+L}{L-2} = \binom{t+L}{t+2}$를 얻는다.

$k=x$인 경우를 특별하게 처리해주면, 문제를 해결할 수 있다. 이항 계수는 적당히 잘 계산하자. $\mathcal{O}(N^3)$의 동적계획법이 완성된다. 

BOJ 18480 Four Elements (H, Ruby V)

생성함수를 이용한다. 생성함수에 대한 식으로 답을 표현하는 게 상당히 귀찮다.

전형적인 포함-배제를 하듯이, 열심히 계수를 맞춰주면 되는데, 결론적으로 이런 식이 나온다. 검증해보자.

그러면 식이 대충 계산 가능한 다항식이 분자에 있고, $(1-x^t)$ 형태의 식이 분모에 있는 형태가 된다.

그런데 $\displaystyle \frac{1}{1-x} = 1+ x+x^2+ \cdots $를 이용하면 분모를 없애고 식 전체를 생성함수로 전개할 수 있다.

조금 머리를 굴리면, 댓글의 말처럼 뒤에 있는 네 개의 항을 $\mathcal{O}(n^3)$으로 단순 계산을 할 수 있음을 확인할 수 있다.

첫 번째 항인 $A(x)^4$가 약간의 문제가 된다. 이 경우 $\sum_{i=1}^n \left( x^{l_i} - x^{r_i+1} \right) $에 곱해지는 값은 $\displaystyle \frac{1}{(1-x)^4} = \sum_{k=0}^\infty \binom{k+3}{3} x^k$이다.

이제 $\displaystyle P(x) = \sum_{i=1}^n \left( x^{l_i} - x^{r_i+1} \right)$라 하고, 다항식 $f$의 $x^t$의 계수를 $[f]_t$라 하자.

우리가 구하고자 하는 값은 $\displaystyle \sum_{i=0}^s [P(x)^4]_i \binom{s-i+3}{3}$이다. 문제는 역시 $P(x)^4$를 구할 여력이 없다는 점이다.

이 문제를 Vandermonde's Identity로 해결할 수 있다. 우선 $\displaystyle [P(x)^4]_i = \sum_{j=0}^i [P(x)^2]_j [P(x)^2]_{i-j}$라고 써보자.

그러면 우리가 계산해야 하는 것은 $\displaystyle \sum_{i=0}^s \sum_{j=0}^i [P(x)^2]_j [P(x)^2]_{i-j} \binom{s-j-(i-j)+3}{3}$이다.

이제 저 이항 계수를 쪼개고 싶다는 게 명확해지고, $\displaystyle \binom{s-j-(i-j)+3}{3} = \sum_{l=0}^3 \binom{3-j}{l} \cdot \binom{s-(i-j)}{3-l}$로 이를 쪼갤 수 있다.

식을 제대로 쪼개고 나면 문제가 크게 어렵지 않다. $P(x)^2$에 대한 정보를 전부 계산하고, 정렬/부분합이면 된다.

은근 상수도 커서 (특히 $\mathcal{O}(n^3)$ 부분이 조금 상수가 크다) 구현을 나름 섬세하게 해야 했다.

5월 1일

BOJ 18297 Pixels (O, Diamond III) 

이 문제의 핵심 아이디어는, 첫 줄에 대한 press/avoid를 결정하면, 나머지는 전부 자동적으로 결정된다는 것이다.

첫 줄을 모두 결정하면, 두 번째 줄은 첫 줄을 맞춰주기 위해서 자동 결정이고, 세 번째 줄은 두 번째 줄을 맞춰주기 위해서 자동 결정이다.

이를 반복하면, 결국 모든 줄이 자동적으로 결정된다. 이때, 우리의 목표는 이때 마지막 줄이 정확하게 완성되는 것이다.

다른 말로 하면, "가상의 마지막 줄"을 하나 더 추가하고, 이들을 전부 avoid 하는 것이 "자동 결정되도록" 하는 것이다.

어쨌든 이를 전부 식으로 쓰면, $\mathbb{F}_2$ 위의 linear equation을 하나 얻을 수 있다. 

이건 가우스 소거 + bitset으로 쉽게 해결할 수 있고, 답 복원도 위 원리를 파악했다면 쉽게 할 수 있다.

구현 디테일이 조금 귀찮은데, $H > W$가 되도록 직사각형을 돌려줘야 한다. 가우스 소거가 $\mathcal{O}(W^3)$에 작동하기 때문이다.

또한, 기본적으로 각 칸의 press/avoid 여부를 첫 줄의 press/avoid 여부의 선형결합으로 표현하는데, 이 과정에서 토글링이 필요하다.

이 문제에서 조금 더 나아가면 Project Euler 707번을 해결할 수 있다. 물론 더 머리를 써야하는 문제다.

5월 2일

BOJ 14639 Replicate Replicate Rfplicbte (N, Diamond II)

아이디어 3개로 문제를 해결할 수 있고, 다른 풀이들도 대부분 이런 방식으로 생각하는 것 같다.

아이디어 1: Bounding Box의 크기는 한 번의 시행마다 양변의 길이가 2만큼 증가한다. 오류 여부는 상관없다.

아이디어 2: 오류가 없는 경우, 시행 이전에 모습을 복원하는 것은 간단한 DP로 어렵지 않게 할 수 있다.

아이디어 3: 오류가 있는 경우, 위 방식대로 복원을 하면 오류가 어떻게 전파되는가를 그려볼 수 있다.

그림을 실제로 그려보면 오류의 존재 여부 및 오류의 위치를 파악하는 방법을 알 수 있다.

또한, 오류의 위치를 알 때 오류를 수정하는 방법 역시 쉽게 파악할 수 있다. 

만약 오류를 수정해도 여전히 오류가 있다면, 그때는 "시행 이전의 모습" 자체가 없었던 것으로 보면 된다.

이제 남은 건 구현이다. 진짜 재밌고 멋있는 문제라고 생각하고, 17WF 남은 문제도 풀어봐야겠다. 

BOJ 18527 All Kill (I, Ruby IV)

정말 재밌게 푼 문제다. 깔끔하고 아이디어도 좋은 문제. 이 문제는 풀이만 써놓기엔 좀 애매해서 생각 과정도 적는다.

Part 1: 기본적인 관찰

결국 문제의 statement는 각 문제에 대한 아이디어는 시작 후 $0, 1, \cdots t-1$분 후 중 한 시각에 얻어지고, 각 확률이 $1/t$로 동일하며 이는 문제마다 독립적이라는 것이다. 이는 $p \cdot t^n$이 정수인 이유가 되고, 동시에 이 문제가 확률 문제가 아닌 카운팅 문제임을 시사한다.

Part 2: $n$이 작은 경우 직접 계산

우선 $x_1+x_2+ \cdots + x_n > t$인 경우에 답이 $0$임은 자명하다. $n=1$인 경우 답이 $t-x_1+1$임도 자명하다.

$n=2$인 경우를 열심히 계산했고, (이 계산은 어렵지 않다) $(t-x_1-x_2+1)(t-x_2+2)$를 얻었다. 

이는 문제의 답이 생각보다 간단한 형태를 가질 거라는 믿음을 나한테 줬다. 도움이 꽤 된듯.

Part 3: $n = t$, $x_1 = x_2 = \cdots = x_n = 1$인 경우

예제 2가 이런 경우고, $n=5$였다. 이때 예제 답이 $1296$이었는데, 이건 $6^4$다. 

뭔가 느낌이 쎄해서 $n=2$, $n=3$인 경우를 손으로 계산했는데, 각각 $3^1$, $4^2$가 나왔다.

여기서 나는 답이 $(n+1)^{n-1}$이라고 확신했고, 증명을 고민하기 시작했다. 근데 생각해보니 아는 내용이었다.

이 경우에는 중간에 문제가 바뀌는 걸 고민할 필요가 없다. 시간 안에 아이디어가 공급되는 것만이 중요하다.

각 문제의 아이디어가 나오는 시간을 $t_0, t_1, \cdots , t_{n-1}$이라 하면, 정렬 후 $i$번째 값이 $i$ 이하이면 된다. (0-index) 

이건 Parking Function과 같은 문제고, 예전에 한 번 공부를 했다. 여기서 도움을 정말 많이 받았다.

Parking Function하면 역시 원으로 바꾸고 자리 하나 더 만드는 방법이 너무 강력해서, 이를 사용해보기로 생각했다.

Part 4: $x_1 = x_2 = \cdots = x_n = 1$인 경우

기존 Parking Function에서 한 방식과 마찬가지로, 총 $t$개의 타임슬롯에 하나를 추가하고 이를 원형으로 바꾸자.

정당한 시간 배치가 되려면, 추가된 타임슬롯을 사용하지 않으면 된다. 여전히 문제는 Parking Function과 다르지 않다.

문제 큐에서 대기하고 있는 것을 자리가 차지되어서 다음 자리로 넘어가는 것으로 생각하면 된다.

이제 임의로 각 문제의 아이디어가 생각날 시간을 고르고 (즉, 각 차가 선호하는 자리를 고르고) 그 중 추가된 타임슬롯이 비게 되는 경우를 세자.

전체 경우의 수는 $(t+1)^n$이고, 그 중 $(t-n+1)/(t+1)$ 만큼이 추가된 타임슬롯을 사용하지 않는다. 

여기서 기존 Parking Function에서 사용되는 rotation argument가 그대로 사용된다.

그러니 답은 $(t-n+1)(t+1)^{n-1}$이 된다. 이는 $t=n$인 경우 Part 3의 결과와 모순되지 않는다.

Part 5: 본 문제 해결

이제부터 본 문제를 해결해야 한다. 역시 하나의 타임슬롯을 추가하고 원형으로 문제를 바꿔보자.

역순으로, $n$번째 문제부터 순서대로 타임슬롯을 고른다고 하자.

$n, n-1, \cdots , k+1$번째 문제에 대응이 되는 타임슬롯을 골랐다고 하자.

추가한 각 문제가 (한 문제를 연속된 한 구간동안 잡는다는 조건 때문에) "금지하는" 타임슬롯의 개수를 생각해보자.

조금 생각해보면 실제로 금지하는 타임슬롯의 개수가 특정 값으로 고정된다는 것을 알 수 있다. 경우 나누기가 필요 없다는 뜻.

이제 순서대로 타임슬롯을 골라준 다음, 추가된 타임슬롯을 사용하지 않도록 회전해주면 된다.

여기서 실제로 타임슬롯을 고른다는 것의 의미가 무엇인지 헷갈릴 수 있는데, 이건 잘 생각해보자.

BOJ 18574 Fractional XOR Maximization (E, Ruby V)

큰 그림은 꽤 뻔하지만, 디테일과 구현이 생각보다 까다로운 문제다.

큰 비트부터 보고, 그리디하게 가능하면 1이 XOR의 결과로 나오도록 하는 것을 반복해야 한다.

목표가 $x \in [a,b]$, $y \in [c,d]$에 대하여 $x \oplus y$의 supremum을 구하는 것이라고 하자.

우선, $a, b, c, d$ 각각에 $2^{-60}$을 곱해서 전부 $1$ 미만의 값이 되도록 하자. 나중에 $2^{60}$을 다시 곱하면 된다.

이제 $2^{-1}$에 해당하는 비트부터 시작해서, 큰 비트부터 차례대로 보자.

$a, b, c, d$가 현재 보고 있는 비트를 갖는지 여부를 $0/1$로 표현해보자.

$0000, 0011, 1100, 1111$의 경우에는 결정권이 없으니, 보고 있는 비트를 제외한 값으로 $a, b, c, d$를 대체한다.

$0001$의 경우에는 이 비트에서 XOR을 1로 만들어야 하므로, $y$의 비트를 $1$로 고정해야 한다. 이는 $c$를 교체하는 것과 같다.

$0100$의 경우에도 마찬가지로, $x$의 비트를 $1$로 고정해야 한다. 이는 $a$를 교체하는 것과 같다.

$1101$의 경우에는 $y$의 비트를 $0$으로 고정해야 하고, 이는 $d$를 교체하는 것과 같다.

$0111$의 경우에는 $x$의 비트를 $0$으로 고정해야 하고, 이는 $b$를 교체하는 것과 같다.

$0101$의 경우는 조금 특수한데, 조금 생각하면 이 경우에는 아예 답이 결정됨을 알 수 있다.

$1.000000$과 $0.1111111$을 XOR하면 사실상 가능한 최대의 값을 뽑아낼 수 있기 때문이라고 생각하면 쉽다.

이제 이를 반복해서 재귀적으로 계산하면 되는데, 문제는 이 과정이 무한히 반복될 수 있다는 것이다.

여기서는 $a, b, c, d$의 이진법 표기의 주기성을 이용하면 된다. 즉, 반복 주기가 되면 그 시점에서 재귀를 끊을 수 있다는 것이다.

이렇게 하면 풀이는 완성되는데, 생각보다 고려해야 할 것도 많고 구현도 힘들다. 디테일은 각자 채워 넣어보자. 

5월 4일

BOJ 18791 N의 배수 (2) (Y, Diamond III)

예전에 $\mathcal{O}(n^2)$ 논문이 있길래 이걸 구현해보려다가 뇌절을 심하게 하고 멘탈 나가서 놓은 문제였다.

풀이는 이 블로그에서도 언급한 EGZ 정리의 증명을 이용한다. 우선 합성수인 경우, 문제를 쪼개서 합칠 수 있다.

$n=ab$라 쓰자. 단, $a, b > 1$. $2ab-1$개의 수가 있을 때, $a$에 대한 문제를 여러 번 풀어 합이 $a$의 배수가 되도록 묶인 $2b-1$개의 그룹으로 만들 수 있다. $2a-1$개의 수를 가지고 합이 $a$의 배수인 그룹을 하나 만들고, 사용되지 않은 수를 다시 써먹는 것을 반복하면 된다.

이제 $2b-1$개의 그룹을 가지고 단순히 $b$에 대한 문제를 풀면 된다. 이는 구현이 귀찮지만 어렵지는 않다.

소수인 경우가 문제인데, 이는 여러 방법의 증명이 있다. (내가 좋아하는 것은 Chevalley-Warning) 

여기서는 Cauchy-Davenport 정리를 사용한다. 주어진 수를 정렬하여, $0 \le a_1 \le a_2 \le \cdots \le a_{2p-1} < p$라 하자.

이제 $a_i = a_{i+p-1}$인 $i$가 있다면 $i$부터 $i+p-1$을 전부 택하면 합이 자명하게 $p$의 배수가 된다.

그렇지 않다면, 주어진 수를 $\{a_1\}, \{a_2, a_{p+1}\}, \{a_3, a_{p+2}\}, \cdots, \{a_p, a_{2p-1} \}$로 분할하자.

첫 집합을 제외하면, 각 집합의 크기는 (중복 원소가 없으므로) $2$가 된다. 이제 순서대로 Cauchy-Davenport를 쓰면, 각 집합에서 한 원소를 골라서 $p$의 배수를 만들 수 있음을 얻는다. 이를 knapsack과 같은 방법으로 처리하면 끝. 참 멋진 문제라고 생각한다.

BOJ 18792 N의 배수 (3) (Z, Diamond I)

위 문제의 구현을 bitset 등으로 최적화하면 맞는다. 이상한 실수를 하나 해서 시간을 오지게 날렸다.