problem solving 2016.09.24

푼지 몇달 된 것도 있고 얼마 전에 푼것도 있다. 

ONTAK2010. Garden

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

쉽게 생각할 수 있는 아이디어는 N^2개의 행을 잡고, 행 각각에서 교집합을 잡아서 O(N) 루프를 돌리는 것이다. N^3의 끔찍한 시간 복잡도를 가지기에 여기서 포기하기 쉽지만, 놀랍게도 sqrt decomposition을 통해서 큰 차이 없이 N^1.5 정도에 풀 수 있다.
행 R에 대해서, Xi == R을 만족하는 i의 개수가 N^0.5 이상일 경우 heavy row라 하고, 아닐 경우 light row라고 하자. 두가지 방법으로 문제를 해결한다.

 * 두 행 쌍 중 하나라도 light row일 때를 세주자. light row를 하나 잡고, 고를 수 있는 N^2개의 경우를 모두 시도한다. 해시 맵이나 이진 탐색 등으로 원소의 존재 여부를 체크하면 상수 ~ lgN 정도의 시간에 한 쌍을 해결할 수 있다. (상수라 하자) 모든 light row에 대해서 이를 시도하면 O(sigma(|S|^2)) <= O(sigma(|S| * N^0.5)) <= O(N^1.5).

 * 두 행 쌍이 모두 heavy row일 때를 세주자. heavy row 쌍을 하나 잡고, 교집합을 골라서, Xj - Xi == D인 쌍의 개수를 찾는다. heavy row의 개수는 N^0.5개 이하니, 한 row는 많아야 N^0.5번 조사된다. 고로 O(N^1.5)번.

잡설이지만 답의 하한 역시 N^1.5라 int 범위 안에서 풀 수 있다.

ONTAK2010. Party

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

친구 pair의 에지 수에 무려 “하한”이 걸려 있다. 도대체 왜인지 잘 모르겠다 싶었으나, N = 250일 때 친구 pair를 묶어서 컴포넌트를 묶으면 많아야 “46개”의 컴포넌트가 나온다. 친구 pair를 묶으면, 이제 적 pair만 남아있고, 문제는 V <= 46인 그래프의 Maximum Independent Set과 그 개수를 찍는 문제가 된다.

독립집합 문제가 NP인건 너무 잘 알려져 있고, 그래프에 특별한 조건도 없으니 brute force를 최적화 시키는 풀이를 생각해야 한다. 재밌게도 2^(n/2) 류의 meet in the middle이 먹힌다. 정점 집합을 V1, V2로 가른 후, 한쪽 사이드에서 백트래킹을 돌려 2^23개 정도의 독립 집합을 나열하자. 한쪽 사이드의 독립 집합을 결정할 시 다른 쪽 사이드의 독립집합에서 고를 수 없는 정점 셋들이 결정된다 (bitmask로 관리하자). 이제 반대쪽 사이드에서 빠르게 계산해야 하는 것은, “주어진 집합 S의 부분집합 중, 가중치 합이 가장 큰 부분집합과 그의 개수” 이다. 이는 O(2^n * n)에 precalculate 가능하다. http://koosaga.com/98

World Finals 2016. String Theory

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

답이 100 이하의 자연수일 테니, 답을 고정시키고 생각해보자. k quotation을 한번 치면, 아래에는 무조건 k-1 quotation들만 있어야 한다. 즉 최종 결과물을 생각해보면

k k-1 ... 2 1 (???????) 1 2 ... k-1 k

과 같은 모양일 것이다. 

이제 중간을 채울 수 있는지를 판별해야 하는데, 중간은 그냥 1-quotation 이라고 가정하면, 항상 채울 수 있다. (짝수이기만 하면 되는데 홀수는 자명히 안되니까) 결국

k k-1 ... 2 1 1 1 1 .... 1 1 1 1 2 ... k-1 k

과 같은 패턴을 만족하게 할 수 있는지 판별하면 된다. 

여담으로, 1-quotation은 다른 k와 다르게 "1 1"만 가능하다. 이것 때문에 10번 이상 틀렸는데 제발 조심 ㅠㅠ

