Meta Hacker Cup 2024 - Practice Round

A. Walk the Line

최적의 전략은 다음과 같다.

• $S_i$가 가장 작은 사람 한 명을 고른다.
• 왼쪽 구간에 사람이 두 명 이하가 될 때까지 다음을 반복한다.
  • $S_i$가 가장 작은 사람, 그리고 왼쪽에 남아 있는 사람 중 아무나 함께 오른쪽으로 이동한다. 이때 $S_i$가 더 큰 사람이 wheelbarrow에 탑승한다.
  • $S_i$가 가장 적은 사람이 wheelbarrow를 타고 돌아온다.
• 남은 사람이 오른쪽으로 이동한다.

이때 걸리는 시간은 $\min S_i \times \left( \max(n, 2) - 3 \right)$인데, 이보다 답이 더 작아질 수는 없다. $\times$ 오른쪽의 항은 최소 이동 횟수인데, 한 번의 이동이 $\min S_i$보다 짧을 수 없기 때문이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n; ll k;
ll arr[1002];

int main(){
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d %lld", &n, &k);
        for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
        sort(arr+1, arr+n+1);
        ll val = arr[1] * (max(n, 2) * 2 - 3);
        printf("Case #%d: ", tc);
        if(val <= k) printf("YES\n");
        else printf("NO\n");
    }
}

B. Line by Line

$p = \frac{P}{100}$이라고 하자. $N$개의 줄을 모두 실수없이 칠 확률은 $p^n$이다. 이 문제는 $p^{n-1} \ge p'^{n}$인 최소 $p'$를 찾는 문제이다. 여기서 답은 당연히도 $p' = p^{\frac{n-1}{n}}$일 것이다. 따라서 $p^{\frac{n-1}{n}} - p$를 퍼센트로 출력하면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
double n, p;

int main(){
    freopen("input2.txt", "r", stdin);
    freopen("output2.txt", "w", stdout);
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%lf %lf", &n, &p);
        double pp = p/100;
        double ansp = pow(pp, (n-1)/n);
        double ans = ansp * 100;
        printf("Case #%d: %.12f\n", tc, ans - p);
    }
}

C. Fall in Line

문제가 상당히 특이한데, $N$개의 점이 주어질 때 최대한 많은 점을 포함하는 직선을 찾고, 그 직선 밖의 점이 몇 개인지를 맞춰야 한다. 이때 답이 $M$이라면 $M$ 이상 $2M$ 이하의 수를 출력했을 때 정답으로 인정된다.

 

여기서 중요한 점은, 직선 밖의 점이라는 것이다. 따라서 만약 반 이상의 점을 포함하는 직선이 없다면, 실제 답은 $\frac{N}{2}$ 이상이 될 것이고, 그러면 그냥 $N$을 출력하면 맞는다. 따라서, 반 이상의 점을 포함하는 직선이 있는지만 생각하면 되고, 이것은 랜덤을 이용해 쉽게 해결할 수 있다.

다음의 시행을 $100$회 정도 반복하자:

• 임의의 두 점을 뽑는다. 그리고 그 두 점과 일직선 위에 있는 점의 수를 센다. 만약 이 두 점을 통과하는 직선이 반 이상의 점을 포함한다면 종료한다.

이렇게 하면 각 시행마다 해당 직선을 찾을 확률이 $\frac{1}{4}$이므로, 100회 반복하면 실패 확률은 약 $3 \times 10^{-13}$이 된다. 시간 제한이 굉장히 널널한 문제기 때문에 (사실상 5분 근처) 불안하면 시행 횟수를 더 늘려도 된다.

 

실제로 구현할 때는 이렇게 하지 말고, 각 시행에 대해서 해당 직선 밖에 있는 점을 센다. 이 값의 최솟값을 답으로 출력하면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct vector2{
    ll x, y;
    vector2(){}
    vector2(ll x, ll y): x(x), y(y){}

    vector2 operator-(const vector2 &r)const{
        return vector2(x-r.x, y-r.y);
    }

    ll cross(vector2 r)const{
        return x*r.y-y*r.x;
    }
};

ll ccw(vector2 a, vector2 b){
    return a.cross(b);
}

ll ccw(vector2 a, vector2 b, vector2 c){
    return (b-a).cross(c-a);
}

int t;
int n;
vector2 arr[1000002];

