Ccmmutty logo
Commutty IT
・19 min read

水色コーダーが ABC 全問解説する【ABC283】

AtCoder競技プログラミングAtCoderBeginnerContest
https://cdn.magicode.io/media/notebox/92618fa2-d06e-487c-b9d4-a457bc8a2aae.jpeg

ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283)

4 完(´・ω・｀)　5 完でパフォ下限 1500 くらいだから難しめかな？
でも、公式解説見た感じ、持ち物検査的な問題が多いような…？

A - Power

for ループで単純に掛け算するだけで OK。AB≤99<231A^B \leq 9^9 < 2^{31} なので int でもオーバーフローしない。C++ には pow 関数があるので、それを使ってもいい (ただし、cout を使う場合、指数表記にならないように注意すること)。
公式解説の注意にもあるように、条件が AB<260A^B<2^{60} とかだった場合は、pow 関数だとオーバーフローする可能性がある。powl 関数を使えば、2602^{60} 程度でもオーバーフローしない。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;

    cin >> a >> b;

    // 整数型に変換して指数表記を回避
    cout << (int)pow(a, b);

    return 0;
}

B - First Query Problem

どちらの操作も O(1)O(1) なので、そのまま実装すればいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q;

    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    cin >> q;
    for (int i = 0, t, k, x; i < q; ++i) {
        cin >> t;
        if (t == 1) {
            cin >> k >> x;
            a[k] = x;
        } else {
            cin >> k;
            cout << a[k] << '\n';
        }
    }

    return 0;
}

C - Cash Register

0 以外は、必ず 11 回ボタンを押す必要がある。0 の場合は、0 が kk 回連続しているとき、少なくとも ⌊k+12⌋\lfloor \frac{k+1}{2} \rfloor 回ボタンを押す必要がある。このまま実装してもいいし、連続する 0 のうち奇数個目のときのみ 11 カウントするのでもいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    string s;
    int ans = 0;

    cin >> s;

    bool odd0 = false;  // 連続する 0 が奇数番目か
    for (int i = 0, sz = s.size(); i < sz; ++i) {
        if (s[i] == '0') {  // 0 なら
            odd0 ^= true;     // 偶奇を反転
            if (odd0) ++ans;  // 奇数番目なら 1 加算
        } else {  // 0 でないなら
            odd0 = false;     // 0 の偶奇をリセット
            ++ans;            // 1 加算
        }
    }

    cout << ans;

    return 0;
}

D - Scope

箱に入っているボールと、) が来たときに消せるボールをそれぞれ保持しておけばいい。 ) が来たときに消せるボールは、( が来るたびに別々に保持する必要があるので、以下のように実装する (以下は入力例 11 の図)。

このように、( が来るたび、新しく格納場所を追加し、文字が来るたび、11 番新しい格納場所に格納する。また、) が来るたび、11 番新しい格納場所に格納されているボールを全体のボールから消し、11 番新しい格納場所も消す。
最後まで全体のボールが被らなかったので、答えは Yes。
以下は入力例 22 の場合である。

このように、全体のボールの文字が被った時点で気を失うので終了。答えは No。
ボールを保持するには set や配列を使えば OK。また、格納場所の保持には stack などがいい。文字の種類数を CC とおくと、set なら O(∣S∣log⁡C)O(|S| \log C)、配列なら O(∣S∣C)O(|S|C)。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    string s;

    cin >> s;

    // 全体のボール
    vector<bool> ball(26);
    // 格納場所の保持用
    stack<vector<bool>> st;
    // 初期状態の格納場所の個数は 1 個
    st.push(vector<bool>(26));
    for (int i = 0, sz = s.size(); i < sz; ++i) {
        if (s[i] == '(') {  // '(' なら
            st.push(vector<bool>(26));  // 格納場所を追加
        } else if (s[i] == ')') {  // ')' なら
            vector<bool> &del = st.top();  // 最新の格納場所を取得
            // ボールを消す
            for (int j = 0; j < 26; ++j) {
                if (del[j]) ball[j] = false;
            }

            st.pop();  // 最新の格納場所を消す
        } else {  // 文字なら
            if (ball[s[i] - 'a']) {  // すでに箱にボールが入っているなら
                cout << "No";  // 答えは "No"
                return 0;      // 終了
            } else {  // 入ってないなら
                // それぞれに追加
                ball[s[i] - 'a'] = true;
                st.top()[s[i] - 'a'] = true;
            }
        }
    }

    // 操作を最後まで出来れば答えは "Yes"
    cout << "Yes";

    return 0;
}

