USACO 2024-2025 January (Silver)

1. Cow Checkups

$a_i = b_j$인 모든 $(i, j)$ 쌍에 대해, $A$의 구간을 적당히 뒤집었을 때 $a_i$가 $j$번 위치에 오도록 하는 경우의 수를 구해 보자.

 

$i = j$인 경우는 따로 처리해 준다. 뒤집은 구간이 $i$번을 포함하지 않는 경우가 있고, 뒤집은 구간의 가운데에 $i$번 위치가 있는 경우가 있다.

 

$i \neq j$인 경우를 보자. 편의상 $i < j$라고 가정하자. 이때 $A$의 구간을 적당히 뒤집었을 때 $a_i$가 $j$에 오는 구간을 보면,

• 구간 $[i, j]$의 경우 이 조건을 만족하고,
• 여기서 양옆을 같은 길이만큼 늘려도 이 조건을 만족한다.

따라서 이러한 구간이 총 $\min(i, n-j+1)$개 있음을 알 수 있다.

 

이것을 모든 $i$와 $j$에 대해 계산하면 $O(n^2)$ 정도 시간 복잡도에 문제를 해결할 수 있다.

 

시간 복잡도를 줄이기 위해서는 $a_i$나 $b_j$의 값이 같은 것들을 더 빠르게 처리해 줘야 한다. $a_i = b_j = p$인 $i$ 값들과 $j$ 값들을 한 번에 모아 보자. 각각의 $j$ 값에 대해, 다음과 같은 함수를 생각하자.

$$
f_j(i) = \begin{cases}
\min(i, n-j+1) & (i < j) \
\min(j, n-i+1) & (j < i)
\end{cases}
$$

단, $i = j$인 경우는 따로 처리할 것이다.

 

목표는 $\sum_{a_i = p, i \neq j} f_j(i)$를 각 $j$에 대해 구하는 것이다. 그런데 $f_j(i)$는 $i$의 범위에 따라 세 가지 일차함수 중 하나로 나타남을 알 수 있다. 따라서 $j$ 값들을 미리 구해놨을 때, 세 가지 일차함수의 범위 각각에 대해 조건을 만족하는 $j$ 값들의 개수와 합을 알 수 있다면, $\sum f_j(i)$도 쉽게 구할 수 있다. 자세한 구현 방식은 아래 코드를 참고하는 것이 좋다.

 

시간 복잡도는 $O(n \log n)$이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int A[500002];
int B[500002];

vector<ll> loc[500002];
vector<ll> sum[500002];

ll middle(ll x){
    return (x-1)*x/2 + (n-x)*(n-x+1)/2 + min(x, n-x+1);
}

ll ans;

void calc(int v, int L, int R, ll a, ll b){
    if(L>R) return;
    int itL = lower_bound(loc[v].begin(), loc[v].end(), L) - loc[v].begin();
    int itR = upper_bound(loc[v].begin(), loc[v].end(), R) - loc[v].begin() - 1;

    ll c = itR - itL + 1;
    ll s = (itR < 0 ? 0 : sum[v][itR]) - (!itL ? 0 : sum[v][itL-1]);
    ans += s * a + c * b;
}

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

    /// loc, sum
    for(int i=1; i<=n; i++) loc[B[i]].push_back(i);
    for(int i=1; i<=n; i++){
        sum[i].resize(loc[i].size());
        for(int j=0; j<(int)loc[i].size(); j++){
            sum[i][j] = (j ? sum[i][j-1] : 0) + loc[i][j];
        }
    }

    for(int i=1; i<=n; i++){ /// A[i]¿Í °°Àº °Í
        if(A[i] == B[i]) ans += middle(i);
        if(i*2<=n){
            int opp = n+1-i;
            calc(A[i], 1, i-1, 1, 0);
            calc(A[i], i+1, opp, 0, i);
            calc(A[i], opp+1, n, -1, n+1);
        }
        else{
            int opp = n+1-i;
            calc(A[i], 1, opp-1, 1, 0);
            calc(A[i], opp, i-1, 0, opp);
            calc(A[i], i+1, n, -1, n+1);
        }
    }

    printf("%lld", ans);
}

2. Farmer John's Favorite Operation

일단 입력으로 들어오는 모든 값들을 $m$으로 나눈 나머지로 바꿔도 답은 변함이 없다.

 

이제 $a_1, \cdots, a_n$이 모두 $[0, m-1]$ 범위 안에 있을 때, 최종 값 $p$를 적당히 정해야 한다. $p$를 정하고 나면 $a_i$를 $p$로 옮기는 비용은 $\min(|a_i - p|, m - |a_i - p|)$이다.

 

$f(p) = \min(|a_i - p|, m - |a_i - p|)$라고 정의해 보자. $a_i = 0$일 때 $f(p)$는 다음 둘 중 하나의 모습으로 생겼다.

 

 

실제로 의미 있는 점은 정수점밖에 없기 때문에, 실수일 때의 그래프와 모양을 살짝 다르게 그렸다.

 

만약 $a_i \neq 0$이라면, $f$의 그래프는 저 위 그래프를 오른쪽으로 $a_i$만큼 민 그래프처럼 생겼을 것이다. (주기 $m$으로 순환한다고 가정한다.)

 

따라서 $a_i$의 값에 상관없이 그래프를 최대 세 개의 직선의 합집합으로 나타낼 수 있다.

 

