Ccmmutty logo
Commutty IT
・14 min read

青色コーダーが ABC 全問解説する【ABC288】

AtCoder競技プログラミングAtCoderBeginnerContest
https://cdn.magicode.io/media/notebox/2e52ada5-0c99-4ca2-be46-93597cf0cc5f.jpeg

Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）

残り 12 秒で滑り込み 6 完！
というか 4 完の最低パフォ 1500 超、 5 完の最低パフォ 1900 超って何…。
と思ったら、

らしい (ここ)。

A - Many A+B Problems

int でもオーバーフローしないし、for で (Ai,Bi)(A_i,B_i) を受け取って、そのまま Ai+BiA_i+B_i 出力するだけ。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;

    for (int i = 0, a, b; i < n; ++i) {
        cin >> a >> b;
        cout << a + b << '\n';
    }

    return 0;
}

B - Qualification Contest

{S1,S2,⋯SK}\{S_1, S_2, \cdots S_K\} をソートして出力するだけ。
vector AA の、前から KK 個をソートしたいときは、
sort(A.begin(), A.begin() + K);
でできる。
AA が配列なら、
sort(A, A + K);
でできる。
vector でも、配列でも、
sort(&A[0], &A[K]);
にすることもできる。
今回の場合は、入力を KK 個だけ受け取って、普通にソートしても問題ない。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;

    cin >> n >> k;

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

    sort(s.begin(), s.end());

    for (int i = 0; i < k; ++i) cout << s[i] << '\n';

    return 0;
}

C - Don’t be cycle

「連結」かつ「閉路を持たない」グラフの辺の数は、頂点の数より 11 少ない。
なので、連結成分の個数を numnum とおくと、「閉路を持たない」グラフの辺の数は、頂点の数より numnum 少ないので、答えは、M−(N−num)M - (N - num) である。
連結成分の個数は、この問題を参考にすると求められる。(私の解説は、ここ。)
また、別解として、Union-Find を用いる方法がある。
まず、辺の張られていない NN 頂点のグラフ GG を考える。 ii ごとに、以下の操作を行う。
  • AiA_i と BiB_i が連結でないなら、GG に、辺 ii を追加する
  • そうでないなら、辺 ii を追加すると閉路ができてしまうので、何もしない
上記の操作を終えたあとの GG は閉路のないグラフとなり、追加しなかった辺の数が答えとなる。Union-Find を用いると、以下のように解ける。
ans=0ans=0 として、ii ごとに、Union-Find を用いて、以下の操作を行う。
  • AiA_i と BiB_i が違うグループなら、同じグループにする
  • そうでないなら、ansans を 11 加算する
上記の操作を終えたあとの ansans が答えとなる。
こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// 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 main() {
    int n, m;
    int ans = 0;

    cin >> n >> m;

    UnionFind uni(n);
    for (int i = 0, a, b; i < m; ++i) {
        cin >> a >> b;
        --a; --b;
        if (uni.isSame(a, b)) ++ans;
        else uni.unite(a, b);
    }

    cout << ans;

    return 0;
}

D - Range Add Query

今回のコンテストの難易度を跳ね上げた問題。一応、典型らしい。私は、K≤min⁡{10,N}K \leq \min\{10,N\} を何故か 10≤K≤N10 \leq K \leq N と勘違いして混乱してた…。
結論からいうと、答えは、
∑l≤i≤r,(i mod K)=0Ai=∑l≤i≤r,(i mod K)=1Ai=⋯=∑l≤i≤r,(i mod K)=K+1Ai\sum_{l \leq i \leq r, (i \bmod K) = 0} A_i = \sum_{l \leq i \leq r, (i \bmod K) = 1} A_i = \cdots = \sum_{l \leq i \leq r, (i \bmod K) = K + 1} A_i
なら Yes、違うなら No。累積和を前計算しておけば、各クエリ O(1)O(1) で求められる。
何故、上記の方法で答えを求められるかを考える。
操作は、以下のように、左端から順に要素を 00 にするような cc を足していけばいい。(以下の例は、入力例 22 の 33 クエリ目。)

