ABC 420

Table of Contents

https://atcoder.jp/contests/abc420

A. What month is it?

https://atcoder.jp/contests/abc420/tasks/abc420_a

自力 AC

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll X, Y;
    cin >> X >> Y;

    X += Y;
    X %= 12;

    if (X == 0) X = 12;
    cout << X << endl;
}

B. Most Minority

https://atcoder.jp/contests/abc420/tasks/abc420_b

自力 AC

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vector<string> S(N);
    rep(i, N) cin >> S[i];

    vll scores(N);
    rep(j, M) {
        ll x = 0, y = 0;
        rep(i, N) {
            if (S[i][j] == '0')
                x++;
            else
                y++;
        }

        if (x == 0 || y == 0) {
            rep(i, N) scores[i]++;
            continue;
        }

        if (x < y) {
            rep(i, N) {
                if (S[i][j] == '0') scores[i]++;
            }
        } else {
            rep(i, N) {
                if (S[i][j] == '1') scores[i]++;
            }
        }
    }

    ll mx = 0;
    rep(i, N) {
        chmax(mx, scores[i]);
    }

    vll ans;
    rep(i, N) if (scores[i] == mx) ans.push_back(i + 1);
    print(ans);
}

C. Sum of Min Query

https://atcoder.jp/contests/abc420/tasks/abc420_c

自力 AC

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;
    vll A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];

    ll sum = 0;
    rep(i, N) sum += min(A[i], B[i]);

    rep(i, Q) {
        char c;
        cin >> c;
        ll x, v;
        cin >> x >> v;
        x--;
        sum -= min(A[x], B[x]);
        if (c == 'A') {
            A[x] = v;
        } else {  // c == 'B'
            B[x] = v;
        }
        sum += min(A[x], B[x]);
        cout << sum << endl;
    }
}

D. Toggle Maze

https://atcoder.jp/contests/abc420/tasks/abc420_d

自力 AC

表の世界と反転世界で BFS をする。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W;
    cin >> H >> W;
    vector<string> grid(H), invgrid(H);
    rep(i, H) cin >> grid[i];
    invgrid = grid;

    int si, sj, fi, fj;

    rep(i, H) rep(j, W) {
        if (invgrid[i][j] == 'o')
            invgrid[i][j] = 'x';
        else if (invgrid[i][j] == 'x')
            invgrid[i][j] = 'o';

        if (grid[i][j] == 'S') si = i, sj = j;
        if (grid[i][j] == 'G') fi = i, fj = j;
    }

    vector dist(2, vector(H, vll(W, INF)));
    dist[0][si][sj] = 0;

    // i, j, state, distance
    // state = 0 が表
    using P = tuple<ll, ll, ll, ll>;
    queue<P> que;
    que.push({si, sj, 0, 0});

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    while (que.size()) {
        auto [i, j, state, D] = que.front();
        que.pop();

        if (dist[state][i][j] < D) {
            continue;
        }

        rep(d, 4) {
            ll ni = i + di[d], nj = j + dj[d];
            if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj) continue;
            char nxmass = grid[ni][nj];
            if (nxmass == '#') continue;
            if (state == 0 && nxmass == 'x') continue;
            if (state == 1 && nxmass == 'o') continue;
            if (nxmass == '?') {
                if (dist[1 - state][ni][nj] > D + 1) {
                    dist[1 - state][ni][nj] = D + 1;
                    que.push({ni, nj, 1 - state, D + 1});
                }
            } else {
                if (dist[state][ni][nj] > D + 1) {
                    dist[state][ni][nj] = D + 1;
                    que.push({ni, nj, state, D + 1});
                }
            }
        }
    }

    ll ans = min(dist[0][fi][fj], dist[1][fi][fj]);
    if (ans == INF) ans = -1;
    cout << ans << endl;
}

E. Reachability Query

https://atcoder.jp/contests/abc420/tasks/abc420_e

自力 AC

連結性は Union Find で管理。各連結成分の黒ノードの数を別で管理して、クエリ 3 のときにそれを参照する。 黒ノードの数は leader node の番号基準で管理すればいい。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;

    dsu uf(N);
    vll cntb(N, 0);
    vint color(N);

    rep(i, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            int u, v;
            cin >> u >> v;
            u--, v--;

            if (uf.same(u, v)) {
                continue;
            }
            int l = uf.leader(u), r = uf.leader(v);
            ll lnum = cntb[l], rnum = cntb[r];
            int leader = uf.merge(u, v);
            cntb[leader] = lnum + rnum;
        } else if (t == 2) {
            int v;
            cin >> v;
            v--;

            int leader = uf.leader(v);
            if (color[v] == 1) {
                cntb[leader]--;
            } else {
                cntb[leader]++;
            }

            color[v] = 1 - color[v];
        } else {
            int v;
            cin >> v;
            v--;

            int leader = uf.leader(v);
            yesno(cntb[leader] > 0);
        }
    }
}

F. kirinuki

https://atcoder.jp/contests/abc420/tasks/abc420_f

わからん

G. sqrt(n²+n+X)

https://atcoder.jp/contests/abc420/tasks/abc420_g

自力 AC.

解説で言われているような内容はわかっていなかったが提出したら AC してしまった。

$\sqrt{n^2 + n + X}$ が整数ならば $n^2 + n + X = (n + a)^2$ となる整数 $a$ が存在する。

\begin{align*} &n^2 + n + X = (n + a)^2 \\ \Rightarrow ~~~ &n = \frac{X - a^2}{2a - 1} \end{align*}

となる。 $a \in [-10^8, 10^8]$ の範囲で全探索して $n$ が整数になるものを数えたら AC するかなぁと半信半疑で提出したら AC してしまった。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll X;
    cin >> X;

    set<int128> ans;
    rep2(x, -(ll)1e8, (ll)1e8 + 1) {
        int128 n = (X - x * x) / (2 * x - 1);
        if (n * (2 * x - 1) == X - x * x) ans.insert(n);
    }

    cout << ans.size() << endl;
    vector<int128> v;
    for (auto x : ans) v.push_back(x);
    print(v);
}