대회 링크

http://codeforces.com/contest/22

해설

A. Second Order Statistics

간단한 정렬 문제이므로 생략

B. Bargaining Table

O( N^{2} M^{2} ) $O( N^{2} M^{2} )$ 해법

• 모든 (i,j)$(i,j)$에 대해 top-left가 (0,0)$(0,0)$이고 bottom-right가 (i,j)$(i,j)$인 사각형 구간의 누적합(1의 개수)를 미리 계산한 테이블을 가지고 있으면 임의의 top-left가 (a,b)$(a,b)$, bottom-right가 (c,d)$(c,d)$인 구간의 1의 개수를 O(1)$O(1)$에 구할 수 있다.
• 이를 이용하여 모든 구간이 0인 구간 중 최대가 되는 사각형 구간이 답이 된다. 이 때 둘레는 (height+width) * 2 $(height+width) * 2$로 계산 가능하다.

O( N^{3} M^{2} )$O( N^{3} M^{2} )$ 해법

• 우선 문제 조건이 25^5$25^5$기 때문에 가능한 해법
• 각 행에 대한 누적합을 구하고 지정한 사각형 구간에 대해 O(N)$O(N)$으로 스캔하여 0만 존재하는 구간인지 확인하여 후보 구간을 선별한다.

• 선별된 구간 중 둘레가 최대가 되는 구간이 답이 된다.

• 소스코드(hyunhwan작성)

C. System Administrator

D. Segments

O(N^{2})$O(N^{2})$ 해법

• 좌표의 순서대로 (왼쪽부터 오른쪽으로) 이동하며 못을 박는다 하자. 이 경우에 이동시 못을 박지 않고 지나친 segment가 존재하면 올바른 답이 아니기 때문에, 무조건 박아야 한다는 사실을 알 수 있다. 또한 이 전략을 취할 때 한 segment에 대해 못을 박을 경우 맨 오른쪽에 못을 박는것이 좋다는 사실 또한 알 수 있다. 따라서 다음의 알고리즘을 통해 이 문제를 해결 할 수 있다.

1. O(N)$O(N)$에 현재 못박지 않은 segment 중 오른쪽 끝 좌표가 최소인 segment를 찾아 그 부분에 못을 박는다.
2. 이때 O(N)$O(N)$의 연산을 통해 이 부분에 포함되는 segment역시 못을 박았다 간주한다.
3. 앞의 과정을 모든 segment에 대해 처리했을 때 종료한다.

• 소스코드(hyunhwan작성)

E. Scheme