Meta Hacker Cup 2024 - Round 1

그동안 해커컵을 잘 못하다가 미국에 오니 시간대가 맞아서 편하게 할 수 있게 되었다. 앞 4문제를 풀어 69등으로 Round 2에 진출하였다.

A. Subsonic Subway

이 문제는 $N$가지 조건이 있고, 그 중 $i$번째 조건은 $i$번 위치에 도달하는 시간이 $A_i$ 이상 $B_i$ 이하라고 해석할 수 있다. 여기에서 속도에 대한 범위를 얻을 수 있다. 속도는 $\frac{i}{B_i}$ 이상 $\frac{i}{A_i}$ 이하가 된다. 이제 이 $N$개의 구간들의 교집합을 모두 구한 뒤, 해당 교집합이 공집합인지, 공집합이 아니라면 왼쪽 끝점 (가능한 최저 속도)가 얼마인지를 구해 주면 된다. 실수형으로 관리를 해도 통과를 할 수 있을 것 같긴 한데, 나는 안전하게 분수 자료형을 만들어서 해결했다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll a, ll b): a(a), b(b){}

    bool operator<(const Frac &r)const{
        return a*r.b < b*r.a;
    }
};

int t;
int n;
ll L[1000002], R[1000002];

int main(){
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d", &n);
        Frac sl (0, 1), sr (1'000'000, 1);
        for(int i=1; i<=n; i++){
            scanf("%lld %lld", &L[i], &R[i]);
            sl = max(sl, Frac(i, R[i]));
            if(L[i]) sr = min(sr, Frac(i, L[i]));
        }

        printf("Case #%d: ", tc);
        if(sr < sl) puts("-1");
        else printf("%.12f\n", double(sl.a)/sl.b);
    }
}

B. Prime Subfactorization

어떤 세 소수 $a$, $b$, $c$에 대해 $a+b=c$라면 $a$나 $b$ 둘 중 하나는 $2$일 수밖에 없다. 따라서, set에 들어갈 수 있는 소수는 $p$와 $p+2$가 모두 소수인 $p$뿐만이 가능하다. 사전에 에라토스테네스의 체를 돌려 놓고, 이러한 형태의 수들을 모두 구해 놓자. 일단 입력 $n \le 4$라면, 답은 $0$이다. 그렇지 않다면, $n-2$ 이하의 소수들 중 $p$와 $p+2$가 모두 소수인 것의 개수를 구하면 된다. 이때 $2$도 포함해야 하기 때문에 답에 $+1$을 해 주면 된다. 이 부분은 누적합으로 쉽게 계산할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MX = 10'000'000;

int t;
int n;
bool isPrime[MX+2];
int sum[MX+2];

int main(){
    for(int i=2; i<=MX; i++) isPrime[i] = 1;
    for(int i=2; i*i<=MX; i++){
        if(!isPrime[i]) continue;
        for(int j=i*i; j<=MX; j+=i) isPrime[j] = 0;
    }
    sum[5] = 1;
    for(int i=5; i<=MX; i++){
        if(isPrime[i] && isPrime[i-2]) sum[i]++;
    }
    for(int i=5; i<=MX; i++) sum[i] += sum[i-1];

    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d", &n);
        printf("Case #%d: %d\n", tc, sum[n]);
    }
}

C. Substantial Losses

아무리 봐도 이건 수학 문제인 것 같다.

$f(n, L)$을 현재 $n$ kg을 더 감량해야 하고, 문턱이 $L$ kg인 경우 (지금 몸무게보다 최대 $L$ kg까지만 더 찔 수 있는 경우)의 기댓값이라고 하자. 여기서 $f(n, L)$은 $f(n-1, L) + g(L)$이라고 쓸 수 있다. 여기서 $g(L)$은 몸무게가 현재보다 $1$kg 줄어드는 데 필요한 시행 횟수의 기댓값이다. $f(0, L) = 0$이므로, 이것을 반복하면 $f(n, L) = ng(L)$임을 알 수 있다.

