Ccmmutty logo
Commutty IT
・12 min read

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

AtCoder競技プログラミングAtCoderBeginnerContest
https://cdn.magicode.io/media/notebox/6a1ae48d-4f4c-4863-b7dd-a2377f6d171c.jpeg

AtCoder Beginner Contest 292

66 完。まあまあかな？

A - CAPS LOCK

小文字 cc を大文字へ変換するには、c += 'A' - 'a' をすれば OK。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;

    cin >> s;

    for (int i = 0; i < s.length(); ++i) s[i] += 'A' - 'a';

    cout << s;

    return 0;
}

B - Yellow and Red Card

レッドカードを、イエローカード 22 枚分に置き換えれば、イエローカードが 22 枚以上提示されたかどうかの判定問題に置き換わる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q, t, x;

    cin >> n >> q;

    vector<int> yellow(n);
    for (int i = 0; i < q; ++i) {
        cin >> t >> x;
        if (t == 3) cout << (yellow[x - 1] >= 2 ? "Yes" : "No") << '\n';
        else yellow[x - 1] += t;  // イエローカードなら t == 1、レッドカードなら t == 2 なので、
                                  // t を足すとちょうどいい
    }

    return 0;
}

C - Four Variables

cnt[i]=(αβ=icnt[i]=(\alpha\beta=i となる正整数の組 (α,β)(\alpha,\beta) の個数)) とおくと、
∑i=1N−1(cnt[i]⋅cnt[N−i])\sum_{i=1}^{N-1} (cnt[i] \cdot cnt[N-i])
が答えとなる。
cntcnt は、i=1,⋯ ,Ni=1,\cdots,N の順に、cnt[icnt[i の倍数]] に 11 ずつ加算していけば求まる。
オーダーは、エラトステネスのふるいなどと同じくらい。少なくとも O(Nlog⁡N)O(N \log N) 以下。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;

    cin >> n;

    vector<ll> sum(n + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            ++sum[j];
        }
    }

    ll ans = 0;
    for (int i = 1; i < n; ++i) ans += sum[i] * sum[n - i];

    cout << ans;

    return 0;
}

D - Unicyclic Components

連結成分を求めて、連結成分ごとに辺を数えるだけ。
連結成分は、DFS、BFS、Union-Find などで求められる。辺の数は、連結成分の各頂点の次数の総和の 1/21/2 と等しい (辺 11 つで、頂点 22 つの次数が 11 ずつ増えることに着目すればいい) ので簡単に求められる。
↓ こんな感じ。
#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 size(int x) { return -p[find(x)]; }
};

int main() {
    int n, m;

    cin >> n >> m;

    vector<vector<int>> g(n);
    UnionFind uni(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);
        uni.unite(u, v);
    }

    vector<int> p(n);     // p[i] は i を含む連結成分の代表
    vector<int> size(n);  // 代表が i である連結成分の頂点の個数
    vector<int> e(n);     // 代表が i である連結成分の各頂点の次数の総和
    for (int i = 0; i < n; ++i) {
        p[i] = uni.find(i);
        size[p[i]] = uni.size(p[i]);
        e[p[i]] += g[i].size();
    }

    bool ans = true;
    for (int i = 0; i < n; ++i) {
        if (size[i] * 2 != e[i]) {
            ans = false;
            break;
        }
    }

    cout << (ans ? "Yes" : "No");

    return 0;
}

E - Transitivity

条件をよくみると、「xx から yy への距離が 22 であるすべての組 (x,y)(x,y) に対して、xx から yy への辺を張る」ことを、距離が 22 である組がなくなるまで繰り返せばいいことがわかる。
距離が 33 以上であるパスには、距離が 22 のパスが含まれているため、距離が 22 である組がなくなるということは、距離が 22 以上であるすべての組がなくなる (距離が 11 になる) ということである。
つまり、距離が 22 以上である組すべてに辺を張る必要があるため、答えは、距離が 22 以上である組の個数に等しい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 頂点 v から各頂点への距離を求める
vector<int> bfs(int v, vector<vector<int>> &g) {
    queue<int> que;
    vector<int> d(g.size(), -1);
    que.push(v);
    d[v] = 0;
    while (!que.empty()) {
        int v = que.front();
        que.pop();

        for (int child : g[v]) {
            if (d[child] == -1) {
                d[child] = d[v] + 1;
                que.push(child);
            }
        }
    }

    return d;
}

int main() {
    int n, m;

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

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        auto d = bfs(i, g);
        for (int j = 0; j < n; ++j) {
            if (d[j] >= 2) ++ans;
        }
    }

    cout << ans;

    return 0;
}

F - Regular Triangle Inside a Rectangle