int main(){
    random_device rd;
    mt19937 gen (rd());

    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%lld %lld", &arr[i].x, &arr[i].y);

        uniform_int_distribution<int> dist(1, n);

        int minMove = n;
        for(int turn=1; turn<=200; turn++){
            int a = dist(gen);
            int b = a;
            while(a==b) b = dist(gen);

            int cnt = 0;
            for(int i=1; i<=n; i++){
                if(ccw(arr[a], arr[b], arr[i]) != 0) cnt++;
            }
            minMove = min(minMove, cnt);
        }
        printf("Case #%d: %d\n", tc, minMove);
    }
}

D1. Line of Delivery (Part 1)

뭔가 수직선 위에서 부딪히는 문제는 부딪히는 것의 의미가 있는지를 생각해 보는 게 좋다. 이 문제에서는 부딪힐 때 원판들의 위치 집합에는 차이가 없고, 인덱스가 바뀐다고 생각하는 편이 더 쉽다.

 

따라서, 입력으로 들어온 수열이 끝날 때 모든 돌의 위치이다. 그런데 인덱스는 어떻게 찾을까? 당연히도 가장 멀리 있는 게 1번 돌이고, 가장 가까이 있는 게 $n$번 돌이다. 따라서, 입력으로 들어온 순열을 역순 정렬하고, $G$에서 가장 가까운 것과 그 인덱스를 출력하면 답이 된다.

 

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n; ll L;
ll arr[300002];

int main(){
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d %lld", &n, &L);
        for(int i=1; i<=n; i++){
            scanf("%lld", &arr[i]);
        }
        sort(arr+1, arr+n+1);
        reverse(arr+1, arr+n+1);

        ll minDist = 1e18; int minIdx = 0;
        for(int i=1; i<=n; i++){
            if(minDist > abs(arr[i] - L)){
                minDist = abs(arr[i] - L);
                minIdx = i;
            }
        }
        printf("Case #%d: %d %lld\n", tc, minIdx, minDist);
    }
}

D2. Line of Delivery (Part 2)

상황은 비슷하지만 컬링 공에 크기가 생겨 난이도는 훨씬 더 어려워 보인다. 하지만 사실은 앞 D1 코드에 단 두 줄만 추가하면 정답을 받을 수 있다.

 

핵심 아이디어는 바로 정렬 전에 $a[i]$에 $i$를 더하고, 정렬 후에 $a[i]$에서 $i$를 빼는 것이다.

이게 왜 될까? 컬링 공에 길이 $1$이 생겨 보이지만 사실 전체적인 메커니즘은 직전 문제와 똑같다. 다만 차이가 있다면 이전에는 $0$이었던 최소 간격이 $1$로 늘어난 것 뿐이다. 그렇다면, $a[i]$들을 적절히 조정하여 Part 1로 문제를 환원해보고 싶다는 생각이 든다.

 

어떻게 해야 D1과 equivalent한 상황을 만들 수 있을까? 게임판에 공이 두 개 있다고 생각해 보자. 각 공의 길이가 $1$이므로, 만약 두 공이 닿아 있다면, D1에서는 두 공 사이의 거리가 $0$이겠지만 D2에서는 $1$일 것이다. 그렇다면, 오른쪽에 있는 공의 위치에서 $1$을 뺀다면 D1과 같은 상황이 될 것이다.

 

공의 개수가 더 많아지면 어떻게 될까? 일단, 먼저 던진 공이 항상 더 오른쪽에 있을 것이다. 그 말은, $i$번째로 던진 공은 오른쪽에서 $i$번째에 있을 것이다. 그러나 우리는 먼저 던진 공들의 위치를 그만큼 왼쪽으로 옮기고 싶다. 따라서, $i$번째로 던진 공의 위치에 $i$를 더하자. 이제 공들 사이의 상대적인 간격만 보자면 D1과 동일한 상황이 되었음을 알 수 있다. 이제 D1과 같이 역순 정렬을 하고, 다시 $i$번째 공의 위치에서 $i$를 빼 주면 D2 문제 기준으로 공들이 이동한 실제 위치를 알 수 있다.

 

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n; ll L;
ll arr[300002];

int main(){
    freopen("input2.txt", "r", stdin);
    freopen("output2.txt", "w", stdout);
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d %lld", &n, &L);
        for(int i=1; i<=n; i++){
            scanf("%lld", &arr[i]);
            arr[i] += i;
        }
        sort(arr+1, arr+n+1);
        reverse(arr+1, arr+n+1);
        for(int i=1; i<=n; i++){
            arr[i] -= i;
        }

        ll minDist = 1e18; int minIdx = 0;
        for(int i=1; i<=n; i++){
            if(minDist > abs(arr[i] - L)){
                minDist = abs(arr[i] - L);
                minIdx = i;
            }
        }
        printf("Case #%d: %d %lld\n", tc, minIdx, minDist);
    }
}