$g(L)$은 어떻게 구할 수 있을까? 만약 $L = 0$이면 $g(0) = 1$임이 자명하다. $L>0$이라면, $\frac{1}{2}$ 확률로 첫 턴에 체중이 감소하고 끝날 것이다. 만약 첫 턴에 체중이 증가했다면, 여기서 $g(L-1)$만큼의 턴을 더 기다려야 한다. 이렇게 하면 다시 체중이 기존으로 돌아온다. 여기서 다시 $\frac{1}{2}$ 확률로 체중이 감소할 수 있고, 또는 다시 증가할 수 있다. 이것을 식으로 써 보면, $g(L) = \frac{1}{2} + \frac{1}{2}(1 + g(L-1) + \frac{1}{2} + \frac{1}{2}(1 + g(L-1) + \frac{1}{2} + \frac{1}{2}(\cdots)))$와 같은 형태가 된다. 여기서 식의 순서를 바꾸면 $g(L) = (\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots)(1 + 1 + g(L-1)) = g(L-1) + 2$임을 알 수 있고, $g(L) = 2L+1$임을 알 수 있다. 따라서 $f(n, L) = n(2L+1)$임을 최종적으로 구할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 998244353;

int t;
ll n, u, l;

int main(){
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%lld %lld %lld", &u, &n, &l);
        n = u - n;

        n %= MOD;
        l %= MOD;
        printf("Case #%d: %lld\n", tc, n*(l*2+1)%MOD);
    }
}

D. Substitution Cipher

일단 최대 경우의 수를 구하는 것에서부터 시작해 보자. 조금 생각해 보면, ?에 모두 1을 넣었을 때 가장 많은 경우의 수를 만들 수 있다는 것을 알 수 있다. 왜냐하면 1은 혼자서도 수를 형성하고, 뒤에 어떤 숫자가 붙어 있어도 두 자리 수가 되고, 앞에 1과 2가 붙는 경우에도 두 자리 수를 형성할 수 있기 때문이다. 따라서 먼저 1로 채운 다음 DP를 돌려 전체 경우의 수를 구할 수 있다.

다음으로 최대 경우의 수를 만드는 사전순으로 $K$번째 해를 찾아야 한다. 대략적인 접근은 이렇다. 사전순이므로 첫 번째 자리부터 채우면서 생각하자. 왼쪽에서 첫 번째 ?에 대해, 만약 이 칸에 9를 채웠을 때 $K$개 이상의 해를 만들 수 있다면 여기에 9를 채워야 할 것이다. 그렇지 않다면 $K$에서 아까 구한 9를 넣었을 때 해의 수를 뺀 다음 8을 생각한다. 이 과정을 반복해 답을 구할 수 있다.

여기서 중요한 것은 앞 ? 자리 몇 개에 수를 채웠을 때 뒤에 ?를 적당히 채워 최대 경우의 수를 만드는 방법의 수를 알 수 있어야 한다. 그런데 사실 앞 ?에 뭘 채웠든, 뒤에 영향을 주는 것은 맨 뒷자리 하나밖에 없다. 따라서 $N \times 10$가지 경우의 수에 대한 답을 미리 전처리로 구해 놓으면 편할 것이고, 이 부분은 DP를 통해 미리 구해둘 수 있다. 이제 남은 부분은 DP와 역추적 등을 잘 짜면 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAX = 2'000'000;
const ll MOD = 998244353;

int t, n, k;
char s[100005];
int arr[100005];

ll cases[100005];
bool yes[100005], yes_rev[100005];
bool sing[100005], doub[100005];

int value(int i){
    return (arr[i] == -1 ? 1 : arr[i]) * 10 + (arr[i+1] == -1 ? 1 : arr[i+1]);
}

int DP[100005][10]; /// 0-9: 뒤 자리수

