USACO 2024-2025 December (Silver)

1. Cake Game

$N$이 짝수라는 조건을 놓치기 쉽다. 먼저 이 부분을 잘 읽어야 한다.

 

게임을 직접 손으로 돌려보며 다양한 관찰을 해 보면, 몇 가지 관찰을 할 수 있다. 대부분의 경우, 선공이 가운데쯤에 어떤 "큰 뭉치"를 만들고, 해당 뭉치를 마지막까지 안 빼앗기는 게 최적임을 관찰할 수 있다.

 

이것을 조금 더 엄밀하게 쓰면 다음과 같다: 맨 첫 턴에, 선공은 가운데의 두 더미를 합친다. 그리고, 후공이 양쪽 끝 더미 중 하나를 가져갈 경우, 선공은 자신의 더미가 가운데에 오도록 가운데 근처에서 적당히 다시 합친다. 이렇게 하면 선공은 자신이 만든 큰 더미를 끝까지 지켜 가져갈 수 있고, 후공은 그 더미를 제외한 나머지 더미를 모두 가져가게 된다.

 

더미를 만드는 과정에 따라, 마지막에 남는 더미는 초기에 놓여 있던 $N/2+1$개의 연속한 더미를 합친 것임을 알 수 있다. 후공 입장에서는 매 턴 왼쪽 끝/오른쪽 끝 중 어느쪽을 가져갈지를 적당히 조절해 선공이 가져가는 $N/2+1$개의 더미의 위치를 조절할 수 있다. 예를 들어, 만약 후공 입장에서 선공이 맨 오른쪽 $N/2+1$개의 더미를 가져가는 게 최적이라면, 후공은 계속 맨 왼쪽 것을 가져가면 되고, 그러면 선공이 마지막에 만드는 더미는 자연스럽게 맨 오른쪽 $N / 2 + 1$개의 더미가 된다.

 

여기까지 관찰하고 나면 (선공의) 답은 연속한 $N/2+1$개의 합 중 최솟값이라고 추정할 수 있다. 이것은 다음과 같이 증명할 수 있다.

 

선공이 $N/2+1$개의 더미를 가져간다는 것은 후공이 $N/2 - 1$개의 더미를 양끝에서 가져간다는 것으로도 생각할 수 있다. 최적해에서 후공이 가져가는 더미들은 양옆에서 $N/2-1$개의 더미를 뽑는 방법 중 합이 최대화되는 방법이다.

 

후공이 양옆에서 합이 최대화되도록 $N/2-1$개의 더미들을 가져가기로 마음을 먹었다고 생각해 보자. 선공이 어떻게 중간에 합치든, 후공은 그냥 원하는 방향에서 계속 가져가면, 후공의 턴이 최소 $N/2-1$턴 있음이 보장되므로, 저 모든 더미들을 가져갈 수 있다. (선공이 최선의 전략을 취하지 않는다면, 후공이 가져가는 더미가 늘어날 뿐이다.) 반대로 선공 입장에서는 후공이 어떻게 가져가더라도 항상 최소 $N/2+1$개의 더미는 지킬 수 있는데, 그때의 가능한 최솟값이 이 상황과 같다.

 

따라서 선공의 최고 전략과 후공의 최고 전략이 일치하게 되고, 답의 정당성이 증명되었다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n;
ll A[500002];

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%lld", &A[i]);

        ll L = n/2+1;
        for(int i=1; i<=n; i++) A[i] += A[i-1];

        ll ans = 1e18;
        for(int i=L; i<=n; i++) ans = min(ans, A[i] - A[i-L]);
        printf("%lld %lld\n", ans, A[n] - ans);
    }
}

2. Deforestation

그리디한 전략을 사용할 것이다.

다음과 같은 전략이 통함을 보일 수 있다.

• 나무를 왼쪽부터 차례로 본다.
• 해당 나무를 잘랐을 때 위배되는 조건이 하나라도 생긴다면 그 나무를 그대로 둔다.
• 해당 나무를 잘라도 상관없다면 그냥 자른다.

그러니까, 그냥 나무를 왼쪽부터 보면서 자를 수 있으면 자르는 전략이다. 엄밀한 증명을 하진 않겠지만, 증명의 직관은 다음과 같다. 현재까지 본 나무들, 그러니까 $[1, p]$번 나무들 중 어떤 것을 자를지 결정했다고 생각해 보자. 이때 $p+1$번 이후의 나무 중 자를 수 있는 나무들의 번호 중 가장 왼쪽에 있는 두 개를 $q$번과 $r$번이라고 하자. $r$번 나무를 잘랐을 때보다 $q$번째 나무를 잘랐을 때가 항상 이득이라는 걸 보이면 되는데, 남아 있는 조건들은 다음과 같이 네 가지로 요약할 수 있다.