BOI 2012. Mobile

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

모든 점의 x좌표가 다르다고 가정해도 무리가 없다. 두 점을 골랐을 때, 수직이등분선을 기준으로 왼쪽은 A가 가깝다. 오른쪽은 B가 가깝다.. 와 같은 관계를 유도할 수 있다. 여기서 Cross(A, B)를 A, B의 수직이등분선이 고속도로를 만나는 x좌표 라고 정의하자. 

스택을 사용해서 x좌표가 작은 순으로 삽입하는데, Cross(stk[stk.size()-2], stk.back()) > Cross(stk.back(), 넣을 점) 이면, stk.back() 점은 있으나 마나 한 점이다. 고속도로 상에서 어떤 위치를 잡아도 항상 그 점보다 가까운 점이 존재하기 때문이다.

이제 결과물 스택에 있는 원소들은, Cross(stk[x], stk[x+1]) <= Cross(stk[x+1], stk[x+2]) 를 만족한다. 이 때 고속도로의 [Cross(stk[x], stk[x+1]) , Cross(stk[x+1], stk[x+2])] 구간에서는 stk[x+1] 기지국이 제일 가깝다. 이러한 구간은 N개 생기고. 각각에 대해서 선분과 점 사이의 최대 거리를 구하면 된다. 선분의 끝점만 보면 되기 때문에 그 문제는 쉽게 풀 수 있다. convex hull trick과 상당히 비슷한 느낌의 문제이다. 

청소년을 위해 쉽게 설명한 Voronoi Diagram 같은 느낌이다 ㅋㅋ

POI 2004. Cave

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

트리의 center / centroid를 잡고 계속 트리를 쪼갠다와 같은 greedy가 생각되지만, 모두 틀린다 ㅠㅠ

먼저 이 문제를 일종의 coloring 문제로 생각할 수가 있다. 트리의 각각의 노드에 1 / 2 / 3 .. 과 같은 수를 부여하는데, 임의의 두 같은 수를 잇는 path 상에서 그 수보다 큰 수가 반드시 존재해야 한다. 이러한 성질을 만족하는 coloring을 구했을 때 이 coloring과 일대일 대응되는 질문 순서를 알아낼 수 있다. 목표는 최소의 수를 사용하는 것이다.

임의의 점을 루트로 잡고 dfs를 통해서 “Visibility set” 를 관리해준다. 각각의 정점에 대해서 visibility set은 “해당 정점의 서브트리에서 도달할 수 있는 수들의 집합” 이다. 도달할 수 있다는 것은, 현재 점과 그 수를 잇는 path 상에서 그 수보다 큰 수가 없다는 것을 의미할 것이다. 이제 현재 노드에서 해야 할 것은 자식의 visibility set을 토대로 현재의 visibility set을 만드는 것이다.

어떠한 수가 자식의 visibility set에서 몇번 나왔는지를 cnt[] 배열에 세 준다. cnt[x] >= 2 이상인 수 x가 있다면, 현재 노드에는 적어도 x+1 이상의 수가 필요할 것이다. 또한, cnt[x] != 0인 수 x를 현재 노드에 값으로 매길 수는 없다.

이제, 이 조건을 만족하는 최소의 x를 현재 정점의 번호라고 하고, 수 x + (x+1 이상의 수 y 중 cnt[y] == 1인 수들) 을 현재 노드의 visibility set에 넣는다. 이러한 coloring이 최소의 수를 사용한다고 한다. (나도 왠지는 잘 모른다..)

VPCPC 2014. An inexperienced slalomer

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

각각의 세그먼트에서 y축이 큰 쪽에 있는 점을 U, 작은 쪽에 있는 점을 L이라고 하자. 각각의 셋에서 컨벡스 헐 상에 포함되지 않은 점은 쓸모가 없으므로 날리면 된다.

이제 위쪽으로 convex한 체인 (L) 과 아래쪽으로 convex한 체인 (U)를 지나는 최대 두께의 선분을 찾으면 되는데, 이는 두 체인 간의 최소 거리이다. 풀이 적고 보니까 너무 허무하다..

JOI 2013. JOIOI 탑

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

