1주차 (~5.1)

1. 스탬프렐리-2 (11986)

편의상 J를 1, O를 2, I를 3이라 하자.

pdp[i][j] : 1~i번째 상점까지 봤을 때 1~j번 스탬프까지 받은 경우의 수,

sdp[i][j] : n~i번째 상점까지 봤을 때 3~j번 스탬프까지 받은 경우의 수로 각각 정의하자. 각각의 점화식은 O(1) 점화식으로 매우 간단히 구해진다.

k번째 상점 바로 뒤에 스탬프 m을 가진 상점을 끼워 넣을 때 추가되는 경우의 수는 pdp[k][m-1] * sdp[k+1][m+1]이다. 이 중 최댓값을 mx라 하자. 그러면 답은 (끼워 넣은 상점에서 스탬프를 안 받는 경우의 수) + (받는 경우의 수) = pdp[n][3] + mx로 간단히 구해진다. 시간복잡도는 자명히 O(N).

2. POI (5462)

각 참가자를 (받은 점수, 푼 문제 수, -(ID))의 tuple로 놓고 내림차순 정렬했을 때 필립이 몇 번째에 오는지를 구하면 된다.

주어진 정보를 이용해 각 문제의 점수를 구해서 각 참가자의 점수 합을 구할 수 있고, 구조체 정렬을 이용하면 아주 쉽게 필립의 등수를 알 수 있다. 시간복잡도는 O(NT+NlogN).

3. 고용 (5461)

임금에 대한 비례 상수 k를 정하면, 그 때 고용 가능한 노동자들 중 자격증 레벨이 낮은 노동자부터 고용하는 것이 최적이다. 한편, k가 될 수 있는 후보는 각 노동자를 고용하는 데 필요한 최소의 k, 즉 (최소 임금)/(자격증 레벨) 중 하나로 좁혀진다.

이제 그 값의 오름차순으로 노동자들을 정렬하고, 차례대로 보면서 세그먼트 트리에 값을 갱신해주면 세그먼트 트리에서의 이분탐색을 이용해 어떤 k에 대해 고용할 수 있는 노동자의 수와 그 때 드는 비용을 O(logN)만에 계산할 수 있다. k의 후보의 가짓수가 O(N)이므로 시간복잡도는 O(NlogN).

4. Trapped in the Haybales (10760)

각 짚더미별로 (왼쪽에 있는 자기보다 작은 짚더미가 모두 뚫렸다면) 왼쪽에서 Bessie가 자신을 뚫을 수 있는지 여부를 계산할 수 있다. (이 값을 l[i]라 하자.) 이는 자신의 왼쪽에 있는 짚더미 중 가장 오른쪽에 있는 자기보다 크거나 같은 짚더미까지의 거리가 자신의 크기보다 큰지와 동치이며, set이나 세그먼트 트리 등을 사용하면 총 O(NlogN)만에 계산할 수 있다. 반대 방향의 경우(r[i])에 대해서도 똑같이 계산해 놓을 수 있다.

한편, 짚더미 사이 N-1개의 각 구간에 대해 그 구간에서 나갈 수 있는지 여부는, 왼쪽과 오른쪽으로의 짚더미의 increasing sequence를 생각했을 때 왼쪽 increasing sequence의 모든 r[i]가 true이고 오른쪽 sequence의 모든 l[i]가 true인 것과 동치이다. 그러면, 스택을 이용해 왼쪽과 오른쪽으로 각각 스위핑하며 모든 N-1개의 구간에 대해 거기서 나갈 수 있는지 없는지를 O(N)만에 알 수 있다. 답은 탈출 불가능한 모든 구간의 길이를 더하면 된다.  

5. Acrobat (13973)

A의 한 정점에서 출발해 모든 간선을 지나 다시 시작 정점으로 돌아오기 위한 충분조건은 다음의 두 가지이다.

1. A와 B의 각 정점이 짝수점이다.

2. B의 모든 정점이 연결되어 있다.

위 조건을 만족하도록 그래프에 가할 수 있는 조작은 "간선 Ai-Bj를 Aj-Bi로 바꾼다"(이하 1번 조작 or 조작 [1, i, j])와 "간선 Bi-Bj를 추가한다"(이하 2번 조작)의 두 가지이다. 1번 조작의 경우에는 정점 Ai, Aj, Bi, Bj의 홀짝을 바꾸고, 2번 조작은 정점 Bi와 Bj의 홀짝을 바꾼다.

A의 정점의 홀짝을 바꾸는 조작은 1번 조작 뿐이니 이를 이용해 먼저 A의 모든 정점을 짝수점으로 만들자. 조작 [1, i, j]를 실행할 수 있는 조건은 원래 간선 중 Ai-Bj가 존재하는 것이다. 원래 간선 Ai-Bj를 Ai-Aj로 바꾼 새로운 그래프에서 생각을 해 보자. 조작 [1, i, j]를 실행할 때, Ai와 Aj가 둘 다 홀수점이라면 둘 다 짝수점이 되고(즉, 없어지고), 둘 중 하나만 홀수점이라면 홀수점이 한 쪽에서 다른 한 쪽으로 옮겨간다고 생각할 수 있다. (둘 다 짝수점인데 이 조작을 실행할 이유는 없다) 그렇게 되면 새로운 그래프의 컴포넌트별로 홀수점이 짝수 개 있을 때 (홀수개 있으면 절대 홀수점을 없앨 수 없다) Spanning Tree를 아무 것이나 하나 잡아 그 트리에 해당하는 조작만 적절히 사용해 홀수점을 모두 없앨 수 있다. 컴포넌트 갯수를 C라 하면 N-C번 이하의 조작으로 가능하다.

이제 2번 조작으로 B의 모든 정점의 degree를 짝수로 만들면서 하나의 컴포넌트로 연결시키면 된다. (1번 조작을 어떻게 했든 A의 홀수점이 모두 없어졌다면 B의 각 정점의 상태는 하나로 결정된다.) 홀수점이 홀수 개 있으면 홀수점을 없앨 수 없으므로 불가능하다. 한편, 홀수점이 짝수 개이면, 짝수점이 있을 때와 없을 때의 두 가지 케이스로 나누면 둘 모두 쉽게 N번 이하의 조작으로 조건을 만족시킬 수 있다.

총 2N-1번 이하의 조작으로 주어진 조건을 모두 만족시켰다. 문제 제한이 왜 5N/2번인지는 의문이다.

6. 단층 (11989)