ABC 326 Upsolving

대회 참가 유무: Y
최종 Performance: 1214 (Rank: 1852 / 11827)
Round 링크: Top / Tasks
문제별 결과

A	B	C	D	E	F	G
AC	AC	AC	AC	-	-	-

A - 2UP3DOWN

문제 링크: https://atcoder.jp/contests/abc326/tasks/abc326_a
Score: 100점
문제 예상 티어: Bronze V

조건에 맞게 Takahashi가 계단을 탈지 엘베를 탈지 결정해주면 된다.

B - 326-like Numbers

문제 링크: https://atcoder.jp/contests/abc326/tasks/abc326_b
Score: 200점
문제 예상 티어: Silver V

문제에서 항상 이런 숫자가 존재한다고 했기 때문에 그냥 구현하면 되었다. 증명하라고 하면 쉽지 않을 듯.

C - Peak

문제 링크: https://atcoder.jp/contests/abc326/tasks/abc326_c
Score: 300점
문제 예상 티어: Gold V

N의 범위가 $N \le 3 \times 10^5$ 이고, 숫자의 범위 $A_i \le 10^9$ 이기 때문에, 정렬 후 lower_bound를 통해 적절한 구간 $(x, x + M)$ 안에 속한 원소들의 수를 구해주면 되는 문제였다. 만약 숫자의 범위가 작다면 완탐이 오히려 빠를 수도 있지만 이 문제의 경우에는 아니었다.

D - ABC Puzzle

문제 링크: https://atcoder.jp/contests/abc326/tasks/abc326_d
Score: 450점
문제 예상 티어: Gold III

조금 까다로운 조건의 문제였다. 가지치기 dfs로 접근했는데 풀이가 뇌절의 뇌절을 거듭한 가운데 종료 5분전에 제출 할 수 있었다. 덕분에 다른 문제들도 풀만한 것들이었는데 풀 시간이 없었다..

처음에 dfs를 2개로 나누어 생각했지만 이것은 오히려 패착이었다. 간단한 조건으로 푸는게 항상 옳다. 그냥 $x$ -> $x + 1$ 로 전이 시키고, $x$ == $N - 1$ 이 될 때 다음 row로 가게 하는 dfs가 유효했다. 다음에는 이런 유형 나올 때 너무 어렵게 접근하지 말자..

E - Revenge of “The Salary of AtCoder Inc.” (Solved with Editorial)

문제 링크: https://atcoder.jp/contests/abc326/tasks/abc326_e
Score: 450점
문제 예상 티어: Platinum V
기댓값 이론 정리: 링크

기댓값 DP 유형 이라고 한다. 문제 내에서 Modular Inverse도 요구하는 등 상당히 백준에서 일반적으로 접하기는 어려운 유형이다. 에디토리얼을 보고 풀이를 정리해본다.

우선, 기댓값을 바로 구하기에는 난이도가 있다. 기댓값을 구하기 이전에, 확률을 먼저 구해보도록 하자. $p_i$ 를 $A_i$ 엔이 지급되었을 때의 확률이라고 하자. 편의상 $p_0 = 1$ 로 정의하자. 그러면, 다음을 얻을 수 있다고 한다.

$p_i = \displaystyle \frac 1 N \sum_{j=0}^{i-1} p_j$

위 수식을 처음부터 생각하기 어렵다. small to large 해보자. 만약 $N = 1$ 이라면 자명하게 $p_1 = 1$ 이다. $N = 2$ 라면 아래와 같은 경우가 있다.

$p_1 = \displaystyle \frac 1 2 (1) = \frac 1 2$ … 처음 주사위를 던져서 1이 나왔을 확률
$p_2 = \displaystyle \frac 1 2 (1 + \frac 1 2) = \frac 3 4$ … (처음에 2가 바로 나왔을 확률) + (처음 주사위를 던져서 1, 그다음 2가 나왔을 확률)

모든 확률의 합이 $1$ 이 되지 않았다고 해서 당황할 필요는 없다. 지금 모든 확률이 독립인 경우를 다루고 있는 것이 아니다. $p_i$ 를 $A_i$ 엔이 지급되었을 때의 확률이라고 정의하고 있다. (실제 기댓값을 구하기 용이하도록) $N = 3$ 인 경우를 한번 더 생각해보자.

