USACO 2024-2025 February (Silver)

1. The Best Lineup

사전순으로 최대인 것을 찾는 문제는 보통 그리디한 접근 방식을 가지는 경우가 많다. 사전순으로 최대라는 개념은 정의 자체가 그리디하기 때문이다.

 

그래서 이 문제의 경우도 앞부터 채워나가면서 가장 큰 수를 그리디하게 넣으려는 접근이 성립한다. 문제에 주어진 연산을 최대 한 번 해서 만들 수 있는 결과 수열을 유효한 수열이라고 하자. 맨 앞 자리에서부터 최대한 큰 수 넣기를 시도해 보면서, 해당 수열이 유효한지를 계속 확인하면 된다. (어떤 수열이 유효하면 그 접두사들도 모두 유효해야 하므로...)

 

최종 답의 형태를 보면, 큰 수 여러 개가 같은 것이 여러 개끼리 나오면서, 점점 줄어드는 형태를 상상할 수 있다. 따라서 $v$를 $N$부터 $1$까지 내리면서, $v$를 최대 몇 개까지 넣을 수 있는지 생각해 보자. 이렇게 하면서 답을 앞부터 점점 채워나갈 것이다.

 

연산을 한 번도 쓰지 못한다고 가정해 보자. 이 경우 $v$들 중에서 현재 답의 마지막 원소보다 오른쪽에 있는 것들을 사용할 수 있다. 그러나, 만약 연산을 한 번 사용할 수 있다면, $v$들 중에서 현재 답의 두 번째로 마지막 원소보다 오른쪽에 있는 것들을 사용할 수 있을 것이다. 만약 지금 연산을 사용해서 넣을 수 있는 수의 개수가 더 많다면, 우리는 사전순 최대인 답을 찾고 있으므로 무조건 연산을 사용해야 한다. 그러나 만약 연산을 사용해도 지금 넣을 수 있는 $v$의 개수가 변하지 않으면, 연산은 아껴두는 게 좋을 것이다.

 

이것은 사전에 각 수의 위치를 모두 저장해 놓고 이분 탐색 등을 잘 활용하여 $O(N \log N)$에 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n;
int A[200002];
vector<int> occ[200002];

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

        vector<int> ans; /// 위치로 저장
        int used = 0; /// 마지막 위치, 스킬 사용 여부
        for(int v=n; v>=1; v--){
            if(occ[v].empty()) continue;
            if(ans.empty()){
                ans = occ[v];
                continue;
            }
            int cnt = occ[v].end() - lower_bound(occ[v].begin(), occ[v].end(), ans.back());
            int new_cnt = used ? 0 : (occ[v].end() - lower_bound(occ[v].begin(), occ[v].end(),
                                                                 ans.size()==1 ? 0 : ans[ans.size()-2]));

            if(cnt < new_cnt){
                used = 1;
                int p = (ans.size()==1 ? 0 : ans[ans.size()-2]);
                for(int x: occ[v]) if(x > p) ans.push_back(x);
            }
            else for(int x: occ[v]){
                int p = ans.back();
                if(x > p) ans.push_back(x);
            }
        }

        for(int i=0; i<(int)ans.size(); i++){
            printf("%d%c", A[ans[i]], i+1==(int)ans.size() ? '\n' : ' ');
        }
    }
}

2. Vocabulary Quiz

문제의 상황을 트리로 생각할 수 있다. (엄밀히 말하자면 문제의 상황은 Trie(트라이)와 일치하지만, 해당 자료구조를 전혀 몰라도 푸는 데 지장이 없다.)

 

어떤 단어 (정점) $x$를 말할 때, $x$를 확정할 수 있을 때까지 말한다고 한다. 이때 어디까지 말해야 할까? 어떤 단어 $x$를 말하는 과정은 트리의 루트($0$번 정점)에서 $x$번 정점을 향해 내려가는 과정으로 생각할 수 있다. 그러다가 밑으로 내려가는 길에 리프 노드가 $x$번 하나밖에 안 남으면 멈춘다.

 

