Three Squares (BOJ 10454, ICPC Daejeon Regional 2014)

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

Observation 1. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 세 정사각형으로 채울 때, 세 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.

-> 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. 케이스를 많이 나누는 식으로 증명이 되지 않을까.. 싶다.

Observation 2. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 두 정사각형으로 채울 때, 두 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.

-> 역시 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다.

Observation 3. X가 3SQ-sufficient 일때 X+1은 3SQ-sufficient이다.

-> 직관적인 설명 말고 역시 할말이 없다. 이는 Parametric Search의 가능성을 시사한다.

세가지 관찰로 즉시 O(NlgXi)의 풀이를 뽑을 수 있다.

일단, Xi를 고정시키는 Parametric Search가 O(lgXi) 이고, 이 후 세 정사각형 중 하나의 위치는 많아야 4개이므로 O(1) 이다. 한개의 정사각형으로 cover되지 않은 것을 두개의 정사각형으로 찾으면 되니, 그 set을 뽑는데 걸리는 시간이 일단 O(N)이고, 거기서 두 정사각형의 위치를 뽑는 경우의 수가 2개이다. 고로 O(NlgXi)로 문제를 해결 할 수 있다.

Parametric Search시 주의점은 (s + e) / 2 식으로 parametric을 돌릴 때 무려 오버플로우가 날 수 있다는 점이다. 난 처음에 inf를 뱉어내는 잘못된 코드를 짠 덕분에 이 사실을 일찍 깨닫고 멘탈붕괴했는데 (...) 어째 나빼고 다 당연하다는 반응 (......) 도움이 되었으면 좋겠다.

여담으로 Observation 1/2의 반례가 4개부터 잡힌다. 난이도가 다른 차원으로 올라가는 느낌이던데 관심있으면 풀어보길 (?)