長方形の内部に描ける正三角形の頂点が長方形の辺上に 11 つ以下しかない場合、正三角形を拡大することで、辺上の頂点を 22 つ以上にできる。よって、辺の長さが最大の正三角形の頂点のうち 22 つは、長方形の辺上にある。
また、その辺上の頂点が、長方形の頂点と 11 つも頂点を共有していないとき、平行移動することで、正三角形の頂点と長方形の頂点を 11 つ共有させられる。そのため、正三角形の頂点のうち 11 点は、長方形の頂点のうちの 11 点と共有させても問題ない。
さらに、残りの 22 つの頂点のうち 11 つは、長方形の (共有している頂点と逆側の) 長辺上にある。なぜなら、22 点とも長方形の長辺上にない場合、正三角形を回転 & 拡大することで、長方形をはみ出さずに、11 点を長方形の長辺上に乗せられるからである。
あとは、残りの 11 点が長方形内に含まれる正三角形のうち、辺の長さが最大のものを、長辺上の頂点を二分探索で求めればいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    const double PI = 3.141592653589793;

    cin >> a >> b;

    if (a > b) swap(a, b);  // b を長辺とする

    double ok = 0, ng = b;
    for (double mid = (ok + ng) / 2; abs(ok - ng) > 1e-12; mid = (ok + ng) / 2) {
        // 長方形の頂点の座標を (0, 0), (a, 0), (a, b), (0, b) として、
        // 正三角形の頂点のうち、長方形の辺上の 2 点を (0, 0), (a, mid) としたときの
        // 残りの 1 点 (c, d)
        double c = a * cos(PI / 3) - mid * sin(PI / 3), d = mid * cos(PI / 3) + a * sin(PI / 3);
        if (0 <= c && c <= a && 0 <= d && d <= b) ok = mid;
        else ng = mid;
    }

    printf("%.16lf", sqrt(a * a + ok * ok));

    return 0;
}

G - Count Strictly Increasing Sequences

DP で O(N3Mb)O(N^3Mb) で解けるらしい (公式解説)。
dp[m][k][l][r]=(Sl%10m<⋯<Sr−1%10mdp[m][k][l][r]=(S_l \% 10^m < \cdots < S_{r-1} \% 10^m が成り立つ通り数 (Si(S_i の最上位の値は kk 未満)))) とおくと、
dp[m][k][l][r]=∑mid=lrdp[m][k−1][l][mid]⋅dp[m−1][b][mid][r]dp[m][k][l][r]=\sum_{mid=l}^r dp[m][k-1][l][mid] \cdot dp[m-1][b][mid][r]
とかになるのだと思われる。
↓ こんな感じ。
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
    int n, m;
    const int b = 10;

    cin >> n >> m;

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

    // dp[桁][l][r] ([l, r))
    vector<vector<vector<mint>>> dp(m + 1, vector<vector<mint>>(n, vector<mint>(n + 1)));
    for (int i = 0; i < n; ++i) dp[m][i][i + 1] = 1;  // 最下位対応用
    for (int i = m - 1; i >= 0; --i) {
        // dp2[上から i 桁目の値が k 未満][l][r]
        vector<vector<vector<mint>>> dp2(b + 1, vector<vector<mint>>(n, vector<mint>(n + 1)));
        for (int l = 0; l < n; ++l) {
            for (int k = 0; k <= b; ++k) dp2[k][l][l] = 1;  // mid == l 対応用
            for (int r = l + 1; r <= n; ++r) {
                for (int k = 1; k <= b; ++k) {
                    dp2[k][l][r] = dp2[k - 1][l][r];
                    for (int mid = r - 1; mid >= l; --mid) {
                        if (s[mid][i] != k - 1 + '0' && s[mid][i] != '?') break;
                        // [mid, r) の 上から i 桁目の値がすべて k - 1 の場合を加算
                        dp2[k][l][r] += dp2[k - 1][l][mid] * dp[i + 1][mid][r];
                    }
                }
                dp[i][l][r] = dp2[b][l][r];
            }
        }
    }

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

    return 0;
}

Ex - Rating Estimator

ユーザ解説を参考に、区間 add 区間 max の遅延セグ木を用いて、∑i=1n(Pi−B)\sum_{i=1}^n (P_i-B) を管理。00 以上となる最小の nn をにぶたん。
aia_i の 11 点更新 → 遅延セグ木の [c,N][c,N] を更新
↓ こんな感じ。
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using S = long long;
S op(S a, S b) { return max(a, b); }
S e() { return -(1e18); }

using F = long long;
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

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

    cin >> n >> b >> q;

    vector<S> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i], a[i] -= b;  // B を引いて
    for (int i = 1; i <= n; ++i) a[i] += a[i - 1];        // 累積和

    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);

    int c;
    double x;
    for (int i = 0; i < q; ++i) {
        cin >> c >> x;
        // 累積和なので seg.get(c) - seg.get(c - 1) == a_i - B
        seg.apply(c, n + 1, (x - b) - (seg.get(c) - seg.get(c - 1)));
        int r = min(n, seg.max_right(1, [](S x) { return x < 0; }));
        printf("%.16lf\n", (double)seg.get(r) / r + b);
    }

    return 0;
}

Discussion

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