USACO 2024 December Contest Silver 1, 2번 문제

해당 글에서는 USACO 2024 December Contest Silver 1, 2번 문제의 풀이를 간단히 설명하고자 한다.

 

1. Cake Game

 

https://usaco.org/index.php?page=viewproblem2&cpid=1446

 

Elsie는 왼쪽, 오른쪽 끝에서부터 시작해서 연속하여 케이크를 원하는 대로 총합  N/2개를 먹을 수 있으므로 Elsie가 먹게 되는 케이크의 양은 처음 상태에서 Elsie만 N/2번 가져갈 때의 최댓값 이상이다.

 

Bessie는 다음과 같은 방법을 통해 Elsie가 최댓값보다 더 많이 가져가지 못하게 할 수 있다:

자신의 차례에서 놓여있는 짝수개의 케이크 중 가운데에 있는 두 케이크를 합친다. 이렇게 하면 Elsie의 차례에서 합쳐진 케이크는 홀수개의 케이크 중 가운데에 있는 케이크가 유일하므로 합쳐진 케이크를 먹을 수 없다.

 

결론적으로 Bessie는 연속한 N/2개의 케이크의 양의 합이 최소인 N/2개를, Elsie는 나머지를 먹게 되고 누적합으로 양을 시간 복잡도 $O(N)$으로 계산할 수 있다. 

 

2. Deforestation

 

https://usaco.org/index.php?page=viewproblem2&cpid=1447

 

각 나무를 잘라도 되는지의 여부는 해당 나무를 포함하는 구간에 대한 제약에 의해 결정된다.

 

다음과 같은 알고리즘을 생각하자:

먼저, 각 제약에 대해 '허용값'을 구간에서 제거해도 되는 나무의 개수(구간에 이미 있는 나무의 개수-제약이 제한하는 나무의 수의 최솟값)로 정의하자. sweeping으로 각 나무를 확인할 때마다 구간이 해당 나무를 포함하지 않게 된 제약의 허용값을 set에서 제거하고 구간이 해당 나무를 포함하게 된 제약의 허용값을 set에 추가하면서 set의 원소들의 최솟값이 1이상일 때만 나무를 제거하고 set에 있는 제약의 허용값을 모두 1씩 감소시키자. 그리고 제거한 나무의 개수를 세자.

 

이 알고리즘이 올바른 답을 내는 이유는 다음과 같다: 

위의 알고리즘에서 나무를 제거할 수 있는 임의의 경우 해당 나무의 위치를 a라 하고 지금까지 제거한 나무는 고정하자. a에서 제거하지 않는 경우를 제거하는 경우와 비교하면 제거하지 않으면 set에 있는 허용값이 1씩 감소하지 않지만 그러한 제약의 구간은 a를 포함한다. 여기서 제거되는 나무의 개수가 최대화될 때 제거되는 나무 중  a다음에 있는 나무 중 가장 앞에 있는 나무의 위치를 b라 하면 a대신 b를 제거하면 구간이 a와 b를 모두 포함하거나 포함하지 않는 제약은 제거되는 나무의 개수에 변화를 주지 않고 a만을 포함하는 경우 a이전의 나무는 고정되어 있고 b또는 그 이후의 나무는 구간에 포함되지 않으므로 개수가 커지지 않고 b만을 포함하는 경우 b를 포함하는 구간의 허용값이 1씩 감소하므로 개수가 커지지 않는다. 그러므로 a를 제거하는 것이 개수를 감소시키지 않는다. 이러한 논리를 앞에서부터 적용하면 된다.

 

구현할 때는 위에서 설명한 알고리즘에서 실제로 모든 허용값을 1씩 감소시키는 대신 지금까지 감소시킨 값의 총합을 계산해서 set에 허용값을 추가할 때 허용값에서 총합을 빼고 set의 원소들의 최솟값이 1이상인지를 확인할 때는 1대신 총합+1이상인지를 확인하면 된다. 시간복잡도는 $O((N+K)logN)$이다.