Meta Hacker Cup 2024 - Round 2

이번 문제들은 Round 1보다 까다로웠던 것 같다. A1, A2, C를 풀어 85등으로 Round 3에 진출하였다. B는 답안을 제출했으나 끝나고 틀린 것으로 밝혀졌다.

 

A1. Cottontail Climb (Part 1)

문제의 조건을 만족하는 수의 개수가 매우 적으므로 (45개로 기억하지만 정확하지 않다), 모두 만들어둔 뒤 나이브하게 계산하면 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
ll a, b;
ll m;
vector<ll> vec;

void init();

int main(){
    init();
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%lld %lld %lld", &a, &b, &m);
        ll ans = 0;
        for(ll v: vec) if(a<=v && v<=b && v%m == 0) ans++;
        printf("Case #%d: %lld\n", tc, ans);
    }
}

void init(){
    for(int mid = 1; mid <= 9; mid++){
        for(int len = 1; len <= mid; len++){
            ll v = 0;
            int s=mid-len+1;
            for(int i=s; i<=mid; i++) v = v * 10 + i;
            for(int i=mid-1; i>=s; i--) v = v * 10 + i;
            vec.push_back(v);
        }
    }
}

A2. Cottontail Climb (Part 2)

앞 문제인 A1의 경우 조건을 만족하는 수는 정말 적었지만 A2에서는 이 경우의 수가 훨씬 많다. 이 개수가 약 7천만 개 정도 되는데, 나는 이걸 모두 구해 놓고 시간 안에 동작한다고 확신하지 못해서 조금 더 어려운 풀이를 짰다. 그냥 미리 모두 구해놓고 나이브하게 개수를 세어도 시간 내에 돈다고 한다.

내가 쓴 방법은 중간 수 $mid$를 고정하고 왼쪽에 올 수 있는 부분과 오른쪽에 올 수 있는 부분의 쌍을 모두 구해 놓은 뒤, meet in the middle과 비슷한 느낌으로 왼쪽 수를 고정한 다음 오른쪽에 올 수 있는 수의 개수를 빠른 시간 내에 구하는 방법이다. 이것을 해 놓으려면 $m$으로 나눈 나머지를 고려해 그룹으로 묶어 놓은 뒤, $a$와 $b$ 범위를 판단하며 이분 탐색으로 개수를 찾아 주어야 한다. 여러모로 하기 싫은 구현이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
ll L, R;
ll m;

ll p10[19];
vector<ll> lvec[10][9], rvec[10][9]; /// [가운데 수][양옆 길이]

void init();
inline ll rmod(ll v){
    ll a = v%m;
    if(!a) return 0;
    return m-a;
}

int main(){
    freopen("input2.txt", "r", stdin);
    freopen("output2.txt", "w", stdout);
    init();
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%lld %lld %lld", &L, &R, &m);

        ll ans = 0;
        for(int mid = 1; mid <= 9; mid++){
            for(int len = 0; len <= 8; len++){
                ll rMin = 0, rMax = p10[len] - 1;

                vector<ll> lChoice, rChoice;
                for(ll v: lvec[mid][len]) lChoice.push_back((v*10+mid)*p10[len]);
                for(ll v: rvec[mid][len]) rChoice.push_back(v);

                sort(lChoice.begin(), lChoice.end(), [&](ll a, ll b){
                    ll am = a%m, bm = b%m;
                    if(am != bm) return am < bm;
                    return a < b;
                });
                sort(rChoice.begin(), rChoice.end(), [&](ll a, ll b){
                    ll am = rmod(a), bm = rmod(b);
                    if(am != bm) return am < bm;
                    return a < b;
                });

                int pnt = 0, ls = (int)lChoice.size(), rs = (int)rChoice.size();
                for(int a=0; a<ls; a++){
                    int b = a;
                    while(b+1 < ls && lChoice[a]%m == lChoice[b+1]%m) b++;

                    ll rm = lChoice[a] % m; /// rs에서 찾아야 하는 나머지
                    while(pnt < rs && rmod(rChoice[pnt]) < rm) pnt++;
                    if(pnt == rs) break;
                    if(rmod(rChoice[pnt]) > rm) {a = b; continue;}

                    int c = pnt;
                    while(pnt+1 < rs && rmod(rChoice[pnt+1]) == rm) pnt++;
                    int d = pnt;

                    /// lc [a-b] 와 rc [c-d] 사이 연결
                    for(int x=a; x<=b; x++){
                        ll v = lChoice[x];
                        if(v + rMin > R || v + rMax < L) continue; /// 가망이 없음
                        if(L <= v + rMin && v + rMax <= R){ /// 뭘 해도 들어감
                            ans += d - c + 1;
                            continue;
                        }
                        /// 여기서는 부분만 들어감
                        ll ql = max(rMin, L - v), qr = min(rMax, R - v);
                        ans += upper_bound(rChoice.begin()+c, rChoice.begin()+d+1, qr)
                             - lower_bound(rChoice.begin()+c, rChoice.begin()+d+1, ql);
                    }
                    a = b;
                }
            }
        }

        printf("Case #%d: %lld\n", tc, ans);
    }
}