E - Don't Isolate Elements

時間外で通せたけど…、DP か…。
ii 行目が孤立するかどうかは、i−1i-1 行目と i+1i+1 行目にのみ依存する。ii 行目、i+1i+1 行目を反転するかをそれぞれ curcur、nextnext (反転しているなら 11、していないなら 00) とおいて、
dp[i][cur][next]dp[i][cur][next] := (11 から ii 行目まで孤立した要素がないときの操作回数の最小値)
とすれば、i−1i-1 行目を反転するかを prevprev とおいて、prev,cur,nextprev,cur,next の 88 通りの選び方それぞれに対して、ii 行目が孤立しないなら、
dp[i][cur][next]=min⁡(dp[i][cur][next],dp[i−1][prev][cur]+next)dp[i][cur][next]=\min(dp[i][cur][next],dp[i-1][prev][cur]+next)
で更新すればいい。
dpdp の各値は ∞\infty で初期化し、dp[1]dp[1] は、cur,nextcur,next の 44 通りの選び方それぞれに対して、11 行目が孤立しないなら、
dp[0][cur][next]=cur+nextdp[0][cur][next]=cur+next
で初期化し、i=2i=2 から順に更新していけばいい。答えは、min⁡(dp[H][0][0],dp[H][1][0])\min(dp[H][0][0],dp[H][1][0])。
DP の状態数が O(H)O(H) で、遷移数が各 O(1)O(1)、孤立しているかの計算に各 O(W)O(W) かかるので、合わせて O(HW)O(HW)。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// a_{i, j} が孤立しているか調べる
// prev, cur, next はそれぞれ i - 1 行目、i 行目、i + 1 行目を反転しているか (しているなら 1、していないなら 0)
bool isIsolate(int i, int j, int prev, int cur, int next, int h, int w, vector<vector<vector<int>>> &a) {
    int x[4] = {1, 0, -1, 0};
    int y[4] = {0, 1, 0, -1};
    int rev[3] = {prev, cur, next};

    for (int k = 0; k < 4; ++k) {
        int ii = i + x[k], jj = j + y[k];
        if (0 <= ii && ii < h && 0 <= jj && jj < w) {
            if (a[cur][i][j] == a[rev[1 + x[k]]][ii][jj]) {
                return false;
            }
        }
    }

    return true;
}