이제 저 형태의 그래프 $n$개가 합쳐졌을 때 최솟값을 구하면 된다. 각 $n$개의 그래프에 대해 $x=0$에서의 기울기와 값, 그래프가 꺾이는 점의 $x$좌표와 그때마다 얼마나 꺾이는지를 모두 구해 두자. 꺾이는 점 데이터는 $x$좌표 순으로 정렬해 둔다. 이제 $x$좌표를 앞부터 스위핑하면서, 꺾이는 점마다 $x$의 변화량과 현재 기울기를 적절히 이용해 모든 꺾이는 점들의 좌표를 구해줄 수 있고, 최종적으로 이들 점 중 가장 $y$값이 작은 값을 선택하면 문제를 해결할 수 있다.

 

이런 식으로 기울기 그래프를 이용해 해결하는 유형은 꽤 많이 나오니 잘 익혀두면 좋다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Line{
    ll da, x;
    Line(){}
    Line(ll da, ll x): da(da), x(x){}

    bool operator<(const Line &r)const{
        return x<r.x;
    }
};

int t;
int n; ll m;
ll A[200002];

void push_line(vector<Line> &vec, ll x, ll m){
    ll h = m/2;

    if(m%2 == 0){
        vec.push_back(Line(x<h ? -1 : 1, 0));
        vec.push_back(Line(2, x));
        vec.push_back(Line(-2, (x+h)%m));
    }
    else{
        vec.push_back(Line(x<h ? -1 : x==h ? 0 : 1, 0));
        vec.push_back(Line(2, x));
        vec.push_back(Line(-1, (x+h)%m));
        vec.push_back(Line(-1, (x+h+1)%m));
    }
}

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

        vector<Line> vec;
        for(int i=1; i<=n; i++){
            push_line(vec, A[i], m);
        }
        sort(vec.begin(), vec.end());

        ll a = 0, x = 0, y = 0;
        for(int i=1; i<=n; i++) y += min(A[i], m-A[i]);
        ll ans = y;

        for(Line p: vec){
            y += a * (p.x - x);
            x = p.x;
            a += p.da;
            ans = min(ans, y);
        }
        printf("%lld\n", ans);
    }
}

3. Table Recovery

앞 두 문제는 비슷한 유형의 테크닉을 요구했다면 이 문제는 애드혹의 느낌이 강하다.

 

$1$번, $2$번 유형의 쿼리를 처리해서 기존 격자에서 행과 열이 shuffle된 상태를 생각해 보자. shuffle을 한다고 해도 각 수의 개수가 바뀌진 않는다. 또한 각 수가 한 행/열에 최대 한 번 등장한다는 사실도 변하지 않는다.

 

기존 격자에는 $n+1$이 정확히 $n$번 등장하고, 이러한 수는 $n+1$로 유일하다. 따라서 $n+1$이 무슨 수로 변했는지를 가장 먼저 찾을 수 있다.

 

다음으로 $n$과 $n+2$가 무슨 수로 변했는지를 찾을 수 있다. 격자에서 $n-1$번 등장하는 수를 찾으면 된다. 상황이 대칭적이므로 무엇이 어느 쪽인지는 알 수 없다.

 

그 다음으로 나머지 수들을 모두 찾아보자. $n$이 무슨 수로 변했는지 알 때, $n-1$이 무슨 수로 변했는지를 알아보자. $n-1$은 초기 격자에 총 $n-2$번 등장했을 것이다. 그런데 문제는 $n+3$도 $n-2$번 등장했다는 것이다. 이 둘을 구분하기 위해 한 가지 관찰을 해야 한다. 기존 격자에서 $n-1$이 등장하는 모든 행과 열에는 $n-2$도 등장한다. 그러나 $n+3$이 등장하는 행과 열 중에는 $n-2$가 등장하지 않는 것이 존재한다. 이 점을 이용해 $n-1$이 무슨 수로 변했는지를 알 수 있다.

 

비슷한 방식을 쓰면, $n$과 $n+2$가 무슨 수로 변했는지 고정했을 때, 나머지 모든 수들도 어떻게 변했는지를 알 수 있다.

 

이렇게 하면 가능한 답이 총 두 가지가 나올 텐데, 그 중 사전순으로 빠른 것을 찾아 출력해 주면 문제를 해결할 수 있다.

 

USACO Judge에서는 왜인지 모르겠지만 줄 끝에 공백을 출력하면 틀렸다고 판정한다. 이 점을 주의해야 한다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int A[1005][1005];
int cnt[2005];
bool rowEx[2005][1005];
vector<int> occ[1005];

bool included(int x, int y){
    for(int i=1; i<=n; i++) if(rowEx[x][i] && !rowEx[y][i]) return false;
    return true;
}

vector<int> solve(deque<int> &dq){
    vector<int> idx (n*2+2);
    for(int i=0; i<n*2-1; i++) idx[dq[i]] = i+2;

    vector<int> ret;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) ret.push_back(idx[A[i][j]]);
    return ret;
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        scanf("%d", &A[i][j]);
        cnt[A[i][j]]++;
        rowEx[A[i][j]][i] = 1;
    }
    for(int i=2; i<=n*2; i++) occ[cnt[i]].push_back(i);

    int mid = occ[n][0];

    deque<int> dq (1, mid);
    for(int o=n-1; o>=1; o--){
        int L = dq.front(), R = dq.back();
        int A = occ[o][0], B = occ[o][1];
        if(!included(A, L)) swap(A, B);
        dq.push_front(A);
        dq.push_back(B);
    }

    vector<int> ans1 = solve(dq);
    reverse(dq.begin(), dq.end());
    vector<int> ans2 = solve(dq);

    vector<int> ans = min(ans1, ans2);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) printf("%d%c", ans[i*n+j], j==n-1?'\n':' ');
    }
}