CEOI 2009 Day 2 Solutions

1. Logs

문제 제한부터 log를 용납하지 않겠다는 의지가 보인다. 일단 가장 처음 행부터 아래 행까지 스위핑을 해보자. 각각의 열마다 자신을 포함하여 위로 몇개의 연속한 1이 있는지 관리하는데, 이를 H[j]라 하겠다. 각각의 칸마다 H[j]를 구하는 것은 각 행마다 O(M)이면 충분하고, (바로 윗 행의 정보를 토대로 빠른 계산 가능) 이를 내림차순으로 정렬하면 답을 구할 수 있다. 문제는 시간복잡도가 O(NMlogM)이어서 TLE를 받게 된다. 이때 한가지 관찰을 해야되는데, H[j]는 항상 1씩 증가하거나 0이 되는 연산밖에 없어, 0이 되는 j를 앞으로 빼주기만 하면 윗 행의 정보를 토대로 O(M)에 정렬된 상태를 유지해 줄 수 있다는 것이다. 이를 이용해 O(NM)에 AC. 추가로, 입력받을때 문자열을 쓰지 않으면 TLE가 나므로 이에 주의하도록 하자.

 

2. Sorting

-생략-

 

3. Tri

쿼리로 들어오는 삼각형이 각각 x축과 나란하고 y축과 나란한 변을 가진 직각삼각형이라고 가정하자. 그렇다면 점들의 Convex Hull의 아랫부분을 Andrew Chain 따위로 구해준 뒤, 정해진 기울기에 대한 접선을 O(logN)에 그어주는 자료구조 하나만으로 충분하다. 이를 확장시켜 일반적인 경우에 대입해보자. 일단 주어진 점들을 각도 정렬한 뒤, 세그먼트 트리의 리프노드에 각각 담아주도록 하자. 그 뒤 세그먼트 트리의 조상에는 자식 노드에 있는 점들을 토대로 Convex Hull을 구해준다. 각각의 쿼리는, 구간합을 구하듯이 일정 범위에 해당되는 세그먼트 트리의 노드에 있는 Convex Hull을 대상으로 접선을 구해주는 것으로 해결할 수 있다. O(Nlog^2N+Qlog^2N)에 AC를 맞았고, 필요없는 최적화이긴 하지만 Convex Hull을 O(N)에 합쳐주는 테크닉을 통해 O(NlogN+Qlog^2N)에도 풀 수 있다.