int main() {
    int h, w;

    cin >> h >> w;

    // a[0] は A、a[1] は反転した A
    vector<vector<vector<int>>> a(2, vector<vector<int>>(h, vector<int>(w)));
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            cin >> a[0][i][j], a[1][i][j] = a[0][i][j] ^ 1;

    // 任意の要素が孤立した要素でない状態にすることが不可能な場合
    const int INF = 1 << 30;
    // dp[i][cur][next] は、0 ~ i 行目が孤立しないときの反転の最小回数
    // cur, next はそれぞれ i 行目、i + 1 行目を反転しているか (しているなら 1、していないなら 0)
    vector<vector<vector<int>>> dp(h, vector<vector<int>>(2, vector<int>(2, INF)));
    // i = 0 のときの初期化
    for (int cur = 0; cur < 2; ++cur) {
        for (int next = 0; next < 2; ++next) {
            bool flag = true;  // 孤立をなくせるか
            for (int j = 0; j < w; ++j) {
                if (isIsolate(0, j, 0, cur, next, h, w, a)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {  // 孤立をなくせるなら
                dp[0][cur][next] = cur + next;  // 反転回数を cur + next で初期化
            }
        }
    }

    for (int i = 1; i < h; ++i) {
        for (int prev = 0; prev < 2; ++prev) {
            for (int cur = 0; cur < 2; ++cur) {
                for (int next = 0; next < 2; ++next) {
                    bool flag = true;
                    for (int j = 0; j < w; ++j) {
                        if (isIsolate(i, j, prev, cur, next, h, w, a)) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        dp[i][cur][next] =
                            min(dp[i][cur][next], dp[i - 1][prev][cur] + next);
                    }
                }
            }
        }
    }

    int ans = min(dp[h - 1][0][0], dp[h - 1][1][0]);

    cout << (ans == INF ? -1 : ans);

    return 0;
}

F - Permutation Distance

max⁡j<i,Pj<Pi(Pj+j)\displaystyle\max_{j<i,P_j<P_i}(P_j+j) を ii ごとに取得するには、max⁡Pj<Pi(Pj+j)\displaystyle\max_{P_j<P_i}(P_j+j) を ii の小さい順に逐次、取得 & 更新すればいいのか…。これを実装できたとしても、公式解説の解き方だと、式もややこしいし難しくない…？
Manhattan MST さえ持っていれば、別解で瞬殺だし、持ってなかったけど、Manhattan MST、汎用性ありそうなので、別解で解きました。
Manhattan MST の解き方は、こことここを参考にしました。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// Manhattan MST
// 組 (最小全域木の辺のコストの総和, 辺) を返す
template <typename T>
pair<T, vector<tuple<T, int, int>>> RMST(vector<T> &xs, vector<T> &ys) {
    int n = xs.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);

    vector<tuple<T, int, int>> edge;

    auto comp = [&](int i, int j) { return xs[i] + ys[i] < xs[j] + ys[j]; };

    /* --[begin]-- http://users.eecs.northwestern.edu/~haizhou/publications/zhou02ipl.pdf */
    for (int s = 0; s < 2; ++s) {
        sort(idx.begin(), idx.end(), comp);
        for (int t = 0; t < 2; ++t) {
            map<T, int> sweep;
            for (int i : idx) {
                for (auto itr = sweep.lower_bound(~xs[i]); itr != sweep.end(); itr = sweep.erase(itr)) {
                    int j = itr->second;
                    if (xs[j] - ys[j] < xs[i] - ys[i]) break;

                    edge.emplace_back(abs(xs[i] - xs[j]) + abs(ys[i] - ys[j]), i, j);
                }
                sweep[~xs[i]] = i;
            }
            swap(xs, ys);
        }
        for (int i = 0; i < n; ++i) xs[i] = -xs[i];
    }
    /* ---[end]--- http://users.eecs.northwestern.edu/~haizhou/publications/zhou02ipl.pdf */

    sort(edge.begin(), edge.end());
    T sum = 0;
    vector<tuple<T, int, int>> ret;

    class UnionFind {
        vector<int> p;
    public:
        UnionFind(int n) : p(n, -1) {}
        void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (p[x] < p[y]) { p[x] += p[y]; p[y] = x; } else { p[y] += p[x]; p[x] = y; } return; }
        int find(int x) { if (p[x] < 0) return x; while (p[p[x]] >= 0) { p[x] = p[p[x]]; x = p[x]; if (p[x] < 0) return x; } return p[x]; }
        bool isSame(int x, int y) { return find(x) == find(y); }
    } uni(n);

    for (auto [cost, i, j] : edge) {
        if (!uni.isSame(i, j)) {
            uni.unite(i, j);
            sum += cost;
            ret.emplace_back(cost, i, j);
        }
    }

    return {sum, ret};
}

int main() {
    int n;

    cin >> n;

    const int INF = 1 << 30;
    vector<int> idx(n), p(n), ans(n, INF);
    for (int i = 0; i < n; ++i) cin >> p[i], idx[i] = i;

    auto [cost, edge] = RMST(idx, p);

    // 最小全域木の辺をすべて走査して、最小値を更新
    for (auto [d, i, j] : edge) {
        ans[i] = min(ans[i], d);
        ans[j] = min(ans[j], d);
    }

    for (int i = 0; i < n; ++i) cout << ans[i] << ' ';

    return 0;
}

G - Partial Xor Enumeration

