---
id: "imported/blog/history/at/abc-330"
title: "AtCoder Beginner Contest 330"
description: "E를 1분 차이로 제출하지 못한 셋이다. 그래서 한문제 차이로 상당히 망한 퍼포가 나왔다."
kind: "record"
published: "2023-11-25T00:00:00.000Z"
tags: ["PS","atcoder"]
url: "https://www.readiz.com/blog/history/at/abc-330/"
markdownUrl: "https://www.readiz.com/blog/history/at/abc-330/index.md"
---

# AtCoder Beginner Contest 330

# ABC 330 Upsolving

![원문에 첨부된 이미지](https://www.readiz.com/assets/2023-12-03-22-28-33.png)

- 대회 참가 유무: Y
- 최종 Performance: 868 (Rank: 3161 / 10234)
- Round 링크: [Top](https://atcoder.jp/contests/abc330) / [Tasks](https://atcoder.jp/contests/abc330/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)$이다.

```cpp
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`였고, 나는 구간 관리하는 식으로 풀었다. 너무 어렵게 풀어서 시간내에 못낸거 같다.

```cpp
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