RUN@KAIST 7/26 방학 연습 풀이

1. 평균값 수열

수열의 초항 S1을 결정했다 하면, S2 ... SN까지 모든 숫자들이 도미노처럼 결정된다. S_{i+1} = 2 * m_i - S_i 이기 때문이다. 고로, S1을 결정하면 모든 수열의 원소를 알 수 있고, 이들이 단조 증가 하는지만 체크해 주면 된다. 

모든 S1을 다 해 볼 수 없으니, 대신 S1 = x라고 두고 부등식을 계속 쓰는 식으로 x가 답이 될 필요 충분 조건을 찾아보자. 이렇게 했을 때, 수열은 {x, 2m1 - x, 2m2 - 2m1 + x, 2m3 - 2m2 + 2m1 - x ... } 과 같은 형태로 구해진다. 단조 증가한다는 것은 인접한 항들이 모두 <= 관계라는 것이다. 고로, 입력을 통해서 단조 증가하는 수열을 만들기 위한 x의 범위를 구할 수 있다. 최종적으로, 이 범위 안에 들어가는 정수의 개수를 출력하면 된다. 

한편, 문제 제한 상 O(1) 메모리에 답을 찾아야 한다는 점에 유의하라.

2. 민코프스키 합

오해를 막기 위해 적자면 IOI 2004에는 이런 문제 없었다. 대신에 원래 이상한 output only 문제가 있었는데, BOJ에는 이 output only 문제의 체커를 짜는 문제 (...) 가 올라와 있을 뿐이다.

다각형 1에 속하는 모든 각각의 점 (x, y)에 대해서, 다각형 2를 (x, y)만큼 평행이동 한 것을 그렸다고 하자. 이것들의 합이 우리가 구하는 민코프스키 합이 될 것이다. 문제는 다각형 1에 속하는 점들이 무한하다는 것인데, 이 경우에는 민코프스키 합을 어떻게 구할까? 모든 각각의 점이 아니라, 다각형 1의 꼭짓점에 대해서만 평행이동을 시키고, N개의 평행이동된 다각형들에 대해서 컨벡스 헐을 구하면, 그 안에 속하는 모든 점들을 다른 다각형으로 덮을 수 있기 때문에 답이 된다. N개의 평행이동된 다각형들에 대해서 컨벡스 헐을 구하는 것은 사실 거기 속하는 모든 점들을 상대로 컨벡스 헐을 구하는 것과 똑같으므로, 결론적으로 다각형 1의 점이 (x_a, y_a), 다각형 2의 점이 (x_b, y_b) 라고 하면, 모든 NM개의 점 쌍에 대해서 (x_a + x_b, y_a + y_b) 를 가지고 컨벡스 헐을 구해서 답을 출력하면 된다.

사실은 컨벡스 헐을 구하지 않아도, 각 다각형의 둘레를 이루는 방향 벡터를 따서 머지 소트와 유사하게 합쳐주는 방식으로도 풀 수 있다. 이 역시도 벡터를 각도정렬하면 간단하게 풀 수 있다. 다만 각도 정렬이 그닥 간단하지 않은 게 함정.. 이 때는 시간 복잡도가 O((n+m)lg(n+m)) 으로 위 풀이보다 훨씬 빠르다.

3. 정원

사실 2015년 봄에 만들어 놓은 풀이 슬라이드가 있다. 약간 직무유기 같지만 (...) 그 풀이 슬라이드가 잘 되어 있는 것 같아 슬라이드로 대체.

(IOI05) 정원 분할.pdf