USACO 2023-2024 December (Silver)

1. Bovine Acrobatics

문제를 읽어 보면 다음과 같은 그리디한 전략이 통함을 알 수 있다.

• 각 타워의 맨 아래에 있는 소들의 집합 $S$를 관리하자. $S$의 크기는 항상 $m$ 이하여야 한다.
• 크기가 작은 소부터 차례로 보면서, 다음 과정을 반복한다. 현재 보는 소의 크기를 $x$라고 하자.
  • 만약 $S$ 안에 $x - k$ 이하의 크기를 가진 소가 있다면, 그 소 아래에 현재 소를 넣을 수 있다. 즉, $S$에서 $x - k$ 이하의 크기를 가진 원소 하나를 빼고, $x$를 넣는다.
  • 그렇지 않고, $|S| < m$이라면, 새로운 타워를 하나 만든다. $S$에 $x$를 넣는다.
  • $\min S > x-k$이고, $|S| = m$이라면, 이 소는 사용할 수 없다.
• 위 과정과 같이 하면 사용한 소의 개수가 최대가 된다.

증명을 하진 않았지만 직관적으로 위 방법에서 소를 더 집어넣을 수 있는 방법이 없음을 이해할 수 있다.

 

저걸 naive하게 짜면 구현에 따라 subtask 1 또는 subtask 2를 받게 된다. 구현을 효율적으로 하는 방법은 $S$를 소의 크기에 소의 마릿수가 대응되는 std::map 형태로 관리하는 것이다. 그러면 같은 크기의 소들을 한 번에 처리해줄 수 있고, 약 $O(n \log n)$ 정도 시간 복잡도에 문제를 해결할 수 있다. 사실 자료구조 자체는 가장 왼쪽/오른쪽에 삽입/삭제만 하는 것으로도 충분해서, std::deque 등으로도 문제를 풀 수 있고, 이러면 선형도 가능하다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, k;
pair<ll, ll> A[200005];

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<=n; i++) scanf("%lld %lld", &A[i].first, &A[i].second);
    sort(A+1, A+n+1);

    ll tot = 0, ans = 0;
    map<ll, ll> mp;

    for(int i=1; i<=n; i++){
        while(!mp.empty() && mp.begin()->first <= A[i].first - k && A[i].second){
            pair<ll, ll> p = *mp.begin();
            int x = p.first;
            ll v = min(p.second, A[i].second);

            if(v == p.second) mp.erase(x);
            else mp[x] -= v;
            mp[A[i].first] += v;
            ans += v;
            A[i].second -= v;
        }

        if(A[i].second && tot < m){
            ll v = min(A[i].second, m - tot);
            mp[A[i].first] += v;
            tot += v;
            ans += v;
        }
    }

    printf("%lld", ans);
}

2. Cycle Correspondence

최근 USACO 실버 문제에서는 역대급으로 쉬운 문제 같다.

 

먼저 $A$와 $B$ 양쪽 사이클 모두에 포함되지 않는 정점은 얼마든지 같은 점으로 배정해줄 수 있다. 만약 한쪽 사이클에만 포함된다면 같은 점이 될 수 없다.

 

양쪽 사이클에 모두 포함된 경우가 문제인데, $A$와 $B$의 방향이 같다고 한다면, $A$를 $t$번 회전했을 때 $B$가 되어야 한다. 이때 $A$와 $B$에서 순서가 같아지는 점들은 $A_{x+t} = B_{x}$ 꼴인 점들이다.

 

$A$와 $B$ 모두에 포함된 원소 $x$에 대해, $A$와 $B$ 내에서의 위치 $aidx[x]$와 $bidx[x]$를 구한다. 이때 $aidx[x] - bidx[x]$의 최댓값을 찾으면 가장 많이 매칭해줄 수 있는 점의 개수를 찾을 수 있다.

 

$A$와 $B$는 사이클을 둘러보는 순서가 역방향 관계일 수도 있어서, $aidx[x] + bidx[x]$의 최댓값까지 고려해 줘야 한다.

 

$O(n)$에 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int A[500005], B[500005];
int ac[500005], bc[500005];

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=k; i++) scanf("%d", &A[i]), ac[A[i]] = i;
    for(int i=1; i<=k; i++) scanf("%d", &B[i]), bc[B[i]] = i;

    int ans = 0;
    for(int i=1; i<=n; i++){
        if(!ac[i] && !bc[i]) ans++;
    }

    map<int, int> mp;
    for(int i=1; i<=n; i++){
        if(ac[i] && bc[i]) mp[(ac[i]-bc[i]+k)%k]++;
    }
    int a1=0;
    for(auto [x, v]: mp) a1 = max(a1, v);

    mp.clear();
    for(int i=1; i<=n; i++){
        if(ac[i] && bc[i]) mp[(ac[i]+bc[i])%k]++;
    }
    int a2=0;
    for(auto [x, v]: mp) a2 = max(a2, v);

    printf("%d", ans + max(a1, a2));
}

3. Target Practice

조금 처리해 줄 게 많은 케이스워크 문제이다.

 

