안녕하세요

5178 시간 초과 문제에 대한 질문입니다. 참고로 문제 이름이 시간 초과고 결과는 WA입니다.

문제는 프로그램이 주어지고 프로그램의 시간 복잡도가 두 변수 x, y에 대한 다항식이 되는데 이를 big-O notation으로 처리한 가장 간단한 식을 출력하도록 되어 있습니다.

우선 제 풀이는 파싱을 통해 x, y의 지수를 구하고

big-O의 정의에 따라 어떤 항 A가 제외될 조건은 어떤 항 B, C가 존재해서 A <= c * (B+C)를 만족하게 되는 경우가 되는데

x, y의 지수를 평면 상에 올린 뒤 상수를 붙인 AM>=GM을 사용하면

선분 BC의 아래쪽에 A가 존재하는 경우와 A <= c * (B+C)는 필요충분합니다.

그림으로 나타내면 다음과 같은 영역에 해당합니다 (경계포함)

즉 어떤 점 A에 대해 다른 점 B, C가 저렇게 A를 포함하는 영역을 만든다면 제외해도 됩니다.

순서를 B>C인 경우만 본다면 (B의 x가 C의 x보다 더 크거나, x가 같다면 y가 더 클 때)

a) 반직선 BC가 +y방향이면 BC보다 왼쪽에 있으면서 B의 x보다 x가 작고 C의 y보다 y가 작은 경우에 해당하므로 ccw로 풀 수 있습니다. 위의 그림의 영역입니다.

b) B = C인 경우 역시 따져주면 됩니다. 어떤 한 점보다 x와 y가 동시에 작은 점을 제외하므로 타당합니다.

c) 반직선 BC가 -y 방향이라면 어차피 구한 영역 전체가 B보다 x와 y가 둘 다 작은 영역에 포함되므로 고려하든 하지 않든 상관없습니다.

그래서 이러한 조건을 만족하는 두 점이 존재하는 모든 항을 제외하고 남은 점의 집합은 우상단만 있는 볼록 껍질의 형태가 됩니다.

이때, 볼록 껍질 위의 어떤 점도 제외할 수 없습니다. 그 항을 제외한 식 f로 원래의 식 g <= c * f를 항상 만족할 수 없습니다.

증명은, 생각하면서 한 건 아니지만 대략 생각해보면 맞는 것 같습니다.

1. 볼록 껍질 안쪽의 점은 모두 제외된다.

껍질에서 인접한 것끼리의 영역을 보면 모든 영역이 포함되므로 맞습니다.

2. 위와 같이 제외하면 볼록 껍질의 점은 제외되지 않는다.

볼록 껍질의 점의 안쪽끼리 하면 볼록성에 의해 껍질 위의 점은 제외되지 않습니다.

볼록 껍질 위의 점끼리 하면 볼록성에 의해 인접하지 않은 다른 껍질 위의 점은 제외되지 않습니다.

볼록 껍질 위의 점과 안쪽의 점의 영역 역시 껍질 위의 점을 포함할 수 없습니다.

채점이 50%까지 가길래 논리적 오류인줄 알았는데 대소문자 이슈였네요 .....
코드는 너무 정답에 가까워서 삭제했습니다 아이디어는 다른 분들이 참고해도 되겠죠?