Codeforces Round 433 Div.2

문제 : http://codeforces.com/contest/854

---

A. Fraction

\(n \le 1000\)이기 때문에 다양한 풀이가 가능하다. 나는 생각을 최대한 안 하는 풀이인 Brute-force로 짰다.

Complexity : \(O(n lg n)\)

B. Maxim Buys an Apartment

ㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷ

min : 한 쪽에 아파트를 모두 몰아 놓았을 때이다. \(k=0 \vee k=n\)일 때 0, 아니면 1.

max : 그리디하게 2,5,8,....번째 아파트를 inhabited로 설정해 주면 \(min(2k,n-k)\)이 최대가 됨을 쉽게 증명할 수 있는데, 코딩할 때 생각을 너무 안 해서 System Test에서 참교육을 당했다. 으아아아아아아아

Complexity : \(O(1)\)

C. Planning

그리디하게 생각해 보면, \(k+i\)분에 출발할 수 있는 비행기 중 가장 cost가 작은 놈을 \(k+i\)분에 띄워야 함을 알 수 있다. (증명도 간단하다)

priority_queue의 자료구조를 이용하면 쉽게 처리할 수 있는데, andy627은 STL을 쓰지 않고 풀었다고 하고, paulsohn 형은 이 문제가 버블 정렬을 k회 실시한 후의 모습과 동치라고 한다. 다른 풀이가 가능해 보이는데 찾으면 추가하도록 하겠다.

Complexity : \(O(n lg n)\)

D. Jury Meeting

(생각 안해봄, 준비중)

E. Boredom

코포 하면서 E 처음 풀어봤어....

"교점을 하나라도 갖는 직사각형의 수"를 구하는 것보다는 "교점을 갖지 않는 직사각형의 수"를 전체에서 빼는 편이 나을 것이다. 그래서 쿼리로 들어온 직사각형의 4개 변을 기준으로 전체 영역을 자르면 4개의 변과 4개의 귀(?)를 얻는다.

결론만 말하자면 주어진 직사각형과 교점을 갖지 않는 직사각형의 개수는 $$\sum_{\text{side}} {}_{\text{|side|}}C_{2} - \sum_{\text{corner}} {}_{\text{|corner|}}C_{2}$$

$$(|S| : \text{number of points in region } S)$$

개가 된다. 어떤 corner에 속한 점의 개수는 2D query인데, 2D segtree나 BIT는 메모리 때문에 힘들고, 쿼리를 여러 번 날려야 하기 때문에(구현에 따라 \(4Q\) ~ \(9Q\)회) 쿼리당 \(O(lg^2 N)\)의 복잡도를 갖는 Merge sort tree도 힘들다. 그래서 난 Persistent Segment Tree로 카운팅을 했는데, Offline이라는 점을 이용해서 Query Sorting으로도 해결할 수 있다고 한다.

실전에서 처음 PST를 사용해봤고, 또 맞혔다는 점에서 감회가 좀 새롭다.

 Complexity : \(O(N lg N + Q lg N)\)