このとき、操作は、KK で割った余りごとの和に対して、同じだけ影響を与えることがわかる。
そのため、KK で割った余りごとの和がすべて等しいか否かを判定すればいい。
この公式解説では、累積和に O(NK)O(NK) の大きさの配列をとっているが、O(N)O(N) の大きさでもできる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, k, q;

    cin >> n >> k;

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

    // k で割った余りごとの累積和
    for (int i = k; i <= n; ++i) a[i] += a[i - k];

    cin >> q;

    for (int query = 0, l, r; query < q; ++query) {
        cin >> l >> r;
        --l;
        // len は (r - i) - len <= l となるような最小の k の倍数
        int len = ((r - l) + k - 1) / k * k;
        ll sum = a[r] - a[max(0, r - len)];
        bool flag = true;
        for (int i = 1; i < k; ++i) {
            len = (((r - i) - l) + k - 1) / k * k;
            ll sum2 = a[r - i] - a[max(0, r - i - len)];
            if (sum != sum2) {
                flag = false;
                break;
            }
        }
        cout << (flag ? "Yes" : "No") << '\n';
    }

    return 0;
}

E - Wish List

商品 11 から商品 i−1i-1 までのうち kk 個購入するとき、商品 ii は、購入するときに定価に加える金額 CjC_j を i−k≤j≤ii-k \leq j \leq i を満たす任意の jj から選べる。
なので、dp[i][k]dp[i][k] を (商品 11 から商品 ii までのうち kk 個購入するときの合計費用の最小値) とおくと、
dp[i][k]={dp[i−1][k−1]+min⁡i−k≤j≤iCj+Ai(if    i∈{X1,⋯ ,XM})min⁡(dp[i−1][j],dp[i−1][k−1]+min⁡i−k≤j≤iCj+Ai)(otherwise)dp[i][k] = \begin{cases} dp[i-1][k-1]+\displaystyle\min_{i-k \leq j \leq i} C_j +A_i & (\text{if}\;\; i \in \{X_1, \cdots, X_M\}) \\ \min(dp[i-1][j], dp[i-1][k-1]+\displaystyle\min_{i-k \leq j \leq i} C_j +A_i) & (\text{otherwise}) \end{cases}
となる。区間 min\text{min} は、DP なら O(N2)O(N^2)、Sparse Table なら O(Nlog⁡N)O(N \log N) で前計算できるので、オーダーは、O(N2)O(N^2)。
答えは、min⁡M≤i≤Ndp[N][i]\displaystyle\min_{M \leq i \leq N} dp[N][i]。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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();
    }

    T get(int L, int R) {  // [L, R)
        int lg = 31 - __builtin_clz(R - L);
        return op(table[lg][L], table[lg][R - (1 << lg)]);
    }
};

int main() {
    int n, m;
    const ll INF = 1ll << 60;

    cin >> n >> m;

    vector<ll> a(n + 1), c(n + 1);
    c[0] = INF;
    vector<bool> need(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 0, x; i < n; ++i) cin >> x, need[x] = true;

    SparseTable sp(c);
    // 無理なら INF
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, INF));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + sp.get(i - j + 1, i + 1) + a[i]);
        }
        if (!need[i]) {
            for (int j = 0; j < i; ++j) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            }
        }
    }

    ll ans = INF;
    for (int i = m; i <= n; ++i) ans = min(ans, dp[n][i]);

    cout << ans;

    return 0;
}

F - Integer Division