$p_1 = \displaystyle \frac 1 3 (1) = \frac 1 3$
$p_2 = \displaystyle \frac 1 3 (1 + \frac 1 3) = \frac 4 9$
$p_2 = \displaystyle \frac 1 3 (1 + \frac 1 3 + \frac 4 9) = \frac {16} {27}$

여기서 $\frac 1 3$ 은 현재 $p_i$ 가 나오게 된 확률, 그리고 괄호 안에 들어간 숫자들의 합은 그 전 눈금들에 가 있는 상태들의 합이다. 수식이 어려울 뿐 DP 상태전이를 완벽하게 나타낸 표현이라고 볼 수 있다. 또한 위 수식은 누적합을 활용해 $O(N)$ 에 계산할 수 있다.

그리고 문제에서 최종적으로 우리가 구하고자 하는 값은 기댓값이고, 기댓값은 정의에 의해 아래처럼 구할 수 있다.

$E[X] = \displaystyle \sum_{i=1}^{N} x_ip_i$

위 사실들을 조합하고, Modular Inverse를 이용해 최종적인 답을 구할 수 있다. 문제에서 나온 $998244353$ 라는 수는 AtCoder에서 좋아하는 소수인 듯 하다. 이 체 에서 $\displaystyle \frac 1 N$ 은 아래와 같이 구할 수 있다. getInv(N) 으로 구하면 된다.

ll fastPow(ll a, ll p) {
    ll res = 1LL;
    while (p) {
        if (p & 1LL) res = res * a % MOD;
        a = a * a % MOD;
        p >>= 1LL;
    }
    return res;
}

ll getInv(ll v) {
    return fastPow(v, MOD - 2);
}

F - Robot Rotation (Upsolved)

문제 링크: https://atcoder.jp/contests/abc326/tasks/abc326_f
Score: 525점
문제 예상 티어: Platinum V

$N \le 80$ 조건에서 MITM의 냄새를 강하게 느꼈지만, 확신은 없었다. 방향이 2방향이라 양방향에서 출발하면 경우의 수가 $2^{40}$ 이고 이는 꽤 큰 수이기 때문.. 이 풀이가 유효한지 한번 도전해보려고 한다. (아니면 어쩔 수 없고..)

관찰해보면, 우선 처음 로봇의 방향의 양의 x축이다. 그리고 90도씩만 좌우로 회전을 하므로, $i$ 가 홀수인 항은 $y$ 좌표를, $i$ 가 짝수인 항은 $x$ 좌표를 결정짓는다는 사실을 먼저 관찰할 수 있다. 이렇게 되면 우선 각 축으로의 좌표가 $2^{40}$ 으로 줄어든다. 이 상태에서 MITM을 적용하면 $2^{20}$ 정도에 풀 수 있고 이는 해볼만 하다. 도착 좌표를 알고 있으므로 원점과, 도착 좌표 양쪽에서 MITM을 적용하면 풀린다.

…그런데 이렇게까지 하고 끝내면 사실 Gold I 정도의 난이도일 수 있다. 여기에 문제는 경로 복원 까지 요구한다. MITM을 하면서, 도달한 경로를 잘 저장했다가 복원해줘야 하는 로직이 추가된다.

다소 복잡한 MITM이고, 아래에 풀이를 정리해둔다. 시간복잡도는 $O(N 2^{N/4})$ 이 된다. (내 실제 풀이는 로그가 하나 더 붙긴하는데 대세에 지장은 없다)

풀이·코드 펼치기

