2016.04.19 problem solving

Soap Time (CF 118E)

http://codeforces.com/contest/185/problem/E

일단 45도 돌려서 chebyshev distance로 생각하고, 지하철역이 없을 때에 대한 corner case를 처리해주자.

먼저 minsub[i] = (i번 정점에서 가장 가까운 임의의 지하철역까지의 거리) 를 정의하고, 구한 후 시작하자. 시간 제한이 넉넉하기에 아무 방법이나 썼는데, 난 2d range tree를 짠 후 parametric search를 돌리는 방식으로 O(nlg^3n)에 해결하였다.

문제 해결에 있어서는 최댓값을 최소화하기 때문에 직관적으로 parametric search가 떠오른다. parametric search를 구현하는 것이 가장 어려운 부분이다. 일단 답이 X라고 가정을 하고, 이를 만족하는지 확인하는 알고리즘을 제시한다.

사람이 주어진 위치로 가는 경우는 두가지가 있는데

 * 1. 사람 -> 가장 가까운 지하철 역 -> 임의의 위치에서 가장 가까운 지하철 역 -> 주어진 위치. distance : minsub[i] + (subway - pos)

 * 2. 사람 -> 주어진 위치. distance : (person - pos)

이 값들의 최대를 최소화하는 위치를 구해야 한다.

이 때 아이디어는 minsub[i]의 최댓값을 고정시키는 것이다. 이 한도를 L이라고 하면 구해야 하는 위치는 다음 조건을 만족하는 직사각형 영역이 된다.

* 임의의 지하철역에서 거리가 X - L 이하인 점이어야 하며

* minsub[i] > L 을 만족하는 모든 사람들에 대하여, 거리가 X 이하여야 한다.

사람들이 minsub 순으로 정렬되어 있다면 , minsub[i] > L 을 만족하는 모든 사람들에 대하여, 거리가 X 이하인 영역을 two pointers 방식으로 저장할 수 있다. 이 영역이 지하철역에서 거리가 X - L 이하인지 확인하려면, 영역을 좌우로 X - L만큼 넓혀본 후, 이 안에 지하철역이 있는지를 2d range tree에서 질의한다.

이렇게 짜면 2d range tree에 nlgn번 쿼리를 날려서 O(Nlg^3N)이다. 시간 제한이 관대해서 잘 돌아간다.

