_

1. JOI 문장

문제

사각형 한개의 모양을 바꿨을 때 상태가 바뀌는 \(2\times 2\) 사각형의 개수는 4개밖에 안되기 때문에 \(N\times M\)개의 사각형을 하나씩 바꿔보면서 최댓값을 찾아주면 된다.

2. 만두

문제

\(k\)개의 만두를 넣는다고 할 때 만두 가격의 합의 최댓값은 단순히 만두를 가격 순으로 정렬하여 가격이 높은 만두 \(k\)개를 고르면 쉽게 구할 수 있다. 또, \(k\)개의 만두를 넣는다고 할 때 상자에 써야 할 가격의 최솟값은 dp[상자 크기]에 최소 가격을 저장하는 knapsack DP로 구할 수 있다. 따라서 답은 모든 \(k\)에 대해 만두 가격 합의 최댓값 - 상자 가격 합의 최솟값을 계산하여 최댓값을 찾으면 구할 수 있다.

3. 도넛

문제

처음 고르는 구간의 시작점을 s라 하면 어떤 위치 e를 잡고, 나머지 부분을 최대한 같게 나누어 이등분 된 각 구간의 크기가 s부터 e 구간의 크기보다 크도록 나눌 수 있어야 한다. 나머지 구간을 이등분할 수 있는지는 단순하게 이분 탐색으로 양 구간을 s부터 e 구간의 크기 이상으로 나눌 수 있는지 검사하면 된다.

s를 고정하고 e를 점점 키운다고 가정하면 한계점 e'이 존재하여 e'이전 모든 e에서는 조건을 만족하고, e'를 넘는 모든 e에서는 조건을 만족하지 않는다는 것을 관찰할 수 있다. 따라서 이분 탐색을 통해 e'을 구할 수 있다. 따라서 시작점 N개에 대해 이분 탐색을 2번 하여 \(O(N\log ^{2}N\)에 답을 구할 수 있다.

4. 날다람쥐

문제

날다람쥐가 한번 높이 0인 상태에 도달하면, 그 이후 다른 나무로 점프한 후에도 높이 0인 상태를 유지할 것이라고 생각할 수 있다. (점프하기 전 그 이상으로 올라갈 필요가 없다.) 따라서 날다람쥐의 높이가 0인 경우와 그렇지 않은 경우로 나눌 수 있다.

날다람쥐의 높이가 0이 아니면, 시간 \(t\)에 날다람쥐의 높이 \(h = (처음 시작 높이) - t\)로 구할 수 있다. 따라서 날다람쥐의 높이가 0이 아닌 경우는 Dijkstra로 각 나무에 도달할 수 있는 최단 시간을 저장하여 처리할 수 있다. 다음으로 각 나무의 높이 0인 지점에 도달할 수 있는 최단 시간을 비슷한 방식으로 구해주면 답을 구할 수 있다.

5. 절취선

문제

가장 중요한 아이디어는 V - E + F = (연결된 선분 컴포넌트 개수)다. V, E, (연결된 선분 컴포넌트 개수)를 구하면 F를 구할 수 있다.

V와 E는 초기값을 N, 2N으로 잡고, 두 직선이 만날 때마다 V-E 값을 1만큼 감소시켜주면 된다. 이는 Segment Tree를 사용한 Plane Sweeping으로 처리할 수 있다.

연결된 선분 컴포넌트들의 개수를 구해주면 되는데, 이는 선분이 만날 때마다 Union & Find로 합쳐주고 마지막에 Group의 개수를 구하면 된다. Plane Sweeping으로 이를 처리하는 방법은 Lazy Propagation을 쓰는 것인데, Plane Sweeping을 하면서 Segment Tree의 구간에 그 구간을 덮는 선분들의 Group을 lazy 값으로 저장하여 새로운 선분이 추가될 때마다 Union & Find를 해주고, 구간의 선분을 없앨 때는 각 구간의 Lazy를 아래 구간으로 내려주고 구간에 저장된 Group을 없애면 된다.