AA に対してビット単位で掃き出し法をしたあと、00 を除いた列を A′A' をおくと、A′A' の連続とは限らない (空でもよい) 部分列の xor\text{xor} として得られる整数は、部分列ごとにすべて異なる。また、その集合は、集合 {s1,s2,⋯ ,sk}\{s_1,s_2, \cdots ,s_k\} と一致する。なので、k=2∣A∣k=2^{|A|} である。
また、A′A' の要素を小さい順に、a0,a1,⋯ ,a∣A∣−1a_0,a_1,\cdots,a_{|A|-1} とおく。i−1i-1 の 11 が立っているビットを b0,b1,⋯ ,bcntb_0,b_1, \cdots, b_{cnt} (0≤b0<b1<⋯<bcnt<∣A∣)(0 \leq b_0 < b_1< \cdots < b_{cnt} < |A|) (cnt(cnt は、11 が立っているビットの数)) とおくと、sis_i は (ab0,ab1,⋯ ,abcnt)(a_{b_0},a_{b_1},\cdots, a_{b_{cnt}}) の xor\text{xor} と一致する。なので、i=L,⋯ ,Ri=L, \cdots, R の順にそれを出力すればいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// ビット単位の掃き出し法 (返り値は rank)
int GaussianElimination(vector<ll> &a) {
    int sz = a.size();
    int rank = 0;
    vector<int> top;
    for (int i = 59; i >= 0; --i) {
        bool flag = false;
        for (int j = rank; j < sz; ++j) {
            if (a[j] & (1ll << i)) {
                swap(a[j], a[rank]);
                flag = true;
                top.push_back(i);
                break;
            }
        }
        if (flag) {
            for (int j = rank + 1; j < sz; ++j) {
                if (a[j] & (1ll << i)) {
                    a[j] ^= a[rank];
                }
            }
            ++rank;
        }
    }

    for (int i = rank - 1; i > 0; --i) {
        for (int j = i - 1; j >= 0; --j) {
            if (a[j] & (1ll << top[i])) {
                a[j] ^= a[i];
            }
        }
    }

    return rank;
}

int main() {
    int n;
    ll l, r;

    cin >> n >> l >> r;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int rank = GaussianElimination(a);
    // a_0, …, a_{rank - 1} は降順なので反転する
    reverse(&a[0], &a[rank]);
    // a_rank 以降は 0 なので要らない
    a.resize(rank);

    for (ll i = l - 1; i < r; ++i) {
        ll output = 0;
        for (int j = 0; j < rank; ++j) {
            if (i & (1ll << j)) {  // 1 が立っているビットのとき
                output ^= a[j];  // xor を取る
            }
        }
        cout << output << ' ';
    }

    return 0;
}

Ex - Popcount Sum

ちょっとした別解にあるように popcount が x−∑i=1∞⌊x2i⌋x-\displaystyle\sum_{i=1}^{\infty} \left\lfloor \frac{x}{2^i} \right\rfloor で求められるの面白い。ということは、
int popcount = x;
for (int i = x >> 1; i; i >>= 1) {
    popcount -= i;
}
とかで popcount を出せるのか。11 ビットずつ 11 かどうか調べるコードより綺麗。(今回の問題では使わないけど。)
問題の答えは、公式解説の式か、ちょっとした別解の式を使って、ビットごとに floor sum を求めればいい。floor sum 知っていれば簡単…？ (知らなかったけど。)
floor sum は AtCoder Library (ACL) にもあるのでそれを使えば OK。私は一応、ACL やここを参考にして作ってみました。
公式解説にコードがないので、公式解説の式で実装。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// i の範囲が [0, n) での floor((a * i + b) / m) の総和を返す
long long floorSum(long long n, long long m, long long a, long long b) {
    long long ans = 0;
    if (a < 0) {
        long long apos = a % m;
        if (apos < 0) apos += m;
        ans -= n * (n - 1) / 2 * ((apos - a) / m);
        a = apos;
    }
    if (b < 0) {
        long long bpos = b % m;
        if (bpos < 0) bpos += m;
        ans -= n * ((bpos - b) / m);
        b = bpos;
    }

    while (true) {
        if (a >= m) {
            ans += n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }

        long long ymax = a * n + b;
        if (ymax < m) break;

        n = ymax / m;
        b = ymax % m;
        swap(m, a);
    }

    return ans;
}

int main() {
    int t;
    int N, M, R;

    cin >> t;

    for (int i = 0; i < t; ++i) {
        cin >> N >> M >> R;

        // 1 以上 N 以下の整数であって、M で割った余りが R になるものの個数
        int n = (N - R) / M + 1;
        ll ans = 0;

        for (int k = 0; k < 30; ++k) {
            ans += floorSum(n, 1 << (k + 1), M, R + (1 << k)) -
                   floorSum(n, 1 << (k + 1), M, R);
        }

        cout << ans << '\n';
    }

    return 0;
}

Discussion

コメントにはログインが必要です。