• $q$번 / $r$번 나무 모두 포함하는 구간의 조건: 어디를 자르든 상관이 없다.
• $q$번 / $r$번 나무 모두 포함하지 않는 구간의 조건: 어디를 자르든 상관이 없다.
• $q$번 나무만 포함하는 구간의 조건: $r$번 나무를 자른다 하더라도 $q$번 나무를 자르는 데 아무런 영향이 없다. 따라서 그냥 자유롭게 $q$번 나무로 바꿔도 상관이 없다. 나중에 $r$번 나무를 자르지 못하게 되는 부작용이 있을 수 있는데, 어차피 이미 앞에서 나무 하나를 더 벌었으므로 문제가 없다.
• $r$번 나무만 포함하는 구간의 조건: 이 조건은 $q$번 나무를 자르는 데 아무런 영향이 없다. $q$번 나무를 이미 자를 수 있다고 가정했으므로, 그냥 $q$번 나무까지 같이 잘라도 문제가 없을 것이다.

이러한 연유로, 나무를 돌아보며 앞에서부터 그리디하게 잘라도 된다. 저기까지 생각했다면 제곱 풀이가 자명하게 나온다. 저걸 제곱보다 빨리 하는 방법은 다음과 같다.

 

먼저, 조건을 조금 다르게 전처리해둘 것이다. 처음에 입력으로 주어지는 조건의 형태는 $[l, r]$ 구간에 적어도 $v$개 이상의 나무가 있어야 한다는 꼴이다. 그런데 $[l, r]$ 구간에 초기에 있는 나무 개수를 계산할 수 있으면, 이 조건을 $[l, r]$ 구간에서 자를 수 있는 나무가 최대 $v$개이다 꼴로 바꿀 수 있다. 나무 $x$좌표를 정렬해 두고 이분 탐색 같은 걸 해서 이런 변환을 할 수 있다.

 

$x$좌표를 기준으로 왼쪽에서 오른쪽으로 스위핑한다고 생각해 보자. 스위핑을 쭉 하면서 현재까지 자른 나무의 수 $c$를 관리하고 있을 것이다. multiset $S$를 함께 관리한다.

• 만약 조건 구간의 시작점을 만났다면: 현재까지 자른 나무가 $c$개일 때, 이 구간 내에서 자를 수 있는 나무 개수가 최대 $v$개라는 것은, 조건의 구간 끝점까지 자를 수 있는 총 나무 수가 $c+v$라는 것이다. 다른 말로, 지금 관리하고 있는 $c$ 값은, 구간 끝점까지 갔을 때 $c+v$를 초과하면 안 된다는 조건을 얻는다. 이 $c+v$ 값을 $S$에 넣는다.
• 만약 나무를 만났다면: $S$의 최솟값을 확인한다. ($S$가 비어 있으면 $\infty$로 생각한다.) 이것은 현재 $x$좌표가 포함되어 있는 구간들에 대해, 구간 끝점에서의 $c$값 기준 중 최솟값과 같다. 즉, $S$의 최솟값이 $c$와 같으면 나무를 자르면 안 된다. 반대로, $S$의 최솟값이 $c$보다 크면 나무를 하나 자르고, $c$를 증가시킨다.
• 만약 조건 구간의 끝점을 만났다면: 해당 조건 시작점에서 multiset에 넣은 값을 제거한다. 이걸 처리하는 방법은 여러 가지가 있다. 힙 같은 걸 써도 되고, 아니면 그냥 구간 끝점을 따로 모아 두고 투 포인터 같은 걸로 처리해도 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Interval{
    int l, r;
    int at_most;
    bool operator<(const Interval &nxt)const{
        return l < nxt.l;
    }
};

int t;
int n, k;
int A[100002];
Interval intv[100002];

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &k);
        for(int i=1; i<=n; i++) scanf("%d", &A[i]);
        sort(A+1, A+n+1);

        for(int i=1; i<=k; i++){
            int v;
            scanf("%d %d %d", &intv[i].l, &intv[i].r, &v);
            intv[i].at_most = upper_bound(A+1, A+n+1, intv[i].r) - lower_bound(A+1, A+n+1, intv[i].l) - v;
        }
        sort(intv+1, intv+k+1);

        int pnt = 1;
        int cnt = 0;

        multiset<int> limits;
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        for(int i=1; i<=n; i++){
            /// L 처리
            while(pnt <= k && intv[pnt].l <= A[i]){
                pq.push({intv[pnt].r, cnt + intv[pnt].at_most});
                limits.insert(cnt + intv[pnt].at_most);
                pnt++;
            }
            /// R 처리
            while(!pq.empty() && pq.top().first < A[i]){
                limits.erase(limits.find(pq.top().second));
                pq.pop();
            }

            /// 조건 처리
            if(limits.empty() || *limits.begin() > cnt) cnt++;
        }

        printf("%d\n", cnt);
    }
}

3. 2D Conveyor Belt

그래프 문제로 생각할 수 있다.

 

일단 쿼리가 들어오는 걸 무시하고, 벨트 배치가 주어진 특정한 상황에서 문제를 해결하는 방법을 보자. 격자 그래프 $G$를 다음과 같이 구성한다.

• 벨트가 없는 칸에서는 $4$방향으로 인접한 칸으로 가는 간선을 만든다.
• 벨트가 있는 칸에서는 그 방향만으로 인접한 칸으로 가는 간선을 만든다.

