16か月前公開・15か月前更新・19 min read

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

AtCoder競技プログラミングAtCoderBeginnerContest

https://cdn.magicode.io/media/notebox/ecaef6d9-08ac-4a4d-80a9-9ece1a0cbde5.jpeg

HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

なんとか 6 完。D 問題で結構手こずったので危なかった…。6 ペナしたのは気になるけど、今回は多分難しめだったので、まぁ。

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

A - Generalized ABC

文字は数字と紐づけられています。A, B, …, Z には、アルファベット順に、

65,66,\cdots,90

が割り当てられていて、計算もできます。例えば、A +

1

は B になります。
これを知っていると、この問題は、

i=0, \cdots ,K-1

の順に A +

i

を出力すればいいとわかります。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int k;

    cin >> k;

    for (int i = 0; i < k; ++i) cout << (char)('A' + i);

    return 0;
}

B - Let's Get a Perfect Score

普通に全探索で条件を満たす組

(x,y)

を数えれば OK。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    int ans = 0;

    cin >> n >> m;

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

    // 全探索
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            bool flag = true;  // 参加者 i、参加者 j ペアは全問解けるか
            for (int k = 0; k < m; ++k) {
                // 二人とも解けない問題があるなら
                if (s[i][k] == 'x' && s[j][k] == 'x') {
                    flag = false;  // 全問解けない
                    break;
                }
            }
            if (flag) ++ans;  // 全問解けるなら答えに 1 加算
        }
    }

    cout << ans;

    return 0;
}

C - String Delimiter

左から順に " を数え上げる。" の個数が偶数個の間は、括られた文字でなく、" の個数が奇数個の間は、括られた文字であるので、" の個数が偶数個の間、, を . に置き換えればいい。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    string s;
    int cnt = 0;

    cin >> n >> s;

    for (int i = 0; i < n; ++i) {
        if (s[i] == '"') {  // '"' なら
            ++cnt;  // 数え上げ
        } else if (!(cnt & 1) && s[i] == ',') {  // '"' が偶数個のとき ',' なら
            s[i] = '.';  // '.' にする
        }
    }

    cout << s;

    return 0;
}

D - Make Bipartite 2

グラフ

G

が二部グラフでないなら、辺

(u,v)

追加後のグラフは二部グラフにならないので答えは

0

。

グラフ

G

が二部グラフなら、頂点

u

に対して、条件を満たす頂点

v

は、「頂点

u

と非連結」または「頂点

u

と色が異なり、辺でも結ばれていない」のいずれかである。言い換えると、条件を満たさない頂点

v

は、「頂点

u

と連結で色が同じ」または「頂点

u

と辺で結ばれている」のいずれかである。二部グラフであるので、「頂点

u

と辺で結ばれている」頂点

v

の色は頂点

u

と異なる。
そのため、各頂点

i

ごとに

N

-

(「頂点

i

と連結で色が同じ」頂点の個数)

-

(「頂点

i

と辺で結ばれている」頂点の個数) を答えに加算していけばいい。ただし、

u<v

でなくてはいけないため、最後に

2

で割る。

グラフ

G

が二部グラフかどうかは、BFS などで調べられる。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, m;
    ll ans = 0;

    cin >> n >> m;

    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 連結グラフごとに BFS
    queue<int> que;
    vector<int> d(n, -1);       // 距離 (未探索なら -1)
    vector<int> group(n);       // 連結している頂点同士は同じ値
    vector<array<int, 2>> cnt;  // group ごと、色 (偶奇) ごとの頂点数
    int cntG = 0;               // 連結グラフの数
    for (int i = 0; i < n; ++i) {
        if (d[i] != -1) continue;  // 探索済みなら continue
        cnt.push_back({0, 0});     // group[cntG] を初期化

        que.push(i);
        d[i] = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            group[v] = cntG;

            ++cnt[cntG][d[v] & 1];  // 根からの距離の偶奇で色分けしてカウント

            for (int child : g[v]) {
                if (d[child] == -1) {
                    d[child] = d[v] + 1;
                    que.push(child);
                } else if (!((d[child] + d[v]) & 1)) {  // 色分けに矛盾が起きたら
                    cout << 0;  // 二部グラフでないので、答えは 0
                    return 0;
                }
            }
        }
        ++cntG;
    }

    // 各頂点ごとに加算
    for (int i = 0; i < n; ++i) {
        ans += n - g[i].size() - cnt[group[i]][d[i] & 1];
    }

    cout << ans / 2;

    return 0;
}

E - Choose Two and Eat One

行動ごとに食べるボールを決めるのは大変なので、グループで考えてみる。

初期状態では、ボールはそれぞれボール

1

個のみのグループに所属している。

2

