연습은 안하고 입코딩만 한다!
GCJ 2009 Round 2
A. Crazy Rows
- 그리디. 문제를 잘 읽을 것!
- small 은 n 이 작아서 그냥 무식하게 풀어도 된다.
- large 로 가려면 안되는데.. adjacent rows 만 바꿀 수 있다는걸 알면 그냥 풀 수 있다. -.-; 제일 무식하게 풀면 됨!
B. A Digging Problem
- 상태공간탐색.
- small 은 rows * 2^columns * columns 로 풀어도 되고..
- large 에서는 상태공간 개수를 줄여야 한다. 2^columns 를 줄여야 하는데.. 서로 떨어져 있는 두 개의 칸을 둘 다 파는 것이 의미가 없다는 것을 알면 좀 쉽다. 이번 줄에서 왼쪽 끝과 오른쪽 끝, 다음 줄에서 왼쪽 끝과 오른쪽 끝을 각각 기록하면 O(R*C^4) 가 된다. 흠. 이렇게 하면 풀긴 풀 수 있을듯?
C. Stock Charts
- 그래프 + 모델링 + 이분매칭.
- small 만 당시엔 무식하게 풀었었다.
- A 타임 시리즈가 B 타임 시리즈 위에 표현될 수 있다 라는 관계가 DAG 로 표현된다는 것이 포인트. 그러면 path cover 문제로 변환된다. DAG 의 path cover 는 이분매칭으로 풀 수 있다. 아.. 지금 봐도 쉽진 않군 -_-
D. Watering Plants
- 이분탐색 + 노멀라이제이션 + 기하.
- 일단 이분탐색을 해야 한다는 것은 자명한 듯 하고.. R 인 원 두개로 다 덮을 수 있냐를 보면.. 답을 노멀라이징하는 게 중요한데.. 우선 가능한 답들의 원들을 잘 움직이면 같은 plant 들을 덮으면서 두 개에 닿게 만들 수 있다. 덮을 plant 두개와 R 이 주어지면 두 개의 원을 정의할 수 있는데 얘들의 집합 전체만 있어도 답을 구할 수 있음~~~ 그러면 각 원마다 O(n) 으로 덮어지나 확인한 이후에 비트마스크로 확인하면 오우케이. O(n^4) 로 풀 수 있다.
B 나 짜봐야지
