Educational Codeforces Round 121 (Rated for Div. 2) D. Martial Arts Tournament

Problem - D - Codeforces

어떤 배열이 존재하는데 칸막이 두 개를 설치해서 나눠진 3개의 그룹의 각각의 합보다 큰 최소의 2의 거듭제곱의 차의 합을 최소로 만드는 문제이다.

그냥 나이브하게 생각하면 O(N^2) 이 걸리기 때문에 나이브하게는 안된다.

그래서 그냥 직관적으로 한 개의 칸막이는 처음부터 끝까지 순서대로 확인하면서

두 번째 칸막이가 2의 거듭제곱보다는 같거나 작지만 가장 큰 수가 중간 구간에 만들어지게 움직이면 될 거라고 생각했다.

그래서 그렇게 풀었더니 AC가 나왔다.

근데 이게 최적의 해인지 자명한가? 를 따져보는데 뭔가 쉽게 자명하다는 게 증명이 안됐다.

그렇게 생각의 함정에 엄청난 시간을 소비했고 소비하고 난 후 더좋은 풀이도 떠올라서 글로 남긴다.

 

칸막이가 한 개만 있다고 할 때 두 개의 그룹을 최소로 만들고 싶다.

여기서 칸막이가 나이브하게 움직일 필요가 없고 왼쪽 그룹이 될 수 있는 2의 거듭제곱만 확인을 하면서 이분 탐색을 하면 된다.

여기서 자명함을 증명하는 데 있어서 의문점은 2가지가 있다.

1. 왼쪽 구간이 가장 가까운 큰 2의 거듭제곱과 가장 가까운 합이 아니고 오른쪽 구간도 가장 가까운 큰 2의 거듭제곱과 가장 가까운 합이 아닌 경우가 해가 될 수 있을까?

2. 오른쪽 구간이 가장 가까운 큰 2의 거듭제곱과 가장 가까운 합이 해일 수도 있지 않을까?

 

1번에서는 왼쪽 구간이 어떤 2의 x승을 넘지 않으면서 y를 더 가져갈 수 있다고 하자.

오른쪽 구간에서는 y만큼 빠질 것이고 만약 오른쪽 구간에서 y만큼 빠지면서 2의 거듭제곱 경계선을 넘어가는 경우와 넘어가지 않는 경우를 나눌 수 있다.

넘어가지 않는 경우는 오른쪽 구간에서 y만큼 더 추가한다는 추가 요금(?) 이 발생하지만

왼쪽 구간에서도 y만큼 더 경감한다는 것이 발생해서 변화가 없다.

넘어가는 경우에는 오른쪽 구간에서 y보다 작거나 같은 요금이 추가될 수 있다.

따라서 y만큼 빠지고 y보다 작거나 같은 요금이 추가가 된다면 결국 이득인 방향으로 가니까

그리디 적으로 이득이라는 것이 자명하다.

 

2번에서

오른쪽 구간이 가장 가까운 큰 2의 거듭제곱과 가장 가깝다고 왼쪽 구간에서는 가장 가깝지 않고 중간에 원소 (y) 한 개가 존재한다고 가정해보자.

왼쪽 구간에서 그 남은 원소 y를 가져갔을 때 오른쪽 구간에서는 y가 빠지게 된다.

왼쪽에서는 y만큼 이득을 보고 오른쪽 구간에서는 1번과 마찬가지 이유로 y보다 작거나 같은 값을 손해를 보게 된다.

결국 본전 아니면 이득이므로 2번도 틀리다는 것이 자명하다.

여기서 조금 더생각해 보면 왼쪽 구간에서 그 남은 원소 y를 가져갔을 때 오른쪽 구간에서 y가 빠지게 되는데

y가 빠질 때 2의 거듭제곱의 경계선을 넘어갈 경우와 넘어가지 않을 경우를 생각해 볼 수 있다.

넘어가지 않을 경우는 왼쪽이 y를 이득보고 y를 손해 보기 때문에 왼쪽이 가장 가까운 해이든, 오른쪽이 가장 가까운 해이든 상관이 없다.

넘어가는 경우에는 왼쪽이 y를 이득보고 오른쪽이 y보다 작거나 같은 것을 손해를 보지만 왼쪽이 넘어가고 1번째인 상태이기 때문에 오른쪽도 최선의 해고 왼쪽도 최선의 해라는 것을 알 수 있다.

결국 서로가 같은 최선의 해이 거나 서로가 최선의 해가 아닐 경우는 y를 이득보고 y를 손해 보기 때문에 상관이 없으므로

왼쪽 기준으로 2의 거듭제곱으로 이분 탐색으로 맞춰도 되고

오른쪽 기준으로 2의 거듭제곱으로 맞춰도 된다.

 

이제 칸막이 한 개를 두 개의 그룹으로 나눌 때에는 저런 식으로 해도 된다는 것을 알았다.

이제 칸막이 두 개를 확인해보자.

칸막이가 두 개일 경우에는 왼쪽, 중간, 오른쪽으로 나뉘게 된다.

왼쪽과 중간을 둘 다 이분 탐색으로 최선의 해를 찾으면 되지 않을까?라고 생각이 들 수 있지만

놀랍게도 이것은 성립한다...

 

만약 왼쪽이 최선이고 중간도 최선이고 왼쪽에서 어떤 y값을 빼도 2의 거듭제곱의 경계를 넘어가지 않고 이 상황에서 만약 왼쪽에서 y를 떼서 중간에게 줬다 쳤을 때 중간에서 y를 증가시키면서 2의 거듭제곱의 경계를 넘어간다고 가정해보자.

이 경우 중간에서 넘어간 x 만큼 오른쪽에게 줄 수 있고 ( 가장 최적일 때를 가정) 오른쪽에서 2의 거듭제곱을 경계를 안 넘겨서 x만큼 이득을 볼 수 있다 쳐도 손해 본 y보다 이득 본 x는 항상 같거나 작기 때문에 그리디적으로 안 좋다. ( 가장 최적일 때를 가정 했는데 그리디적으로 안좋다. )

 

만약 왼쪽이 최선이고 중간도 최선이고 왼쪽에서 어떤 y값을 빼도 2의 거듭제곱의 경계를 넘어가지 않고 이 상황에서 만약 왼쪽에서 y를 떼서 중간에게 줬다 쳤을 때 중간에서 y를 증가시키면서 2의 거듭제곱의 경계를 안 넘어간다고 가정해보자

이 경우 왼쪽에서 y만큼 손해를 보고 중간에서 y만큼 이득을 보기 때문에 똑같다.

그리고 중간에서 2의 거듭제곱의 경계를 안 넘어갔기 때문에 최선의 해이고 이는 처음 칸막이 하나로 나눴을 때의 증명과 같기 때문에 이미 최선이라 할 수 있다.

따라서 결국 이 문제는 O( (lgN)^2 )으로 풀리는 문제다.

n의 크기를 늘리거나 아니면 칸막이를 늘려서 문제를 만들었으면 더 어렵지 않았을까 생각이 든다.