이 위치를 어떻게 찾을 수 있을까? 반대로 $x$번 정점에서 올라간다고 생각해 보자. 언제까지 올라가면 될까? $par[x]$의 자손이 $1$개인 경우 계속 올라가다가, 자식이 여러 개인 정점을 만난 경우 그 직전에 멈추면 된다.

예시를 보자.

 

 

이것은 두 번째 예제를 그린 것이다. 처음에 $4$번 단어를 읽을 때는 $4$번 정점의 부모인 $1$번 정점이 자식이 두 개이므로 거기까지 올라가면 안 된다. 즉, $4$번 단어를 확정지으려면 $4$번 단어에 해당하는 노드까지 모두 읽어야 한다. 이때 $4$번 단어의 깊이인 $2$를 출력하면 된다. 이후 $4 \rightarrow 1$로 가는 edge를 제거해 준다.

 

두 번째 케이스에서는 $3$번 정점에서 $1$번 정점으로 올라가도 된다. $1$번 정점의 자식이 하나밖에 안 남았기 때문이다. 그러나 $0$번 정점은 자식이 두 개 남아 있기 때문에, 더 이상 올라갈 수 없다. 즉, 이번 단어를 확정하려면 $1$번 단어까지는 불러야 한다. $1$번 정점의 깊이인 $1$을 출력한다. 이후 $1 \rightarrow 0$으로 가는 간선을 제거한다.

 

세 번째 케이스에서는 $0$번 정점의 자식이 하나밖에 안 남았으므로 $0$번 정점까지 올라갈 수 있다. 따라서 $0$번 정점의 깊이인 $0$이 답이 된다.

 

이제 이 알고리즘의 시간 복잡도를 분석해 보자. 처음에는 이 알고리즘의 시간 복잡도가 $O(N^2)$이라고 생각할 수도 있다. 그러나, 각 간선을 정확히 한 번씩 확인하므로, 실제 시간 복잡도는 $O(N)$이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int par[1'000'005];
int deg[1'000'005], depth[1'000'005];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &par[i]);
        deg[par[i]]++;
        depth[i] = depth[par[i]] + 1;
    }

    int m = 0;
    for(int i=1; i<=n; i++) if(!deg[i]) m++;

    vector<int> vec (m);
    for(int i=0; i<m; i++) scanf("%d", &vec[i]);

    for(int x: vec){
        int y = x;
        while(y && deg[par[y]] == 1){
            y = par[y];
        }
        if(y) deg[par[y]]--;
        printf("%d\n", depth[y]);
    }
}

3. Transforming Pairs

거꾸로 생각하자. 할 수 있는 것은 큰 쪽에서 작은 쪽을 빼는 것밖에 없다. ($a$와 $b$가 모두 $1$ 이하이므로, 두 수가 같은 경우는 더 이상 아무 action도 할 수 없다고 생각해도 된다.)

 

따라서 역으로 문제를 풀어주면 유클리드 호제법과 비슷한 방식으로 쉽게 해결할 수 있다. 구현 시 주의사항으로, $(c, d)$에서 $(c \bmod d, d)$로 가는 중간 과정에서 $(a, b)$가 나올 수도 있다는 사실을 유의해야 한다. 예를 들어 $(c, d) = (19, 8)$인데 $(a, b) = (11, 8)$인 상황을 놓치지 않도록 주의해야 한다. (이러한 상황은 예제 2에서도 등장한다.)

 

유클리드 호제법의 시간 복잡도와 같이, 각 테스트 케이스를 해결하는 복잡도는 $\log \left( \min(c, d) \right)$ 정도 수준이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
ll a, b, c, d;

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        ll cnt = 0; int done = 0;
        while(c && d){
            if(a==c&&b==d){
                printf("%lld\n", cnt);
                done = 1;
                break;
            }
            if(c<d) swap(a,b), swap(c,d);

            if(d == b && c >= a){
                if((c-a)%d == 0){
                    printf("%lld\n", cnt + (c-a)/d);
                    done = 1;
                    break;
                }
            }

            cnt += c/d, c%=d;
        }
        if(!done) puts("-1");
    }
}