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

겨우겨우 두 문제를 풀어냈다. 진도 따라잡기도 벅찰 거 왜 한다고 해서...

오늘 푼 문제들 (2 / Total 10)

POI96. Knights  (Div1A)

POI98. One-sequences (Div1A)

고민중인 문제들

POI96. Castle

POI04. 스타 대회

---

Spoiler Alert.

This section is intentionally left blank.

---

POI96. Knights

Tag : DP, Bitmask

Description에 심각한 오류가 있다. 문제에서 주어지는 set Z는 나이트가 있어야 할 곳이 아니라 있으면 안되는 곳이다. 현재 ko_osaga님이 지적해둔 상태.

보드의 세로가 3밖에 안되기 때문에 자연스럽게 3 * n DP를 생각해볼 수 있다.

하지만 체스보드에 놓여 있는 것이 "나이트"라는 공식화하기 어려운 대상이기 때문에, 결국 (i-1)열까지 위치한 나이트의 정보를 전부 들고 다녀야 한다는 생각이 든다. 당연히 이건 시간, 메모리 모두 만족시키지 못하고...

나이트가 행, 열 중 한 방향으로 이동할 수 있는 최대 길이는 2. 따라서 i열에 나이트를 배치하는 문제에서 (i-2)열보다 왼쪽에 위치한 나이트는 아무 의미가 없다. 따라서 이전 6개 나이트의 정보만 들고 다니면 i열의 나이트 배치 문제를 해결하기에 충분하다.

D(i, k, b) := i열까지, 총 k개의 나이트를 배치하는 경우의 수, 이 때 이전 6개의 나이트의 상태(bit - string)은 b이다.

코딩이 꽤 까다로운 편이다. Z의 원소에 의해 나이트를 놓을 수 없는 칸, 기존의 나이트에 의해 나이트를 놓을 수 없게 되는 칸을 모두 고려해야 한다. i열에 놓고 싶은 나이트의 상태를 X라는 3비트 정수로 나타내고 작두를 타며 비트마스킹을 해야 한다. 이 이상의 디테일은 혼자 생각하는 편이 더 간단할 것 같다.

나이트를 최대 $3n$개밖에 놓을 수 없으므로, 시간 복잡도는 O(n * 3n * 8 * 64) ~ $O(1536n^2)$이 된다. n = 100을 대입하면 연산량이 10^7에 육박함에도 불구하고 커팅이 잘 되는지 4ms가 나왔다.

jh05013님의 블로그에 $O(512n)$ 정도로 보이는 솔루션이 있다.

왜인지 모르겠지만 경우의 수는 long long으로 충분하고, 토글링을 이용하면 메모리를 줄일 수 있다.

09.25) 크리님이 SA로 답이 $10^{15}$까지 나오는 데이터를 만드셨다. 조만간 롱롱 뚝배기가 터질 것 같다...

---

POI98. One-sequence

Tag : Observation, Parity

$a_{1} = 0, |a_{i}-a_{i+1}| = 1$인 수열의 길이가 $n$, 합이 $S$가 되게 a를 만들어야 하는 문제이다.

문제 자체는 간단한 기우성 관찰로 풀 수 있지만, 문제를 봤을 때 빠르게 이 관찰을 떠올리기까지는 수련이 필요할 것 같다.

우선, 절댓값이 $\frac{n(n-1)}{2}$보다 큰 수는 만들 수 없음이 명백하다.

그리고 $S$와 $\frac{n(n-1)}{2}$의 기우성이 다른 경우에도 만들 수 없다. 알아내는 방법은 여러 가지가 있겠지만, 다음의 argument가 깔끔하다.

$$a_{1} = 0 \equiv 0 (\text{mod} 2) \\ a_{2} - a_{1} \equiv 1 (\text{mod} 2) \\ \vdots \\ a_{i} - a_{i-1} \equiv 1 (\text{mod} 2) \\ \therefore a_{i} \equiv i-1 (\text{mod} 2), \ a_{1} + \cdots + a_{i} \equiv \frac{i(i-1)}{2} (\text{mod} 2)$$

나머지 경우, 즉 S의 절댓값이 $\frac{n(n-1)}{2}$ 이하이면서 기우성도 맞아 떨어지는 경우에는 전부 만들 수 있을까? 놀랍게도 정말 만들 수 있다. 실제로 a를 construct하는 방법은 편의에 따라 다를 수 있는데, 내 기본 아이디어는 수열의 합을 $\frac{n(n-1)}{2}$에서 2씩 떨굴 수 있다는 것이다.

$b_{i} = a_{i+1} - a_{i}$라고 하고, $b_{i} = 1$인 0 < i < n을 '증가점', $b_{i} = -1$인 i를 '감소점'이라고 하자.

초기에는 모든 i가 증가점이고, 합은 $\frac{n(n-1)}{2}$가 된다.

이 때 k < n이 감소점이 되는 경우, 수열의 합이 정확히 2(n-k)만큼 감소하게 된다.

만약 $S \ge \frac{n(n-1)}{2} - 2(n-1)$인 경우는 종료. 아니라면 1을 감소점으로 설정한 뒤, b[2..n]에 대해서 동일한 문제를 풀면 된다.

구현은 놀랍도록 간단하지만, 나는 이걸 폰코딩으로 풀다가 4번이나 틀려버렸다.