USACO November 2011 Contest > Gold

 

골드 셋도 맛보고 싶어서 도전해봤다. 옛날 대회라 그런가 든든국밥 문제들만 나와서 비교적으로 쉽게 풀 수 있었던 것 같다.

 

---

 

5922: Above the Median (P4, Segment Tree)

 

젠장 또 median이야!

고정된 값 $X$에 대해 주어진 수열의 contiguous subsequence 중 median이 $X$ 이상인 것들의 개수를 구하는 문제이다. $X$보다 크거나 같은 $a_i$를 $1$로 치환하고 $X$보다 작은 $a_i$를 $-1$로 치환하면, 놀랍게도 합이 0 이상이 되는 연속 부분 배열의 개수를 구하는 문제가 된다! 연습 중에는 merge sort tree로 누적 합을 관리하는 방법을 사용했는데 $(N\log^{2}{N})$, 그냥 누적합 배열에서 inversion counting을 하는 풀이가 제일 깔끔한 것 같다. $(N\log{N})$

 

Median을 새로운 관점으로 볼 수 있어서 재밌었다.

 

---

 

5923: 바이너리 스도쿠 (P1, Bit DP)

 

제약 조건이 너무 적어서 일단 백트래킹은 안 돌아갈 것 같다.

생각해보면 $i$번째 행을 채우는 데 $0 \sim i-1$번째 행이 정확히 어떻게 채워져있는지는 알 필요가 없고, $0 \sim 8$번째 열에 현재까지 쓰여진 숫자 합의 홀짝성만 알면 충분하다.

추가로 현재 행이 지나는 3X3 정사각형에 쓰여진 숫자 합의 홀짝성을 비트마스킹을 이용해 표현해주면 $i$번째 행을 채울 때 필요한 상태를 잘 정의할 수 있다. 

 

정확히는 dp[i][prv][sq]: i번째 행을 채우고 있는데, 현재까지 열의 상태가 prv이고, 3X3 정사각형의 상태가 sq인 상태로 정의하면, 행 간 상태 전이를 $O(2^9)$정도에 할 수 있고 전체 상태는 $O(9 \cdot 2^9 \cdot 2^3)$개 이므로 문제를 풀기에 충분하다.

상태를 전이할 때는 현재 행의 가능한 비트마스킹을 전부 탐색하는 식으로 구현한다. 비트 간 XOR 연산을 활용하면 그나마 깔끔하게 구현할 수 있다.

 

처음으로 (태그, 티어 등 안 보고)자력솔한 P1 문제였다..! 솔직히 P1급은 아닌 것 같고,.. 컨닝 문제와 비슷한 아이디어를 사용하므로 P3~P2가 적당할 것 같다.

(여담: 연습 끝나고 티어 깠을 때 골드 하위에 백트래킹 문제였으면 키보드를 부쉈을지도 모른다...)

 

---

 

5924: Cow Steeplechase (P3, 이분 매칭, 기하학)

 

이분 매칭 국밥 문제이다. 선분을 정점, 선분과 선분의 교차를 간선으로 하여 그래프로 모델링하면 방향이 다른 두 선분만 교차하므로 이는 이분 그래프임을 알 수 있다. 주어진 문제는 이분 그래프에서의 최대 독립 집합을 구하는 문제이며, 이는 $|V|$ - (최대 매칭의 개수)임이 잘 알려져있다!