USACO 2023-2024 February (Silver)

1. Target Practice II

먼저 선분들은 기울기가 양수인 것과 음수인 것으로 나눌 수 있다. 이제 사각형의 네 점이 주어졌을 때, 각 점들에 양수 또는 음수 기울기의 선분을 배정해야 한다.

위 그림에서 보다시피 오른쪽에 있는 두 꼭짓점 중 위의 것은 음수 기울기, 아래의 것은 양수 기울기를 배정해야 한다. 그러나 왼쪽에 있는 두 꼭짓점은 어떤 기울기로 배정해도 상관없다.

 

왼쪽에 있는 꼭짓점들에는 어떤 기울기를 배정해야 할까? 생각해 보면, 위/아래 반경을 줄이기 위해서는, 위쪽에 있는 꼭짓점에는 양수 기울기를, 아래쪽에 있는 꼭짓점에는 음수 기울기를 배정하는 것이 좋다. 따라서, 전체 선분 기울기 목록 중 양수 기울기인 것이 $a$개, 음수 기울기인 것이 $4N-a$개라면, 왼쪽에 있는 꼭짓점 중 가장 위의 $3N-a$개는 양수 기울기를, 가장 아래의 $a-N$개는 음수 기울기를 배정받을 것이다.

 

이제 양수 기울기를 배정받은 점과 음수 기울기를 배정받은 점을 따로 살펴보며, 위쪽 한계의 최솟값과 아래쪽 한걔의 최댓값을 구하면 된다. parametric search를 이용해 가능성 판별을 하는 식으로 답을 구하면 되고, 가능성을 판별하는 부분은 주어진 기울기들 중에서 가장 아슬아슬하게 한계에 닿지 않는 것을 반복해서 선택하는 식으로 그리디하게 판별할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll J = 2e10;

int t;
int n; ll X1;
ll y_1[40002], y_2[40002], x_2[40002];
ll slope[160002];

bool able(vector<pair<ll, ll> > &points, vector<ll> &slopes, ll lim){
    vector<ll> need_slopes;
    for(auto [x, y]: points) need_slopes.push_back((lim - y) / x);
    sort(need_slopes.begin(), need_slopes.end());

    for(int i=0; i<(int)slopes.size(); i++){
        if(need_slopes[i] < slopes[i]) return false;
    }
    return true;
}

ll solve(vector<pair<ll, ll> > points, vector<ll> slopes){
    ll L = -2e18, R = 2e18, ANS = 2e18;
    for(auto [x, y]: points) L = max(L, y);

    sort(slopes.begin(), slopes.end());

    while(L <= R){
        ll M = (L+R+J*2)/2-J;
        if(able(points, slopes, M)) ANS = M, R = M-1;
        else L = M+1;
    }

    return ANS;
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %lld", &n, &X1);
        for(int i=1; i<=n; i++) scanf("%lld %lld %lld", &y_1[i], &y_2[i], &x_2[i]);
        for(int i=1; i<=n*4; i++) scanf("%lld", &slope[i]);

        int slopePositive = 0, slopeNegative = 0;
        for(int i=1; i<=n*4; i++){
            if(slope[i] > 0) slopePositive++;
            else slopeNegative++;
        }
        if(min(slopePositive, slopeNegative) < n){
            puts("-1");
            continue;
        }

        vector<pair<ll, ll> > leftP, rightUpP, rightDownP;
        for(int i=1; i<=n; i++){
            leftP.push_back({X1, y_1[i]});
            leftP.push_back({X1, y_2[i]});
            rightUpP.push_back({x_2[i], y_2[i]});
            rightDownP.push_back({x_2[i], y_1[i]});
        }

        sort(leftP.begin(), leftP.end());

        vector<pair<ll, ll> > pointPos = rightDownP, pointNeg = rightUpP;
        for(int i=0; i<n*2; i++){
            if(i < slopeNegative - n) pointNeg.push_back(leftP[i]);
            else pointPos.push_back(leftP[i]);
        }

        sort(slope+1, slope+n*4+1);
        for(int i=1; i<=slopeNegative; i++) slope[i] *= -1;
        ll up = solve(pointNeg, vector<ll> (slope+1, slope+slopeNegative+1));

        for(auto &[x, y]: pointPos) y*=-1;
        ll down = solve(pointPos, vector<ll> (slope+slopeNegative+1, slope+n*4+1));

        printf("%lld\n", up + down);
    }
}

 

2. Test Tubes

일단 입력에서 $1$이나 $2$가 연속해 있는 경우 하나로 취급해도 된다. 따라서 입력의 두 튜브는 다음 상태 중 하나로 가정해도 좋다.