ll N, X, Y;
void solve() {
    scanf("%lld %lld %lld", &N, &X, &Y);
    vector<ll> dx, dy;
    for(int i = 0; i < N; ++i) {
        ll tmp; scanf("%lld", &tmp);
        if (i % 2 == 0) {
            dy.push_back(tmp);
        } else {
            dx.push_back(tmp);
        }
    }
    int dxsz1 = dx.size() / 2;
    int dysz1 = dy.size() / 2;
    int dxsz2 = dx.size() - dxsz1;
    int dysz2 = dy.size() - dysz1;

    // 1. 원점에서 출발하기
    map<ll, int> px, py;
    int end = 1 << dxsz1;
    for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들
        ll cx = 0;
        for(int i = 0, p = 1; i < dxsz1; ++i, p <<= 1) {
            if (cur & p) {
                cx += dx[i];
            } else {
                cx -= dx[i];
            }
        }
        px.insert({cx, cur});
    }
    end = 1 << dysz1;
    for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들
        ll cy = 0;
        for(int i = 0, p = 1; i < dysz1; ++i, p <<= 1) {
            if (cur & p) {
                cy += dy[i];
            } else {
                cy -= dy[i];
            }
        }
        py.insert({cy, cur});
    }

    // 2. 뒤에서 출발하기
    end = 1 << dxsz2;
    bool xflag = false;
    int x1, x2;
    for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들
        ll cx = X;
        for(int i = 0, p = 1; i < dxsz2; ++i, p <<= 1) {
            if (cur & p) {
                cx -= dx[dxsz1 + i];
            } else {
                cx += dx[dxsz1 + i];
            }
        }
        if (px.find(cx) != px.end()) {
            xflag = true;
            x1 = px[cx];
            x2 = cur;
            break;
        }
    }

    end = 1 << dysz2;
    bool yflag = false;
    int y1, y2;
    for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들
        ll cy = Y;
        for(int i = 0, p = 1; i < dysz2; ++i, p <<= 1) {
            if (cur & p) {
                cy -= dy[dysz1 + i];
            } else {
                cy += dy[dysz1 + i];
            }
        }
        if (py.find(cy) != py.end()) {
            yflag = true;
            y1 = py[cy];
            y2 = cur;
            break;
        }
    }
    if (xflag && yflag) {
        printf("Yes\n");
        // x1: 2진수, dxsz1
        // x2: 2진수, dxsz2, 거꾸로
        vector<int> x, y;
        for(int i = 0, p = 1; i < dxsz1; ++i, p <<= 1) {
            if (p & x1) x.push_back(1);
            else x.push_back(-1);
        }
        for(int i = 0, p = 1; i < dysz1; ++i, p <<= 1) {
            if (p & y1) y.push_back(1);
            else y.push_back(-1);
        }
        for(int i = 0, p = 1; i < dxsz2; ++i, p <<= 1) {
            if (p & x2) x.push_back(1);
            else x.push_back(-1);
        }
        for(int i = 0, p = 1; i < dysz2; ++i, p <<= 1) {
            if (p & y2) y.push_back(1);
            else y.push_back(-1);
        }

        _D("X: ");
        for(auto& item: x) _D("%d ", item);
        _D("\n");
        _D("Y: ");
        for(auto& item: y) _D("%d ", item);
        _D("\n");

        int last = 1;
        string ans = "";
        bool isY = true;
        int cy = 0, cx = 0;
        for(int i = 0; i < N; ++i) {
            if (isY) {
                // y
                if (last > 0 && y[cy] > 0) { ans += "L"; last = 1; }
                else if (last > 0 && y[cy] < 0) { ans += "R"; last = -1; }
                else if (last < 0 && y[cy] > 0) { ans += "R"; last = 1; }
                else if (last < 0 && y[cy] < 0) { ans += "L"; last = -1; }
                ++cy;
                isY = false;
            } else {
                // x
                if (last > 0 && x[cx] > 0) { ans += "R"; last = 1; }
                else if (last > 0 && x[cx] < 0) { ans += "L"; last = -1; }
                else if (last < 0 && x[cx] > 0) { ans += "L"; last = 1; }
                else if (last < 0 && x[cx] < 0) { ans += "R"; last = -1; }
                ++cx;
                isY = true;
            }
        }
        printf("%s\n", ans.c_str());
    } else {
        printf("No\n");
    }
}

G - Unlock Achievement (To be Upsolved?)

문제 링크: https://atcoder.jp/contests/abc326/tasks/abc326_g
Score: 625점
문제 예상 티어: Platinum III

Editorial을 보니 유량 문제라고 한다. Upsolving을 해볼까..?