NP-hard (COCI 13/14 #2/4)

https://www.acmicpc.net/problem/9520

아주 중요한 관찰, 문제에서 말하는 "방문 순서"는 b1 > b2 > .. > bi < bi+1 < .... < bn 형식의 bitonic sequence이다. 즉 방문 순서가 저렇게 생긴 permutation이라는 것과, 문제에서 말하는 올바른 경로라는 것이 동치이다.

bi는 당연히 1일 것이므로, 저기서부터 시작하는 것이 좋을 것이다. dp[i][j] -> (i = bx) > bx+1 .. > bi < bi+1 ... < (j = by) 형태의 수열을 만들었다고 정의하자. 왼쪽에 max(i, j) + 1 / 오른쪽에 max(i, j) + 1 점을 붙이는 식으로 이러한 수열을 모두 열거할 수 있다. (bitonic tour랑 비슷한 원리이다.) 이를 모두 파악시 아주 짧은 O(N^2)코드를 짤 수 있다.

경비병 (APIO 2012)

https://www.acmicpc.net/problem/4003

http://koistudy.net/?mid=prob_page&NO=594

일단. 숨어있는 닌자가 없는 곳을 초기에 마킹해놓고, 숨어있는 닌자가 있다는 내용을 전하는 쿼리만 추출해내자. (즉, 이 글에서 이제 구간이라고 하면 그 구간 안에 닌자가 있다는 뜻이다) 이건 선형 시간에 전처리 가능.

O(NMlgN) 풀이를 생각해보자. 최소의 닌자를 사용해서 숲을 덮는 그리디 알고리즘이 존재한다.

* 1. N개의 수풀을 std::set에 넣고 불가능한 위치를 모두 사전에 제거해준다.

* 2. 닌자가 있다고 보고된 구간들을 끝점 정렬한 후, 만약에 해당 구간에 닌자가 없다면 std::set에서 가능한 가장 큰 점을 사용한다.

이제 N개의 점에 닌자가 확실히 숨어 있는지는, 그 점을 불가능한 위치로 만드는 dummy interval을 넣고, 최소의 닌자가 K+1 이상이거나 아예 배정이 불가능한지를 판별하는 것으로 가능하다. 최소의 닌자로 배정할 수 있다면, 나머지 구간에 닌자를 넣어서 나쁠 것이 없기 때문에 그것만 확인해줘도 괜찮다. corner case는 불가능한 위치가 N - K개인 경우니까 이걸 잘 처리해주자.

NlgN 최적화를 하기 위해서는 어떠한 구간이 쓸모없다는 사실을 알아야 한다. 정확히 말해서, 구간 [s, e]에 대해서 s <= s', e' <= e를 만족하는 [s', e']가 존재하면, 구간 [s, e]가 전하는 정보는 의미가 없다. 이렇게 하면 모든 구간이, s < s'일 때 e < e'를 만족하게 만들 수 있다.

이러한 관찰은 그리디 알고리즘을 더 간단하게 만든다. 일단. 끝점(=시작점) 정렬된 구간에 대해서 다음과 같은 정보를 저장하자. O(M)에 가능하다.

 * dpl[i] = [0, i] 구간을 덮으려면 몇명의 닌자가 필요?

 * posl[i] = 그 닌자 중 마지막 닌자의 위치는 어디?

 * dpr[i], posr[i] = [i, M) 에 대해서 동일하게 처리.

이제, 임의의 X가 주어졌을 때, 해당 점을 제외했을 때의 최적 배치를 O(lgN)에 계산할 수 있다. ei < X, si > X를 만족하는 구간들은 위에서 저장된 정보들로 빠르게 덮어버릴 수 있고, 나머지 구간에 대해서 배치가 가능하다면, 많아야 2번의 배치만으로 충분함을 쉽게 증명할 수 있다. (X 왼쪽 / 오른쪽에 2개 이상을 배치하는 최적 전략은 모순이라는 것을 보이자) 2번만 콩콩 뛰어주면 된다. 좀 이것저것 잔처리가 많아서 구현은 짜증난다.

DRZAVA (COCI 15/16 #2/6)

https://www.acmicpc.net/problem/11592

못풀것처럼 생긴 문제라 바로 풀이를 봤는데 풀이가 좀 천재.

일단은 임의의 그룹의 크기가 K를 초과하면 항상 저러한 성질을 만족하는 부분집합을 고를 수 있음을 쉽게 알 수 있다. (비둘기 집의 원리를 사용해서 증명하자.)

이제 답에 대해서 binary search를 하자. 답을 D라고 했을 때 해당 점에서 D 크기의 원안에 들어오는 점들을 열거만 할 수 있다면 좋겠지만 이럴 때 원은 다루기 참 골치아프다.

대신 점 (X, Y)에서 [X-D, X] x [Y-D, Y+D] 크기의 직사각형을 생각해보자. 이러한 직사각형은 8개의 D/2 크기의 정사각형으로 쪼갤 수 있고, 각각의 정사각형 내부에 K개의 원소가 있다면 자기들끼리 그룹을 이루고 답이 항상 생긴다. 고로, 만약에 직사각형 안에 8K개 이상의 점이 있으면 항상 D는 답이고, 아니면 8K개 이하의 점을 brute force해서 에지를 일일히 만들어주면 된다. std::set으로 plane sweeping하면 쉽게 이 문제를 해결할 수 있고 이 과정이 O(NK + NlgN)이다. 그래프가 만들어졌다면 컴포넌트마다 냅색을 해줌으로써 쉽게 답을 구할 수 있다.

PROKLETNIK (COCI 15/16 #7/6)

https://www.acmicpc.net/problem/11959

영역의 끝점 E를 고정시키고 생각해보자. 두개의 스택을 가지고 다니는데

* stack 1 : [1, E) 구간의 점 i 중, 임의의 j에 대해서, i < j && ai > aj를 만족하는 j가 없는 점 i들을 가지고 다니는 스택

* stack 2 : [1, E) 구간의 점 i 중, 임의의 j에 대해서, i < j && ai <= aj를 만족하는 j가 없는 점 i들을 가지고 다니는 스택

굉장히 부자연스러운 설명이지만 어떻게 이것보다 잘 설명하는지 전혀 모르겠음을 이해해주길 바란다. 저런 스택 만드는건 익숙하면 쉽다. 옛날 ioi 2004 empodia 풀때 썼던 방식이랑 비슷하다. (http://amugelab.tistory.com/entry/Empodia-IOI-2004)

E를 끝점으로 하는 부분수열은 현재 stack 2의 top() + 1 ~ E까지에서만 시작지점을 가질 수 있다. 또한, 시작점은 stack 1의 원소여야 한다. 이 정보를 기억해두자.

두 스택에 E를 넣고 진행한다. 위에서 구한 범위에 있는 stack 1의 원소들을 모두 순회하면서, [s, e] 구간이 valid한 부분 수열임을 체크해두자. 이걸 체크해두는 건 aux[]라는 배열을 잡고, aux[s] = max(aux[s], e)를 반복적으로 해주면 된다.

쿼리는 끝점을 정렬해 두고, E점이 쿼리의 끝점일 때마다 쿼리에 대답해주자. 쿼리의 답은 max_element(aux[s, e])이다.

이렇게 하면 O((N+Q)N)이다. 즉 좀 느린데, 놀랍게도 저 연산들은 모두 세그먼트 트리로 O(lgN)에 계산할 수 있다. 연산들을 간단히 만든 후 잘 생각해보기 바란다 (아주 trivial한 연산들은 아니다) 이제 시간복잡도 O((N+Q)lgN).

아인타는 분할 정복으로 풀었다. 디테일은 생략하는데 분할정복을 구성해서 스택으로 O(N)에 conquer하는 방식이다. (스택은 위에 쓴 거랑 비슷하게 사용한다.) 나도 풀 때 분할 정복으로 시도했는데 conquer에서 이상하게 망해서 (왜 망했지..) 결국 sweeping으로 해결하는 정해를 봤다. (위에 서술한게 정해) 신기한 풀이다.