문제의 핵심은, 중간에 command 하나를 바꿔도 위치가 많아야 $2$만큼 달라진다는 사실이다. 따라서 명령 하나를 바꾼 뒤 위치로 가능한 것이 $-2$ 이상 $2$ 이하의 최대 다섯 개뿐이다.

 

먼저 명령을 하나도 바꾸지 않았을 때 맞추는 표적의 개수를 구한다. 다음으로, 각 명령을 바꾸는 모든 경우에 대해 표적의 수가 어떻게 달라지는지를 구할 것이다.

 

5개의 std::map을 관리한다. 각 std::map을 다음과 같이 초기화하자. $d = [-2, 2]$에 대해, std::map $mp[d]$를 선언하고,

• 초기에 위치 $0$ 대신 위치 $d$에서 시작했다고 할 때,
• 이후 $N$개의 명령을 차례대로 따르며 사격을 할 때, 각 표적 $x$에 대해 해당 표적 $x$를 맞춘 횟수를 $mp[d][x]$ 꼴로 관리한다.
• 이때 맞춘 적이 없는 표적은 맵에 넣지 않는다. 즉, 맞춘 표적의 개수는 mp[d].size() 와 같이 알아낼 수 있다.

이제 바꿀 명령어 포인터를 앞에서부터 옮기면서, 차례로 다음 과정을 반복한다.

• 만약 $i$번째 명령이 사격이었다면, 해당 명령으로 인해 쏘아진 표적을 각 맵에서 제거한다. 이때, 평범하게 명령을 수행했을 때의 위치가 $x$였다면, $x+d$를 맵에서 제거해야 한다. (물론, 해당 위치에 표적이 없었을 수도 있고, 그러면 아무 일도 없을 것이다.)
• 이후, 모든 가능한 변경에 대해 최종 표적의 수가 어떻게 되는지를 계산한다. 이 시점에서 $mp[d]$는 처음에 위치 $0$에서 시작하고, $i$번 명령 직전까지 잘 수행하다가, $i$번 명령을 수행하는 대신 갑자기 $d-2$만큼 오른쪽으로 이동하고 나머지 명령을 수행했을 때 맞춘 표적들을 기록하고 있을 것이다. F로 바꿨을 때 현재 위치의 표적지를 포함해야 한다는 사실에 주의하자.
• 이후, $i$번 명령을 반영한다. 즉, 만약 $i$번째 명령이 사격이었다면, 해당 명령으로 인해 쏘아진 표적을 각 맵에 추가한다.

풀이가 잘 이해가 되지 않는다면, 맵에서 제거되는 위치들은 "명령 하나를 바꾼 이후" 처리되는 표적들이고, 맵에서 새로 추가되는 위치들은 "명령 하나를 바꾸기 이전" 처리되는 표적들이라고 생각하면 된다. 즉, prefix 부분과 suffix 부분을 함께 관리하기 위해 map의 "suffix"에 해당하는 것들을 하나 하나씩 "prefix"의 부분으로 바꿔준다고 생각하면 좋다.

 

문제를 $O(n \log n)$에 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int on[1000005];
int arr[100005];
char str[100005];
int loc[100005];
map<int, int> mp[5];

void add(map<int, int> &mp, int x){
    if(!on[x+n]) return;
    mp[x]++;
}

void del(map<int, int> &mp, int x){
    if(!on[x+n]) return;
    mp[x]--;
    if(mp[x] == 0) mp.erase(x);
}

int main(){
    scanf("%d %d", &k, &n);
    for(int i=1; i<=k; i++) scanf("%d", &arr[i]), on[arr[i]+n]++;
    scanf("%s", str+1);

    { /// 정방향 타겟 구하기
        int x = 0;
        for(int i=1; i<=n; i++){
            if(str[i] == 'L') x--;
            else if(str[i] == 'R') x++;
            else loc[i] = x;
        }
    }

    for(int i=1; i<=n; i++){
        if(str[i] != 'F') continue;
        for(int d=0; d<5; d++){
            add(mp[d], loc[i] + d - 2);
        }
    }

    int ans = (int)mp[2].size();
    int x = 0;
    for(int i=1; i<=n; i++){
        /// 제거
        if(str[i] == 'F') for(int d=0; d<5; d++) del(mp[d], loc[i] + d - 2);

        /// 계산
        if(str[i] == 'L'){
            /// F로 바꿀 경우
            add(mp[3], x);
            ans = max(ans, (int)mp[3].size());
            del(mp[3], x);

            /// R로 바꿀 경우
            ans = max(ans, (int)mp[4].size());

            /// 갱신
            x--;
        }
        else if(str[i] == 'R'){
            /// F로 바꿀 경우
            add(mp[1], x);
            ans = max(ans, (int)mp[1].size());
            del(mp[1], x);

            /// L로 바꿀 경우
            ans = max(ans, (int)mp[0].size());

            /// 갱신
            x++;
        }
        else{ /// F
            /// L로 바꿀 경우
            ans = max(ans, (int)mp[1].size());

            /// R로 바꿀 경우
            ans = max(ans, (int)mp[3].size());
        }

        /// 추가
        if(str[i] == 'F') for(int d=0; d<5; d++) del(mp[d], loc[i]);
    }

    printf("%d", ans);
}