void init(){
    p10[0] = 1;
    for(int i=1; i<=18; i++) p10[i] = p10[i-1] * 10;

    lvec[1][0].push_back(0);
    rvec[1][0].push_back(0);
    for(int mid=2; mid<=9; mid++){
        for(int len=0; len<=8; len++){
            string s (len, '1');
            while(true){
                ll v = 0;
                for(char c: s) v = v * 10 + (c - '0');
                lvec[mid][len].push_back(v);

                v = 0;
                for(int i=len-1; i>=0; i--) v = v * 10 + (s[i] - '0');
                rvec[mid][len].push_back(v);

//                printf("%d %d: %lld %lld\n", mid, len, lvec[mid][len].back(), rvec[mid][len].back());

                if(len == 0 || s[0] == '0' + mid - 1) break;
                int pnt = len-1;
                while(s[pnt] == '0' + mid - 1) pnt--;
                s[pnt]++;
                for(int i=pnt+1; i<len; i++) s[i] = s[pnt];
            }
        }
    }

    int lensum = 0;
    for(int i=1; i<=9; i++) for(int j=0; j<=8; j++){
        lensum += lvec[i][j].size();
    }
//    printf("Total size: %d\n", lensum);
}

B. Four in a Burrow

여러모로 왜 냈는지 잘 모르겠는 문제이다.

문제는 놀랍게도 $7^7$가지의 모든 경우를 탐색해 보는 방식으로 풀 수 있다. 이보다 더 빠른 풀이는 듣지 못했다. 대략적인 흐름은, 승부가 난 시점 $t$를 고정한 뒤, 해당 시점에서 보드판이 될 수 있는 경우의 수인 $7^7$가지를 모두 둘러보고, 해당 시점에 C 혹은 F 둘 중 하나만 빙고가 생겼다면, C 또는 F가 이길 수 있는 가능성이 있다고 판별하는 것이다.

다만 여기서 바로 끝은 아니고, 해당 시점 $t$에서 게임이 끝나는 게 가능한지를 또 판별해야 한다. 여기서 중요한 두 가지 조건은,

• 게임 시작 뒤 돌을 놓는 것을 반복해 게임판 $t$를 만들 수 있다. 이때 시점 $t$ 전에 이미 승부가 결정이 나면 안 된다.
• $t$의 상태에서 돌을 더 놓아서 최종 게임 상태를 만들 수 있다.

이 두 조건은 $7^7$개의 상태를 정점으로 생각한 뒤 그래프 위에서 탐색을 한다는 느낌으로 해결할 수 있다.

나는 저 두 번째 조건을 생각하지 못하고 첫 번째 조건만 짜서 문제를 틀렸다. B에서 틀린 사람들이 굉장히 많은데 비슷한 이슈가 아니었을까 생각한다. 여러모로 예제가 더 강했으면 좋았겠다는 생각이 든다.

C. Bunny Hopscotch

답에 대한 이분 탐색을 해 보자. 그렇다면 문제는 "거리가 $k$ 이하인 서로 다른 색의 칸 쌍이 몇 개인가?"로 환원할 수 있다.