int main(){
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%s %d", s+1, &k);
        n = strlen(s+1);
        for(int i=1; i<=n; i++){
            if(s[i] == '?') arr[i] = -1;
            else arr[i] = s[i] - '0';
        }

        for(int i=0; i<=n+1; i++){
            cases[i] = yes[i] = yes_rev[i] = 0;
            sing[i] = doub[i] = 0;
            for(int j=0; j<10; j++) DP[i][j] = 0;
        }

        /// 항상 1로 채우는 게 최적. cases를 먼저 구하자
        cases[0] = 1;
        for(int i=1; i<=n; i++){
            if(arr[i]) cases[i] = (cases[i] + cases[i-1]) % MOD;
            if(i>1){
                int v = value(i-1);
                if(10 <= v && v <= 26) cases[i] = (cases[i] + cases[i-2]) % MOD;
            }
        }

        yes[0] = 1;
        for(int i=1; i<=n; i++){
            if(arr[i]) yes[i] |= yes[i-1];
            if(i>1){
                int v = value(i-1);
                if(10 <= v && v <= 26) yes[i] |= yes[i-2];
            }
        }

        /// 역방향으로도 시도
        yes_rev[n+1] = 1;
        for(int i=n; i>=1; i--){
            if(arr[i]) yes_rev[i] |= yes_rev[i+1];
            if(i<n){
                int v = value(i);
                if(10 <= v && v <= 26) yes_rev[i] |= yes_rev[i+2];
            }
        }

        for(int i=1; i<=n; i++){
            if(yes[i-1] && yes_rev[i+1] && arr[i]) sing[i] = 1;
        }
        for(int i=1; i<n; i++){
            int v = value(i);
            if(yes[i-1] && yes_rev[i+2] && 10 <= v && v <= 26) doub[i] = 1;
        }

        /// DP 시작
        if(arr[n] == -1){
            for(int i=0; i<10; i++) DP[n][i] = (sing[n] && i==0) ? 0 : 1;
        }
        else DP[n][arr[n]] = 1;

        for(int i=n-1; i>=1; i--){
            for(int j=0; j<10; j++){ /// DP[i+1][j]
                if(!DP[i+1][j]) continue;
                for(int v=0; v<10; v++){
                    if(arr[i] != -1 && arr[i] != v) continue;
                    if(sing[i] && !v) continue;
                    if(doub[i] && (v*10+j < 10 || v*10+j > 26)) continue;
                    DP[i][v] += DP[i+1][j];
                    DP[i][v] = min(DP[i][v], MAX);
                }
            }
        }

        string ans;
        int i = 1, v = 9;
        while(k > DP[i][v]) k -= DP[i][v--];

        while(i < n){
            ans.push_back('0' + v);
            for(int j=9; j>=0; j--){
                if(arr[i+1] != -1 && arr[i+1] != j) continue;
                if(sing[i+1] && !j) continue;
                if(doub[i] && (v*10+j < 10 || v*10+j > 26)) continue;
                if(k > DP[i+1][j]) {k -= DP[i+1][j]; continue;}
                i++, v = j;
                break;
            }
        }
        ans.push_back('0' + v);

        printf("Case #%d: %s %lld\n", tc, ans.c_str(), cases[n]);
    }
}

E. Wildcard Submissions

백트래킹을 메모이제이션으로 약간 최적화한 코드를 짰고, 빠르게 돌아가는 것 같아서 제출을 시도했지만 6분 이내에 정답이 나오지 않아 푸는 데에 실패했다. 의도된 정해는 저기서 $\frac{1}{16}$만큼의 상수를 잘 깎는 것 같고, 나와 같은 상황을 겪은 사람들이 많은 것 같다. 제출이 여러 번 가능했다면 상수 최적화를 처음에 실패해도 다음에 어느 정도 깎고 시도할 수가 있을 텐데, Facebook 특유의 제출 시스템에 전혀 맞지 않는 문제인 것 같아서 아쉽다.