つのボールを選んだとき、それぞれのボールが所属しているグループを

1

グループにまとめてみる。選べる

2

つのボールを、違うグループに所属しているボールの組のみに限定すると、常に、各グループ内の食べられていないボールの数がそれぞれ

1

個になる。
これにより、ボールを食べることを、異なるグループの統合に置き換えられる。

最終的にグループが

1

つになるまで行動を続けるので、この問題は、「頂点

(u,v)

にコスト

(u^v+v^u) \bmod M

の辺を張ったグラフの最大全域木」の辺のコストの総和を求める問題に置き換えられる。

辺の個数は

O(N^2)

であるため、クラスカル法で、ソートに

O(N^2 \log N^2)

、連結に Union-Find を用いて

O(\alpha(N^2))

かかるので、

O(N^2 \log N)

で答えを求められる。

ちなみに、最大全域木の葉である頂点

x

を

1

つ選び、葉につながってる辺のもう一方を頂点

y

とし、

(x,y)

を取り出し、

x

を食べ、頂点

x

を削除することを、最大全域木の頂点が

1

つになるまで行うことで、最大値を獲得する行動ができる。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// Union-Find
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); }

    int size(int x) { return -p[find(x)]; }
};

// 法 mod での累乗
long long pow(long long n, long long m, long long mod) {
    long long ans = 1;
    while (m) {
        if (m & 1) ans = ans * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return ans;
}

int main() {
    int n, m;
    ll ans = 0;

    cin >> n >> m;

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

    // 最大全域木を求める用 ((コスト, 辺の 2 頂点) の組)
    vector<pair<ll, pair<int, int>>> edge;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            edge.emplace_back((pow(a[i], a[j], m) + pow(a[j], a[i], m)) % m,
                              make_pair(i, j));
        }
    }

    // クラスカル法 (最大全域木) (最小全域木の場合と逆にソートするだけ)
    sort(edge.rbegin(), edge.rend());  // 大きい順にソート

    UnionFind uni(n);
    for (auto [val, uv] : edge) {
        auto [u, v] = uv;
        if (!uni.isSame(u, v)) {  // 連結でないなら
            uni.unite(u, v);  // 連結する
            ans += val;       // 辺のコストを加算
        }
    }

    cout << ans;

    return 0;
}

F - Union of Two Sets

Sparse Table の二項演算を、集合の

\cup

にしたものを考えればいい。

N

列の配列を、

i

行目の

[l,r]

の幅が、

2^{i-1}

になるように作っていく。
入力例

1

の場合だとこのような感じで、

(l,r)

を作っていく。

(r>N

になる場合は

r=N

に補正

)

入力例

1

の場合は、実際は、

2

行 (幅:

2

) 、場合分けなしなら

3

行でいい。
必要な行数は、

\lceil \log N\rceil

(N=1

の場合は

1)

行。場合分けなしパターンは

\lfloor \log N \rfloor + 1

行。

以下、場合分けなしのパターンで話を進める。

このように配列を作ると、各クエリは、

\lfloor \log (R-L+1) \rfloor + 1

行目の、

L

列目と、

R

-

幅

+

1

列目を出力すればよくなる。わかりやすくいうと、

\frac{R-L+1}{2}

<

幅

\leq

R-L+1

となる幅の行から、

(l,?)

と

(?,r)

を取ってくればいい。

\lfloor \log 4000 \rfloor + 1=12

なので、

M \leq 4000 \times 12=48000 \leq 50000

も満たせる。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q;

    cin >> n;

    // log = floor(log N) + 1 (面倒なら log = 12 とかでも制約は満たせる)
    int log = 32 - __builtin_clz(n);
    int m = n * log;
    cout << m << endl;

    // 配列を出力
    for (int i = 0; i < log; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << j << ' ' << min((j + (1 << i)) - 1, n) << endl;
        }
    }

    cin >> q;

    // クエリ処理
    for (int i = 0, l, r; i < q; ++i) {
        cin >> l >> r;
        // 行は floor(log (r - l + 1)) 行目 (0-indexed)
        int row = 31 - __builtin_clz(r - l + 1);
        // row 行目の幅は 2 の row 乗
        // 配列の row 行 l 列目と、row 行 r - 幅 + 1 行目を出力
        cout << row * n + l << ' ' << row * n + r - (1 << row) + 1 << endl;
    }

    return 0;
}

G - Similar Permutation

DP は時間があれば何とか解ける (かもしれない)。

n=1

から順番に、

\{A_n,B_n\}

を選んでいくことを考える。

\{A_n,B_n\}

を選んだときに、

A_n,B_n

が、選べた数字の中で何番目に小さかったかをそれぞれ

i_n,j_n

とおく。選べた数字とは、それぞれ