• $1212\cdots121$: Case $11$
• $1212\cdots1212$: Case $12$
• $2121\cdots212$: Case $22$
• $2121\cdots2121$: Case $21$

첫 튜브의 맨 아래를 $1$로 고정하자. ($2$면 모든 $1$을 $2$로, $2$를 $1$로 바꿔도 답이 같다.) 이러면 고려할 케이스가 많이 줄어든다.

 

첫 튜브는 Case $11$ 또는 $12$이고, 두 번째 튜브는 Case $11$, $12$, $21$, $22$ 중 하나이다.

먼저 튜브 $3$이 필요 없는 경우를 생각해 보자.

• 처음부터 이미 분리가 되어 있다면 답은 $0$이다.
• 처음에 분리가 되어 있지 않지만, 전체 구성이 $(12, 2)$나 $(1, 21)$ 꼴이면 튜브 $3$이 필요없이 한 번만 부어도 된다.

저 형태가 아닌 경우 튜브 $3$이 항상 필요하다. 또한, 만약 처음에 양쪽 튜브의 맨 위 색이 같다면 한쪽을 다른 쪽으로 부었을 때 무조건 이득이다. 따라서, 다음 세 가지 케이스만 고려해도 된다. 양쪽 케이스 번호가 $(11, 12)$, $(11, 22)$, $(12, 21)$인 경우만 보면 된다.

 

이제 각각의 케이스를 분석해 보자. 각 튜브의 길이를 $a, b$라고 하자. (여전히, 연속한 같은 약은 하나의 층으로 센다. 예를 들어 상태가 $111222211$인 경우 길이를 $3$으로 생각한다.)

• $(11, 12)$ 케이스인 경우, $a+b$번이 필요하다. 처음에 $2$를 $3$번 튜브에 넣고, 같은 것끼리 계속 합치면 된다.
• $(11, 22)$ 케이스인 경우, $a+b-1$번이 필요하다. 마찬가지로 처음에 $2$를 $3$번 튜브에 넣고 같은 것끼리 계속 합친다.
• $(12, 21)$ 케이스인 경우, $a+b-1$번이 필요하다.

정리하면 최소 횟수 $M$은 다음과 같이 구할 수 있다.

• 먼저 양쪽 튜브의 가장 위 색이 같다면 한쪽을 다른 쪽으로 옮긴다.
• 만약 양쪽 길이가 모두 $1$이 되었다면 남은 횟수는 $0$이다.
• 그렇지 않다면, 양쪽의 가장 아래 색이 같다면 남은 횟수는 $a+b$ (길이 합)이고, 다르다면 $a+b-1$ (길이 합 - 1)이다.

실제 해를 구하는 것은 많이 까다롭다. 정리해서 적기도 힘들다. 이런 유형을 보통 풀 때는 일단 되도록 대칭성 등을 이용해 케이스를 줄이고, 케이스별로 최대한 간단하게 짜는 것이 좋다. 만약 틀리면 여러 가지 데이터를 손으로 넣어 보면서 틀린 케이스를 찾고, AC가 나올 때까지 계속 메워 주는 것이 최적인 것 같다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n, m, p;
int a, b;

void input(int &st, int &len){
    string s;
    cin >> s;

    char prv = 0;
    st = s[0] - '0';
    len = 0;
    for(char c: s){
        if(prv != c) len++;
        prv = c;
    }
}