이 그래프에서 격자 바깥의 아무 칸으로 갈 수 있는 칸의 개수를 구하면 된다. (문제는 격자 바깥으로 못 가는 칸을 구하는 거지만, 어차피 $n^2$에서 빼면 나오니까 그냥 격자 바깥으로 갈 수 있는 칸을 생각하자. 이쪽이 더 편하다.)

 

시작점이 변하고 끝점이 고정된 형태의 reachability 문제이므로, 그래프를 반전시켜서 생각한다. 모든 간선 방향을 반대로 바꿔 주면, 격자 바깥쪽에서 도달할 수 있는 정점들을 모두 찾는 문제가 된다. DFS나 BFS를 통해 $O(n^2)$에 해결할 수 있다.

 

이제 쿼리가 들어오는 경우를 생각해 보자. 벨트가 계속 생긴다고 생각하면, 벨트가 없는 칸에서 있는 칸으로 바뀔 때 그래프에서는 간선이 제거될 것이다. 그런데 간선이 제거되는 상태에서 reachability를 관리하는 것은 굉장히 어렵다. 쿼리 순서를 반대로 바꿔서 생각해 보자. 이렇게 하면 간선이 계속 추가될 때, 시작점에서 도달 가능한 정점 수를 계속 관리하는 것과 같다.

 

일단 모든 쿼리에 해당하는 컨베이어 벨트를 모두 입력받은 상태에서 시작해, 그 상황에서 그래프를 구성하고 $O(n^2)$ DFS/BFS를 돌려 마지막 쿼리에 대한 답을 구하자. 그리고 여기서부터 쿼리를 반대 방향으로 보며 컨베이어 벨트를 없애나갈 것이다. 즉, 그래프에 간선을 추가해줄 것이다.

 

그래프의 각 정점에 대해 해당 정점이 격자 바깥에서 도달 가능한지를 관리한다. 어떤 간선 $u \rightarrow v$가 추가되었을 때, $u$가 격자 바깥에서 도달 가능한 정점이 아니면 간선 추가만 해주고, 별다른 걸 해줄 필요가 없다. 만약 $u$가 격자 바깥에서 도달 가능한 정점이었고, $v$가 격자 바깥에서 도달을 못하는 정점이었다면, $v$는 격자 바깥에서 도달할 수 있는 정점으로 바뀐다. 이제 여기서부터 현재까지 추가된 간선들로 DFS를 돌려서, 격자 바깥에서 도달 가능한 정점으로 변하는 정점들을 모두 세어 주면 된다.

 

각 정점의 상태는 최대 한 번 (격자 바깥에서 도달 못함 -> 격자 바깥에서 도달할 수 있음) 바뀌므로, DFS의 총 시간 복잡도 합이 $O(n^2)$임을 보일 수 있다. 따라서 문제를 $O(n^2)$에 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
const char cc[]="RDLU";

struct Query{
    int x, y, d;
    Query(){}
    Query(int x, int y, int d): x(x), y(y), d(d){}
};

int n, q;
Query queries[200002];
int board[1002][1002];
bool chk[1002][1002];
int cnt;
int ans[200002];

vector<pair<int, int> > search_vec;

void search_cell(int x, int y){
    if(board[x][y] == -1){
        for(int d=0; d<4; d++){
            int tx=x+xx[d], ty=y+yy[d];
            if(chk[tx][ty]) search_vec.push_back({x, y});
        }
    }
    else{
        int d = board[x][y];
        int tx=x+xx[d], ty=y+yy[d];
        if(chk[tx][ty]) search_vec.push_back({x, y});
    }
}

void empty_search_vec(){
    while(!search_vec.empty()){
        int x = search_vec.back().first, y = search_vec.back().second;
        search_vec.pop_back();

        if(chk[x][y]) continue;
        chk[x][y] = 1;
        cnt++;

        for(int d=0; d<4; d++){
            int tx=x+xx[d], ty=y+yy[d];
            if(!chk[tx][ty] && (board[tx][ty] == -1 || board[tx][ty] == (d^2))) search_vec.push_back({tx, ty});
        }
    }
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) board[i][j] = -1;
    for(int i=1; i<=q; i++){
        int x, y; char c;
        scanf("%d %d %c", &x, &y, &c);
        int d=0; while(cc[d] != c) d++;
        queries[i] = Query(x, y, d);
        board[x][y] = d;
    }

    for(int i=0; i<=n+1; i++) for(int j=0; j<=n+1; j++){
        if(i==0 || i==n+1 || j==0 || j==n+1) chk[i][j] = 1;
    }

    for(int x=1; x<=n; x++) for(int y=1; y<=n; y++){
        search_cell(x, y);
    }
    empty_search_vec();
    ans[q] = cnt;

    for(int i=q; i>1; i--){
        int x = queries[i].x, y = queries[i].y;
        board[x][y] = -1;
        search_cell(x, y);
        empty_search_vec();
        ans[i-1] = cnt;
    }

    for(int i=1; i<=q; i++) printf("%d\n", n*n - ans[i]);
}