\{A_1, \cdots ,A_{n-1}\},\{B_1, \cdots ,B_{n-1}\}

に含まれない

1

以上

N

以下の数字のことである。すると、

$i_n \geq i_{n-1}$ のとき、 $A_n>A_{n-1}$
$i_n < i_{n-1}$ のとき、 $A_n<A_{n-1}$

となる。同様に、

$j_n \geq j_{n-1}$ のとき、 $B_n>B_{n-1}$
$j_n < j_{n-1}$ のとき、 $B_n<B_{n-1}$

となる。すると、

「 $i_n \geq i_{n-1}$ かつ $j_n \geq j_{n-1}$ 」または「 $i_n < i_{n-1}$ かつ $j_n < j_{n-1}$ 」のとき、類似度が $1$ 増える。
「 $i_n \geq i_{n-1}$ かつ $j_n < j_{n-1}$ 」または「 $i_n < i_{n-1}$ かつ $j_n \geq j_{n-1}$ 」のとき、類似度は変わらない。

となり、類似度を

k

とおいて、以下のように DP を行える。

\begin{align*} dp[n][k][i_n][j_n]&=\sum_{i_{n-1}=1}^{i_n} \sum_{j_{n-1}=1}^{j_n} dp[n-1][k-1][i_{n-1}][j_{n-1}] + \sum_{i_{n-1}=i_n +1}^{N-n+1} \sum_{j_{n-1}=j_n +1}^{N-n+1} dp[n-1][k-1][i_{n-1}][j_{n-1}] \\ &+ \sum_{i_{n-1}=1}^{i_n} \sum_{j_{n-1}=j_n}^{N-n+1} dp[n-1][k][i_{n-1}][j_{n-1}] + \sum_{i_{n-1}=i_n}^{N-n+1} \sum_{j_{n-1}=1}^{j_n} dp[n-1][k][i_{n-1}][j_{n-1}] \end{align*}

dp[n-1][k]

と

dp[n-1][k-1]

それぞれに対して、

2

次元累積和を取っておけば、これは、

O(1)

で計算できる。

n=1

のとき、

\begin{cases} dp[1][k][i][j]=1 & (\text{if}\;\; k=0 ,1 \leq i \leq N,1 \leq j \leq N) \\ dp[1][k][i][j]=0 & (\text{otherwise}) \end{cases}

なので、これをもとに、

n=2, \cdots , N

の順に

dp[n][k][i_n][j_n]

を求めていけば OK。答えは、

dp[N][K][1][1]

。オーダーは、

2

次元累積和の前計算が、

1

回あたり

O(N^2)

で

O(N^2)

回なので、

O(N^4)

、DP の計算が、状態数が

O(N^4)

で遷移をそれぞれ

O(1)

で計算できるので、

O(N^4)

、合わせて、

O(N^4)

。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 2 次元配列を上書きして 2 次元累積和を生成
// (※与える v は、v[0][*] = 0, v[*][0] = 0 を満たすものとする (* は任意))
void cumulativeSum2(vector<vector<ll>> &v) {
    int h = v.size();
    int w = v[0].size();

    for (int i = 1; i < h; ++i) {
        for (int j = 2; j < w; ++j) {
            v[i][j] += v[i][j - 1];
        }
    }
    for (int i = 2; i < h; ++i) {
        for (int j = 1; j < w; ++j) {
            v[i][j] += v[i - 1][j];
        }
    }
}

int main() {
    int N, K, P;

    cin >> N >> K >> P;

    vector<vector<vector<vector<ll>>>> dp(N + 1);

    // n = 1 のとき
    dp[1] = vector<vector<vector<ll>>>(1, vector<vector<ll>>(N + 1, vector<ll>(N + 1)));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            dp[1][0][i][j] = 1;
        }
    }

    // dp を計算
    for (int n = 2; n <= N; ++n) {
        // 要素数 n のとき、類似度の範囲は、0 <= k <= n - 1
        // n 個目の要素として選べる要素数は、N - n + 1 個
        dp[n] = vector<vector<vector<ll>>>(n, vector<vector<ll>>(N - n + 2, vector<ll>(N - n + 2)));
        // すべての k について、dp[n - 1][k]を計算
        for (int k = 0; k < n - 1; ++k) {
            cumulativeSum2(dp[n - 1][k]);
        }
        // dp[n] の計算
        for (int k = 0; k < n; ++k) {
            for (int i = 1; i <= N - n + 1; ++i) {
                for (int j = 1; j <= N - n + 1; ++j) {
                    if (k > 0) {  // 類似度が 1 増えるパターン
                        dp[n][k][i][j] += dp[n - 1][k - 1][i][j];
                        dp[n][k][i][j] +=
                            dp[n - 1][k - 1][N - n + 2][N - n + 2] - dp[n - 1][k - 1][N - n + 2][j] -
                            dp[n - 1][k - 1][i][N - n + 2] + dp[n - 1][k - 1][i][j];
                    }
                    if (k < n - 1) {  // 類似度が変わらないパターン
                        dp[n][k][i][j] += dp[n - 1][k][i][N - n + 2] - dp[n - 1][k][i][j];
                        dp[n][k][i][j] += dp[n - 1][k][N - n + 2][j] - dp[n - 1][k][i][j];
                    }
                    dp[n][k][i][j] %= P;
                }
            }
        }
    }

    cout << dp[N][K][1][1];

    return 0;
}