int main(){
    cin >> t;
    while(t--){
        cin >> n >> p;
        input(a, n);
        input(b, m);

        int start = 0, where = 0; /// where -> 3-where
        /// 끝이 같은 경우, 한쪽을 합쳐 준다
        if((a+n)%2 == (b+m)%2){
            if(n>1) n--, start++, where = 1;
            else m--, start++, where = 2;
        }

        /// 간단한 케이스 처리 - n=m=1
        if(n==1 && m==1){
            /// M
            printf("%d\n", start);
            if(p>1 && start) printf("%d %d\n", where, 3-where);
            continue;
        }

        /// 나머지 경우
        printf("%d\n", n+m - int(a!=b) + start);
        if(p>1){
            if(start) printf("%d %d\n", where, 3-where);
            /// 해 구성하기
            vector<int> A, B, C;
            for(int i=0; i<n; i++) A.push_back(i%2 ? 3-a : a);
            for(int i=0; i<m; i++) B.push_back(i%2 ? 3-b : b);

            bool swt = 0;
            function<int(int)> get_swt = [&](int x){
                if(swt && x<=2) return 3-x;
                else return x;
            };

            function<void(int, int)> pour = [&](int x, int y){
                printf("%d %d\n", get_swt(x), get_swt(y));
                vector<int> &from = (x==1 ? A : x==2 ? B : C);
                vector<int> &to = (y==1 ? A : y==2 ? B : C);
                if(to.empty() || to.back() != from.back()) to.push_back(from.back());
                from.pop_back();
            };

            if(a==b){ /// 맨 아래가 같음
                if(B.size() == 1) swap(A, B), swt = 1; /// B가 길이 1인 경우는 없음

                /// 3은 1 첫칸과 다르게
                if(A.back() == A[0]) pour(2, 3);
                else pour(1, 3);

                while(A.size() > 1){
                    if(A.back() == C.back()) pour(1, 3);
                    else if(A.back() == B.back()) pour(1, 2);
                    else pour(2, 3);
                }

                while(B.size() > 1){
                    if(B.back() == A.back()) pour(2, 1);
                    else pour(2, 3);
                }

                pour(2, 1);
                pour(3, 2);
            }
            else{ /// 맨 아래가 다름
                if(B.size() == 1) swap(A, B), swt = 1; /// B가 길이 1인 경우는 없음

                /// 3은 1 첫칸과 다르게
                if(A.back() == A[0]) pour(2, 3);
                else pour(1, 3);

                while(A.size() > 1){
                    if(A.back() == C.back()) pour(1, 3);
                    else if(A.back() == B.back()) pour(1, 2);
                    else pour(2, 3);
                }

                while(B.size() > 1){
                    if(B.back() == A.back()) pour(2, 1);
                    else pour(2, 3);
                }
                pour(3, 2);
            }
        }
    }
}

 

3. Moorbles

USACO에 전형적으로 등장하는 사전순 최소 구하기 유형이다.

 

사전순 최소를 구하려면 맨 앞에서부터 보면서, 여기서 Even을 골랐을 때 앞으로 살아남을 수 있는지를 판별해야 한다. 여기서 살아남을 수 있다는 말이 무슨 뜻인지를 생각해 보자. 앞으로 최선의 선택을 했을 때 돌 개수가 $1$개 이상으로 유지된다는 뜻이다.

따라서, 각 턴 $i$에 대해, $i$번 턴부터 진행될 때 앞으로 최선의 선택을 할 경우 지금에 비해 잃을 수 있는 최대 돌의 개수를 구해 놓아야 한다.

 

min_loss[i]를 $i$번 턴부터 진행하며, 돌 $p$개를 가진 상태에서 시작할 때 ($p$는 충분히 크다고 가정한다), 최선의 선택만을 반복할 경우 전체 시점에서 돌의 최소 개수를 $p - x$라고 할 때, 그 $x$값이라고 하자. 다른 말로 하면, $i$번 턴부터 시작했을 때 살아남기 위해 필요한 최소 돌의 개수에서 $1$을 뺀 것과도 같다.

 

짝수를 선택할 때, 홀수를 선택할 때, 최악의 상황만 고려한다면, 이것은 간단한 선형 DP로 구할 수 있다. 이때 뒤에서부터 채워야 한다.

 

min_loss 배열을 모두 채우고 나면 게임에서 살아남는 게 가능한지 먼저 판별해 주고, 가능하다면 각 턴별로 무엇을 골라야 하는지 판별하면 된다.

 

테스트 케이스당 $O(m)$에 해결할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
ll n; int m, k;
ll arr[300005][5];

ll loss[300005][2]; /// loss[i][d]: i번 턴에서 d 선언 시 최소 이익
ll min_loss[300005];

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

        /// 뒤에서부터 보면서 최소 손실 계산
        min_loss[m+1] = 0;
        for(int i=m; i>=1; i--){
            loss[i][0] = loss[i][1] = 1e18;
            for(int j=1; j<=k; j++){
                for(int d=0; d<2; d++){
                    loss[i][d] = min(loss[i][d], arr[i][j]%2 == d ? arr[i][j] : -arr[i][j]);
                }
            }
            min_loss[i] = min_loss[i+1] + max(loss[i][0], loss[i][1]);
            min_loss[i] = min(min_loss[i], 0LL);
        }

        if(n + min_loss[1] <= 0){
            puts("-1");
            continue;
        }

        vector<bool> ans;
        for(int i=1; i<=m; i++){
            if(n + loss[i][0] + min_loss[i+1] > 0){
                ans.push_back(0);
                n += loss[i][0];
            }
            else{
                ans.push_back(1);
                n += loss[i][1];
            }
        }

        for(int i=0; i<m; i++){
            printf("%s%c", ans[i] ? "Odd" : "Even", i==m-1 ? '\n' : ' ');
        }
    }
}