J와 O의 역할은 자명하지만, I는 IOI에서 시작하는 형태의 I일 수도, *OI에서 끝나는 형태의 I일 수도 있다.

이러한 I의 역할을 정해주는 데 있어서 Parametric search는 도움을 준다. 답을 K라고 정했다면, 뒤에 있는 I의 역할은 모두 *OI를 닫는 I라고 가정해도 괜찮다 (정확히는, 그렇지 않다면, 그렇게 바꿀 수 있다.) 이제 I의 역할이 closing / opening으로 딱 정해졌으니 O(n)에 만들어진 탑의 개수를 세 주고, K를 넘는지 확인해 준다. 이진 탐색이 가능하니 O(nlgn). 

ARC 043D. 引っ越し 

http://arc043.contest.atcoder.jp/tasks/arc043_d

최소화해야 하는 값은 Sum(i < j) Pi * Pj * (Xj - Xi) 이며, 1 <= X1 < X2 … < XM <= N이어야 한다.

정말 보기 싫은 식인데, 이 식을 이렇게 전개해주면 굉장히 깔끔한 식이 된다 : Li = sum(Pj) (j <= i), Ri = sum(Pj) (j >= i) 일때, 답은 Sum(i = [1, N-1]) Li * R(i+1) * (Xi+1 - Xi).

이제 수많은 고민들이 너무 쉽게 풀린다. 먼저 Li, Ri가 고정되었을 때 저 식을 최대화해보자. (Xi+1 - Xi) = Yi 라고 하면 sum(Yi) <= N, Yi >= 1, Sum(i = [1, N-1]) f(i) * Yi 를 최대화해야 한다. f(i)가 가장 큰 위치에 Yi를 최대한 많이 몰아넣고, 나머지에 1씩 할당하면 최대화할 수 있는 식이다. 즉, 최대화해야 하는 게 (N-M)Max(Li * Ri+1) + Max(Sum(Li * Ri+1)) 이 됐다. S = Max(Pi) 라 했을 때 Ri+1 = S - Li이라는 점을 생각해보면 (N-M)Max(Li * (S - Li)) + Max(Sum(Li * (S - Li)) 식은 이렇게 N이 날아가버렸고 저 값을 최대화시키는 permutation만 찾으면 된다. 

최적해로 만드는 permutation에서 - Max(Li * (S - Li)) 값을 최대화해주는 Lp가 존재할 것인데, 그 때 [1 … p]에 속하는 subset을 고정시키고 생각해 보자. 이러한 subset을 전부 열거할 수 있으면, (N - M) * Lp * (S - Lp) 값을 더해준 후, 이 subset 두개에서 Max(Sum(Li * (S - Li)) 식을 잘 최대화해주면 된다. subset이 고정되었을 때, 각각의 subset에 대해서 Sum (Li * (S - Li)) 식을 최대화하기 위해서는, 왼쪽 set에서는 내림차순, 오른쪽 set에서는 오름차순으로 정렬해 주는 것이 최적이다. 

이제, subset을 DP를 통해서 열거해 보자. DP[pos][LSum][Rsum] = [1 .. pos] 까지의 원소를 열거했으며, 왼쪽 set에 있는 원소의 부분합은 Lsum, 오른쪽 set에 있는 원소의 부분합을 Rsum이라는 뜻이다. 이제 점화식을 유도할 수 있다.

 * DP[i][Lsum][Rsum] = min(DP[i-1][Lsum - Pi][Rsum] + Lsum * (S - Lsum), DP[i-1][Lsum][Rsum - Pi] + Rsum * (S - Rsum))

P를 내림차순으로 정렬해 놓으면, 왼쪽 set에는 내림차순, 오른쪽 set에는 오름차순으로 잘 들어간다.

여기까지 시간 복잡도는 M * (Ti * M) ^ 2이다. 여기서 망했다고 생각할 수도 있지만, Rsum = Lsum - sum(P[j]) (j <= i) 라 그 쪽은 굳이 인자에 넣지 않아도 된다. 고로 M^2 Ti 라서 시간 안에 나온다. 좋은 문제.