XX の 上位 LL 桁目から RR 桁目までを R−L+1R-L+1 桁の正整数と見たときの値を X[L:R]X[L:R] とおく。
dp[i]dp[i] を X[1:i]X[1:i] の f(S)f(S) の総和とおいて、SS に含まれる数字のうち最大のものが jj である場合を考える。
SS に含まれる数字のうち最大のものが jj である SS を S′S' とおくと、X[1:i]X[1:i] の f(S′)f(S') の総和は、
dp[j]×X[j+1:i]dp[j] \times X[j+1:i]
である。また、S=ϕS=\phi の場合は、f(S)=X[1:i]f(S)=X[1:i] である。よって、dp[0]=0dp[0]=0 として、
dp[i]=X[1:i]+∑j=1i−1(dp[j]×X[j+1:i])dp[i] = X[1:i] + \sum_{j=1}^{i-1} (dp[j] \times X[j+1:i])
で遷移するとわかる。L>RL>R のとき、X[L:R]=0X[L:R] = 0 であることに注意すると、
∑j=1i−1(dp[j]×X[j+1:i])=∑j=1i−1{dp[j]×(X[j+1:i−1]×10+X[i:i])}=∑j=1i−2(dp[j]×X[j+1:i−1])×10+∑j=0i−1dp[j]×X[i:i]=(dp[i−1]−X[1:i−1])×10+∑j=0i−1dp[j]×X[i:i]\begin{align*} \sum_{j=1}^{i-1} (dp[j] \times X[j+1:i]) &= \sum_{j=1}^{i-1} \left\{ dp[j] \times (X[j+1:i-1] \times 10 + X[i:i]) \right\} \\ &= \sum_{j=1}^{i-2} (dp[j] \times X[j+1:i-1]) \times 10 + \sum_{j=0}^{i-1} dp[j] \times X[i:i] \\ &= (dp[i-1] - X[1:i-1]) \times 10 + \sum_{j=0}^{i-1} dp[j] \times X[i:i] \end{align*}
から
dp[i]=dp[i−1]×10+∑j=0i−1dp[j]×X[i,i]+X[1:i]−X[1:i−1]×10=dp[i−1]×10+∑j=0i−1dp[j]×X[i,i]+X[i:i]=dp[i−1]×10+(1+∑j=0i−1dp[j])×X[i,i]\begin{align*} dp[i] &= dp[i-1] \times 10 + \sum_{j=0}^{i-1} dp[j] \times X[i,i] + X[1:i] - X[1:i-1] \times 10 \\ &= dp[i-1] \times 10 + \sum_{j=0}^{i-1} dp[j] \times X[i,i] + X[i:i] \\ &= dp[i-1] \times 10 + \left( 1+\sum_{j=0}^{i-1} dp[j] \right) \times X[i,i] \end{align*}
∑j=0i−1dp[j]\displaystyle\sum_{j=0}^{i-1} dp[j] は、∑j=0i−2dp[j]\displaystyle\sum_{j=0}^{i-2} dp[j] から O(1)O(1) で求められるので、O(1)O(1) で遷移できる。よって、オーダーは O(N)O(N)。
↓ こんな感じ。
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
    int n;
    string x;

    cin >> n >> x;

    vector<mint> dp(n + 1);
    mint sum = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] * 10 + sum * (x[i - 1] - '0');
        sum += dp[i];
    }

    cout << dp[n].val();

    return 0;
}

G - 3^N Minesweeper

公式解説によれば、NN 次元累積和の考え方を応用すれば解けるらしい。
累積和は、Si=∑j≤iAjS_i=\sum_{j \leq i} A_j だから、
Ai=Si−Si−1A_i=S_i-S_{i-1}
で AiA_i を復元できるけど、今回の場合、{S0,S1,S2}={A0+A1,A0+A1+A2,A1+A2}\{S_0,S_1,S_2\} = \{A_0+A_1, A_0+A_1+A_2, A_1+A_2\} とした NN 次元和なので、各次元に対して、
{A0,A1,A2}={S1−S0,S0+S2−S1,S1−S2}\{A_0,A_1,A_2\}=\{S_1-S_0,S_0+S_2-S_1,S_1-S_2\}
で復元すればいいっぽい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;

    vector<int> pow3(n + 1);  // 3 の i 乗
    pow3[0] = 1;
    for (int i = 1; i <= n; ++i) pow3[i] = pow3[i - 1] * 3;
    vector<int> a(pow3[n]);
    for (int i = 0; i < pow3[n]; ++i) cin >> a[i];

    // dp[i] は a から i 次元分を復元したもの
    vector<vector<int>> dp(n + 1, vector<int>(pow3[n]));
    dp[0] = a;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < pow3[n - 1]; ++j) {
            int rem = j % pow3[i - 1], div = j / pow3[i - 1];
            // i 桁目 (1-indexed) に 0, 1, 2 を挿入
            int n0 = (div * 3 + 0) * pow3[i - 1] + rem;
            int n1 = (div * 3 + 1) * pow3[i - 1] + rem;
            int n2 = (div * 3 + 2) * pow3[i - 1] + rem;

            dp[i][n0] = dp[i - 1][n1] - dp[i - 1][n2];
            dp[i][n1] = dp[i - 1][n0] + dp[i - 1][n2] - dp[i - 1][n1];
            dp[i][n2] = dp[i - 1][n1] - dp[i - 1][n0];
        }
    }

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

    return 0;
}

Discussion

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