PS 이야기

문제 ↓ 상당히 까다로워 보이는 문제다. 대회 당시 만점자가 많지 않지만 매우 어려운 문제에 속하진 않는다. 문제는 2차원으로 되어 있지만, 1차원인 경우 부터 먼저 생각해보자. 1차원인 경우 각 셀들이 모두 연결되어 있어야하므로, 셀들이 일직선으로 연결되어있는 선분 하나만 존재할 것이다. 이 때 각 셀 쌍들이 이동하는 거리는 $|X_i-X_j|$ 이다. 이런 셀들이 N개 있을 때 O(N lg N) 정렬 후, O(N) 만에 각 셀 쌍들의 거리 합을 구해줄 수 있다. 전체 해법 설명에 앞서, 서브태스크 3 푸는 법을 먼저 소개하겠다. 서브태스크 3에 있는 조건들이라면 각 셀 쌍들의 이동 거리는 1차원일 때와 비슷하게 $|X_i-X_j|+|Y_i-Y_j|$ 이다. 이때 x 좌표의 거리와 y 좌표의 거리를 독..

문제 ↓이 문제를 풀기 위해서 꼭 해야되는 것이 존재한다. 바로, 레오나르도의 최적 전략을 코딩하는 것이다. 레오나르도의 최적 전략에 대한 설명은 문제에 적혀있다. 레오나르도의 최적 전략을 O(N lg K) 만에 해결할 수 있어야한다. O(N) 만에 각 물감이 다음에 같은 종류의 물감이 언제 등장하는지를 계산할 수 있다. 그 이후, 힙(heap)이나 우선 순위 큐(priority queue) 자료구조를 이용하면 O(N lg K)만에 해결 가능하다.서브태스크 1,2,3 그리고 서브태스크 5의 부분 점수를 노리는 방법은 직관적으로 생각할 수 있다. 각 Request 별로 비계에서 PutBack 해야되는 물감의 번호를 비트로 넘겨주면 된다. 각 Request 별로 차지하는 비트 수는 lg N 이다. 따라서 서..

문제 ↓순서대로 라운드가 진행된다. 라운드 (S[i],E[i])가 진행 되면, 구간 (S[i],E[i])에 있던 실력이 제일 좋은 기사만 남고 나머지는 지워진다. 이렇게 한 명의 기사만 남을 때 까지 라운드는 진행된다.프로그램 수행 시간을 좀 더 줄이기 위해서, 기사를 지우지 않아도 된다. 라운드에서 살아남는 기사는 가장 실력이 좋은 기사다. 기사들이 탈락하고 새로운 라운드의 진행을, 기사들이 탈락하지 않는 라운드 진행으로 바꿀 수 있다. 따라서 매 라운드 (S[i],E[i])가 실제로 의미하는 초기 상태에서의 구간 (S'[i],E'[i])를 구할 수 있다. 이 때, 구간 (S'[i],E'[i]) 들은 서로 포함 관계에 있거나 아예 만나지 않는다. 즉, 교차하지 않는다.우리는 이제 새로운 실력 $R$의 ..