http://icpckorea.org/archives/1774


A. Circuits


직사각형의 폭은 별로 중요하지 않음.
세그먼트 트리를 만들어서 직사각형을 잘 넣어두고
선분 하나를 아래에서 위로 올려가면서 (이 때, 직사각형의 위 아래 부분만 해보면 됨)
해당 선분에 닿고 있는 직사각형을 세그먼트 트리에서 제거하면서 개수를 센다.
그리고 세그먼트 트리에서 남은 직선을 놓을 위치를 결정한다. (이는 구간의 최대 값을 구하면 되니까 O(log N))
따라서 O (N log N)에 최대 값을 구할 수 있다.


B. Cosmetic Survey


d(a, b) > d(b, a)인 점들에 대해서만 a->b 경로를 만들어주자.
이후 플로이드-와샬을 이용하면 모든 X, Y에 대해 S(X, Y)를 구할 수 있다. O(M^3)


C. Disks Arrangement


큰 거 - 작은 거 - 큰 거 - 작은 거 ... 순서대로 배열하는게 최적이라는 사실만 안다면 풀 수 있다.
정 모르겠으면 N이 작을 때 경우를 직접해보자.


D. Go Latin


파이썬이 없으니까 알아서 잘


E. LED


오차 최대치로 파라메트릭. 제한 사항이 많으니까 주의하면서 구해야 함.


F. Parentheses


N의 크기가 적으므로 재귀를 마음놓고 이용할 수 있다. 함수를 몇 개만 잘 정의하면 재귀식이 예쁘게 나온다.
C-expression과 ICPC-expression을 한 번에 다 처리하려고 하지말고, 각각을 확인하는 함수 2개를 만드는 편이 편하다.


G. Secret Code


경우를 나누어 확률을 열심히 구하면 예쁜식이 나온다. 정렬할 때 부동소수점 형식 대신 분수를 사용하도록 하자.


J. Starwars


예선의 Suffix-Freeness와 비슷한 아이디어로 풀면 된다.


K. TV Show Game


조건 3개 중 2개 이상을 만족해야 한다는 말은,
(1) 조건 1이 성립하지 않으면 조건 2, 조건 3 무조건 성립
(2) ...
(3) ...
임을 생각하면 2-SAT 문제로 변환할 수 있음을 알 수 있다.
가능한 아무 답이나 출력해도 되므로 간단하게 구현 가능하다.


L. Working Plan


일단 누군가 일해야 하는 날짜와 명수가 정해져있다는 사실을 알 수 있다.
그러면 매일 현재 남은 일이 많은 사람부터 일을 시키자. (물론 이미 일하고 있거나 휴식중이면 제외)
일을 먼저 하면 이후 선택 범위가 넓어지기 때문에, 결국 방법이 있다면 위의 알고리즘으로 찾을 수 있다.