Ex - Min + Sum

分割統治法… Ex 頻出？

2

つのうち小さいほうを選択すると

O(N)

を

O(\log N)

に落とせるみたいなの忘れがち。

公式解説の [

2

] の解き方で実装。

\min \{A_L, A_{L+1}, \cdots A_R\}

は、Sparse Table を用いて

O(1)

で求められる (ただし、構築に

O(N \log N)

かかる)。それ以外は公式解説のとおりなので、あとは、コードを載せときます。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// Sparse Table
template <typename T>
class SparseTable {
    const vector<T>& arr;
    const int sz;
    vector<vector<T>> table;

    void solve() {
        table[0].resize(sz);
        for (int i = 0; i < sz; ++i) table[0][i] = arr[i];
        for (int i = 1, tsz = table.size(); i < tsz; ++i) {
            int range = 1 << i, tisz = sz + 1 - range;
            table[i].resize(tisz);
            range >>= 1;
            for (int j = 0; j < tisz; ++j) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + range]);
            }
        }
    }
    T op(T a, T b) { return a < b ? a : b; }

   public:
    SparseTable(const vector<T>& arr) : arr(arr), sz(arr.size()), table(32 - __builtin_clz(sz)) {
        solve();
    }

    // 区間 [L, R) の最小値を取得
    T get(int L, int R) {
        int lg = 31 - __builtin_clz(R - L);
        return op(table[lg][L], table[lg][R - (1 << lg)]);
    }
};

// 分割統治法 (区間 [L, R))
ll solve(int l, int r, SparseTable<pair<ll, int>>& minA, vector<ll>& Sb, ll s) {
    // 要素が 0 個なら答えは 0
    if (r - l == 0) {
        return 0;
    }

    // MIN は区間 [l, r) の最小値、m はその添え字
    auto [MIN, m] = minA.get(l, r);
    ll ans = 0;

    // 区間 [l, m] の大きさが、区間 [m, r) 以下なら
    if (m - l < r - m) {
        // 区間 [l, m] を固定
        for (int i = l; i <= m; ++i) {
            // (累積和が右開区間なので) [m + 1, r] の範囲をにぶたん
            int ok = m, ng = r + 1;
            for (int mid = (ok + ng) / 2; abs(ok - ng) > 1;
                 mid = (ok + ng) / 2) {
                if (Sb[mid] - Sb[i] + MIN <= s)
                    ok = mid;
                else
                    ng = mid;
            }
            // (i, m), …, (i, ok - 1) が条件を満たす
            ans += ok - m;
        }
    } else {
        for (int i = m + 1; i <= r; ++i) {
            // (累積和が左閉区間なので) [l, m] の範囲をにぶたん
            int ok = m + 1, ng = l - 1;
            for (int mid = (ok + ng) / 2; abs(ok - ng) > 1;
                 mid = (ok + ng) / 2) {
                if (Sb[i] - Sb[mid] + MIN <= s)
                    ok = mid;
                else
                    ng = mid;
            }
            // (ok, i), …, (m, i) が条件を満たす
            ans += m - ng;
        }
    }

    // [l, m) と [m + 1, r) に分割して再帰
    ans += solve(l, m, minA, Sb, s);
    ans += solve(m + 1, r, minA, Sb, s);

    return ans;
}

int main() {
    int n;
    ll s;

    cin >> n >> s;

    // A も B も 0-indexed
    // 組 (A_i, i)
    vector<pair<ll, int>> a(n);
    // B の累積和 (区間 [l, r) の総和は Sb[r] - Sb[l])
    vector<ll> Sb(n + 1);
    for (int i = 0; i < n; ++i) cin >> a[i].first, a[i].second = i;
    for (int i = 1; i <= n; ++i) cin >> Sb[i];

    // Sparse Table を構築
    SparseTable<pair<ll, int>> minA(a);

    // 累積和を計算
    for (int i = 1; i <= n; ++i) Sb[i] += Sb[i - 1];

    cout << solve(0, n, minA, Sb, s);

    return 0;
}

Discussion

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

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？