여기서 거리는 체비셰프 거리로 정의되므로, 어떤 점에서 거리가 $k$ 이하인 점의 범위가 정사각형 꼴로 나타남을 알 수 있다. 서로 다른 색의 칸 쌍을 구하는 건 좀 어려우니, 거리가 $k$ 이하인 모든 쌍 개수를 먼저 세 주고, 여기서 색이 같은 쌍을 빼 주기로 하자. 이걸 계산하는 것은 점들을 색에 따라 모아둔 뒤, 각각의 집합에서 segtree + sweeping을 통해 해결할 수 있다. 이렇게 하면 시간 복잡도 $O(RC \log C \log X)$ 정도의 풀이를 얻을 수 있다. ($X$는 답의 범위인데, $X = \max(R, C)$로 생각해도 좋다.)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick{
    int n;
    int tree[802];

    void init(int _n){
        n = _n;
        for(int i=0; i<=n; i++) tree[i] = 0;
    }

    void add(int x, int v){
        while(x<=n){
            tree[x] += v;
            x += x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    int sum(int l, int r){
        l = max(l, 1), r = min(r, n);
        if(l>r) return 0;
        return sum(r) - sum(l-1);
    }
} tree;

int t;
int n, m; ll k;
int arr[802][802];
vector<pair<int, int> > ord[640002];

struct Event{
    int type, t, l, r; /// 0: add, 1: query, 2: del
    Event(){}
    Event(int type, int t, int l): type(type), t(t), l(l){}
    Event(int type, int t, int l, int r): type(type), t(t), l(l), r(r){}

    bool operator<(const Event &nxt)const{
        if(t != nxt.t) return t<nxt.t;
        return type < nxt.type;
    }
};

ll calc(int L){
    ll total = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int xl = max(i-L, 1), xr = min(i+L, n), yl = max(j-L, 1), yr = min(j+L, m);
            total += (xr-xl+1) * (yr-yl+1);
        }
    }

    for(int d=1; d<=n*m; d++){
        if(ord[d].empty()) continue;
        vector<Event> vec;
        for(auto [x, y]: ord[d]){
            vec.push_back(Event(0, x-L, y));
            vec.push_back(Event(1, x, y-L, y+L));
            vec.push_back(Event(2, x+L, y));
        }
        sort(vec.begin(), vec.end());

        tree.init(m);
        for(Event &p: vec){
            if(p.type == 0) tree.add(p.l, 1);
            else if(p.type == 2) tree.add(p.l, -1);
            else total -= tree.sum(p.l, p.r);
        }
    }
    return total;
}

int main(){
    freopen("input2.txt", "r", stdin);
    freopen("output2.txt", "w", stdout);

    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d %d %lld", &n, &m, &k);
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
            scanf("%d", &arr[i][j]);
            ord[arr[i][j]].push_back(make_pair(i, j));
        }

        int MIN = 1, MAX = max(n, m), ANS = max(n, m);
        while(MIN <= MAX){
            int MID = (MIN + MAX)/2;
            if(calc(MID) >= k) ANS = MID, MAX = MID - 1;
            else MIN = MID + 1;
        }

        printf("Case #%d: %d\n", tc, ANS);

        for(int i=1; i<=n*m; i++) ord[i].clear();
    }
}

D. Splitting Hares

사실 C를 푼 시점에서 스코어보드를 보고 D를 풀 의지가 거의 없었다. 몇 가지 관찰 정도만 한 뒤, 구현에서 신경써줘야 할 요소가 굉장히 많겠다는 사실을 인지하고 바로 포기했다.

대략적인 몇 가지 아이디어만 적어보면,

• $W$가 모두 주어졌을 때 어떻게 묶는 것이 최선일까? 일단 정렬해 두고 인접한 수들을 묶는 게 최선임이 자명하다. 또한 네 개 이상의 수가 한 그룹으로 묶이면 둘/둘로 쪼개는 것이 이득이다. 따라서 $W$의 크기 순으로 정렬하고, 인접한 두 개 혹은 세 개의 점을 묶는 것이 최선일 것이다.
• 따라서 문제에서 주어진 점들을 $C$별로 나눈 뒤, $4$개 이상의 점이 같은 색이거나, 크기 관계가 정의되지 않는 (즉 색이 $c_1$인 $w_i$와 색이 $c_2$인 $w_j$에 대해 $w_i > w_j$ 그리고 $w_i < w_j$인 경우가 동시에 존재한다면) 경우 불가능을 바로 선언할 수 있다. 그렇지 않다면, 만약 특정 색에 대해 $w$ 값이 하나도 정해지지 않은 것이 있다면 매우 큰 $w$ 값 쪽에 $1$씩 인접하도록 배치해 최적해를 보장할 수 있다.
• 이제 모든 집합의 크기가 $2$ 또는 $3$인 상황이다. 왼쪽 그룹부터 차례로 보면서 DP를 해 줄 수 있으면 좋겠다. DP를 하려면 무엇을 저장해야 할까? 대략적으로 필요한 정보는 현재 보는 그룹의 위치, 그룹의 마지막 원소의 인덱스, 그리고 여기까지 묶었을 때 $F$의 값 등등이 필요할 것 같다.
• $F$를 묶는 방법은 점화식을 생각해 보면 여러 가지일 수 있다. 그러나 그 상대적인 차이만을 저장해 항을 하나 줄일 수 있고, 복잡도에서 $W_i$ 항을 제거할 수 있다. 이렇게 하면 대략 네제곱 정도의 풀이를 찾을 수 있다.

전체 풀이는 여기에서 볼 수 있다.