ABC 330 Upsolving

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

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

E를 1분 차이로 제출하지 못한 셋이다. 그래서 한문제 차이로 상당히 망한 퍼포가 나왔다.

A - Counting Passes

문제 링크: https://atcoder.jp/contests/abc329/tasks/abc330_a
Score: 100점
문제 예상 티어: Bronze IV

Do you know 반복문?

B - Minimize Abs 1

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

B 치고 난이도가 있는 문제였다. 출력 문제로 1틀을 했다. (케이스중 1개에서 공백 출력을 안했다;;) L 보다 왼쪽의 수일 경우 L이, R보다 오른쪽의 수일 경우 R이, 그 사이에 들어올 경우 자기 자신이 되어야 거리가 최소가 된다.

C - Minimize Abs 2

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

수학 문제. 수학 문제인 만큼 솔루션은 여러가지가 있을 수 있는데, 나는 그냥 매개변수탐색으로 해치웠다. 정해는 $O(\sqrt D)$ 이다.

void solve() {
    scanf("%lld", &N);
    ll sN = sqrt(N);
    ll ans = 0x7FFFFFFFFFFFFFFFLL;
    for(ll y = 0; y <= sN; ++y) {
        ll l = 0, r = sN + 1;
        ll yy = y * y;
        for(ll m = (l + r) >> 1; l <= r; m = (l + r) >> 1) {
            ll cur = yy + m * m;
            if (cur <= N) {
                l = m + 1;
                ans = min(ans, min(abs(cur - N), abs(yy + (m + 1) * (m + 1) - N)));
            } else {
                r = m - 1;
            }
        }
    }

    printf("%lld\n", ans);
}

D - Counting Ls

문제 링크: https://atcoder.jp/contests/abc330/tasks/abc330_d
Score: 400점
문제 예상 티어: Gold V

문제는 장황한데, 결국 케이스를 따져가면서 경우의 수를 따져보면, 각 row, col별로 o의 수를 미리 세어두고, 모든 $(i, j)$ 쌍에 대해 ans += (rcnt[i] - 1) * (ccnt[j] - 1)를 해주는 것이 답이다.

E - Mex and Update (Upsolved)

문제 링크: https://atcoder.jp/contests/abc330/tasks/abc330_e
Score: 475점
문제 예상 티어: Gold III

AC가 나왔는데 1분 늦어서 제출을 못했다. mex 연산은 일종의 웰논 연산이고(님게임 등에서 쓰이는듯), 어떻게 빠르게 다음 수를 찾는지가 관건이었다. 정해는 set이나 Segment Tree였고, 나는 구간 관리하는 식으로 풀었다. 너무 어렵게 풀어서 시간내에 못낸거 같다.

풀이·코드 펼치기

int N, Q;
int A[200010];
map<int, int> M;

struct Range {
    int l, r;
    bool operator<(const Range& t) const {
        if (l != t.l) return l < t.l;
        return r < t.r;
    }
};
set<Range> S;

void solve() {
    scanf("%d %d", &N, &Q);
    for(int i = 1; i <= N; ++i) {
        scanf("%d", &A[i]);
        if (M.find(A[i]) == M.end()) {
            M[A[i]] = 0;
        }
        M[A[i]]++;
    }
    for(auto& item: M) {
        S.insert({item.first, item.first});
    }
    for(auto sit = S.begin(); sit != S.end();) {
        Range cur = *sit;
        auto it = sit;
        ++it;
        if (it == S.end()) {
            break;
        } else {
            Range nitem = *it;
            if (cur.r + 1 == nitem.l) {
                S.erase(it);
                S.erase(sit);
                sit = S.insert({cur.l, nitem.r}).first;
            } else {
                sit = it;
            }
        }
    }

    for(auto& item: S) {
        _D("[d] %d ~ %d\n", item.l, item.r);
    }

    for(int q = 0; q < Q; ++q) {
        int idx, val; scanf("%d %d", &idx, &val);
        int old = A[idx];
        A[idx] = val;
        M[old]--;

        // 기존꺼 빼기
        if (M[old] == 0) {
            auto it = S.lower_bound({old, 0x7FFFFFFF});
            --it; // 무조건 있음 문제조건에서
            _D("[d] delete %d!\n", old);
            Range cur = *it;
            S.erase(cur);
            if (cur.r == old) {
                S.insert({cur.l, cur.r - 1});
                _D("(%d, %d) -> (%d, %d)\n", cur.l, cur.r, cur.l, cur.r - 1);
            } else if (cur.l == old) {
                S.insert({cur.l + 1, cur.r});
                _D("(%d, %d) -> (%d, %d)\n", cur.l, cur.r, cur.l + 1, cur.r);
            } else { // 사이
                S.insert({cur.l, old - 1});
                S.insert({old + 1, cur.r});
                _D("(%d, %d) -> (%d, %d) / (%d, %d)\n", cur.l, cur.r, cur.l, old - 1, old + 1, cur.r);
            }

            M.erase(old);
        }

        // 신규 넣기
        if (M.find(val) == M.end()) {
            _D("[d] add %d!\n", val);
            auto it = S.lower_bound({val, 0});
            if (it == S.begin()) {
                Range nitem = *it;
                if (nitem.l - 1 == val) {
                    S.erase(it);
                    S.insert({val, nitem.r});
                } else {
                    S.insert({val, val});
                }
            } else {
                auto pit = it;
                --pit;

                Range nitem = *it;
                Range pitem = *pit;

                if (pitem.r + 1 == val && nitem.l - 1 == val) {
                    S.erase(it);
                    S.erase(pit);
                    S.insert({pitem.l, nitem.r});
                } else if (pitem.r + 1 == val) {
                    S.erase(pit);
                    S.insert({pitem.l, val});
                } else if (nitem.l - 1 == val) {
                    S.erase(it);
                    S.insert({val, nitem.r});
                } else {
                    S.insert({val, val});
                }
            }
            
            M[val] = 0;
        }
        M[val]++;

        
        auto it = S.begin();
        Range cur = *it;
        _D("[begin] (%d, %d)\n", cur.l, cur.r);
        if (cur.l == 0) {
            printf("%d\n", cur.r + 1);
        } else {
            printf("0\n");
        }
    }
}

F - Minimize Bounding Square (To be upsolved…)

문제 링크: https://atcoder.jp/contests/abc330/tasks/abc330_f
Score: 525점
문제 예상 티어: ?

뭔가 웰논의 냄새가 나서 업솔빙 예정.

G

Skip