20か月前公開・20か月前更新・0 pv・13 min read

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

競技プログラミングAtCoderAtCoderBeginnerContest

https://cdn.magicode.io/media/notebox/blob_zb2LLdM

AtCoder Beginner Contest 294

G 問題、間に合わなかった(´・ω・｀)

A - Filter

x % 2 == 0 で、

x

が偶数かどうか判定できる。あとは出力するだけ。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;

    for (int i = 0, a; i < n; ++i) {
        cin >> a;
        if (a % 2 == 0) cout << a << ' ';
    }

    return 0;
}

B - ASCII Art

A_{i,j}=0

なら、. を出力。それ以外なら、

A_{i,j}\;+

A

-\;1

を出力。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int h, w;

    cin >> h >> w;

    for (int i = 0, a; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> a;
            if (a == 0) cout << '.';
            else cout << char(a + 'A' - 1);
        }
        cout << '\n';
    }

    return 0;
}

C - Merge Sequences

A,B

がそれぞれ単調増加なので、

x=1,y=1

から順に、

$A_x<B_y$ なら、 $A_x=C_{x+y-1}$ として、 $x$ に $1$ 加算
$A_x>B_y$ なら、 $B_y=C_{x+y-1}$ として、 $y$ に $1$ 加算

すれば OK。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;

    cin >> n >> m;

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

    vector<int> ansA(n), ansB(m);
    for (int i = 1, x = 0, y = 0; i <= n + m; ++i) {
        if (x >= n) ansB[y++] = i;
        else if (y >= m) ansA[x++] = i;
        else if (a[x] < b[y]) ansA[x++] = i;
        else ansB[y++] = i;
    }

    for (int i = 0; i < n; ++i) cout << ansA[i] << ' ';
    cout << '\n';
    for (int i = 0; i < m; ++i) cout << ansB[i] << ' ';

    return 0;
}

D - Bank

各人

i

ごとに、受付に呼ばれているが受付に行っていないかどうかを保持すればいい。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q;

    cin >> n >> q;

    vector<bool> called(n);  // 受付に呼ばれているが受付に行っていないかどうか
    int num = 0;   // 呼ばれていない人のうち、最も小さい番号の人
    int call = 0;  // 受付に呼ばれているが受付に行っていない人のうち、最も小さい番号の人
    for (int i = 0, t, x; i < q; ++i) {
        cin >> t;
        if (t == 1) {
            called[num++] = true;
        } else if (t == 2) {
            cin >> x;
            called[x - 1] = false;
        } else if (t == 3) {
            while (!called[call]) ++call;  // 受付に行っているなら呼ばない
            cout << call + 1 << '\n';
        }
    }

    return 0;
}

E - 2xN Grid

下のように、赤線で区切った部分ごとにまとめてカウントするように実装すれば OK 。(図は、出力例

1

の図を加工。)

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    ll l;
    int n1, n2;

    cin >> l >> n1 >> n2;

    vector<pair<int, ll>> b1(n1), b2(n2);  // {色, 長さ}
    for (int i = 0; i < n1; ++i) cin >> b1[i].first >> b1[i].second;
    for (int i = 0; i < n2; ++i) cin >> b2[i].first >> b2[i].second;

    // 長さの累積和を取っておく
    for (int i = 1; i < n1; ++i) b1[i].second += b1[i - 1].second;
    for (int i = 1; i < n2; ++i) b2[i].second += b2[i - 1].second;

    ll prevLen = 0, ans = 0;
    for (int i1 = 0, i2 = 0; i1 < n1 && i2 < n2;) {
        ll len = min(b1[i1].second, b2[i2].second);

        if (b1[i1].first == b2[i2].first) ans += len - prevLen;

        if (b1[i1].second < b2[i2].second) ++i1;
        else if (b1[i1].second > b2[i2].second) ++i2;
        else ++i1, ++i2;

        prevLen = len;
    }

    cout << ans;

    return 0;
}

F - Sugar Water 2

X

\%

以上か未満かをにぶたんする方法を思いつけなかった(´・ω・｀)
ということで、公式解説の方法で実装しました。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 濃度が x 以上となる混ぜ方の個数を出力
ll solve(double x, vector<int> &a, vector<int> &b, vector<int> &c, vector<int> &d) {
    int n = a.size(), m = c.size();
    ll ret = 0;
    vector<double> ab(n), cd(m);

    for (int i = 0; i < n; ++i) ab[i] = b[i] * x / (1 - x) - a[i];
    for (int i = 0; i < m; ++i) cd[i] = d[i] * x / (1 - x) - c[i];

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

    for (int i = 0; i < m; ++i) {
        int ok = -1, ng = n;
        while (abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (cd[i] + ab[mid] <= 0) ok = mid;
            else ng = mid;
        }
        ret += ok + 1;
    }

    return ret;
}

int main() {
    int n, m;
    ll k;

    cin >> n >> m >> k;

    vector<int> a(n), b(n), c(m), d(m);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
    for (int i = 0; i < m; ++i) cin >> c[i] >> d[i];

    double ok = 0, ng = 1;
    while (abs(ok - ng) > 1e-11) {
        double mid = (ok + ng) / 2;
        if (solve(mid, a, b, c, d) >= k) ok = mid;
        else ng = mid;
    }

    printf("%.16lf", ok * 100);

    return 0;
}

G - Distance Queries on a Tree

2

頂点

u,v

の距離を

d(u,v)

とおくと、任意の頂点

x

を用いて、

\begin{align*} d(u,v)&=d(LCA(u,v),u)+d(LCA(u,v),v) \\ &=\{d(x,u)-d(x,LCA(u,v))\}+\{d(x,v)-d(x,LCA(u,v))\} \end{align*}

で表せるので DFS などで

x

からの距離を前計算しておけばいい。
LCA がボトルネックで、前計算

O(N \log N)

で、取得

O(1)

や、前計算

O(N)

で、取得

O(\log N)

で求められる。

また、更新も行いたいので、Euler Tour で木を配列に落とす。配列の

1

点更新、区間和取得は、BIT やセグ木で

O(Q \log N)

。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// BIT
template <typename T>  // 0-indexed
class BIT {
    int n;
    vector<T> data;

   public:
    BIT(int _n) : n(_n), data(n + 1, 0) {}
    BIT(vector<T> _data) : n(_data.size()), data(n + 1, 0) {
        for (int i = 1, p; i <= n; ++i) {
            data[i] += _data[i - 1];
            p = i + (i & -i);
            if (p <= n) data[p] += data[i];
        }
    }

    void add(int a, T w) {
        for (int i = ++a; i <= n; i += i & -i) data[i] += w;
    }

    T get(int a) { return sum(a, a + 1); }

    void set(int a, T w) { add(a, w - get(a)); }

    T sum(int a) {  // [0,a)
        T ret = 0;
        for (int i = a; i > 0; i -= i & -i) ret += data[i];
        return ret;
    }

    T sum(int l, int r) {  // [l,r)
        return sum(r) - sum(l);
    }
};

// LCA
class LCA {
    const vector<vector<int>> &g;
    int sz;
    vector<pair<int, int>> path;
    vector<int> appear;
    vector<vector<pair<int, int>>> table;

    void eulerTour(int r, int p, int d) {
        appear[r] = path.size();
        path.emplace_back(d, r);
        for (auto a : g[r]) {
            if (a != p) {
                eulerTour(a, r, d + 1);
                path.emplace_back(d, r);
            }
        }
    }

    void solve() {
        table[0].resize(sz);
        for (int i = 0; i < sz; ++i) table[0][i] = path[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] = min(table[i - 1][j], table[i - 1][j + range]);
            }
        }
    }

   public:
    LCA(const vector<vector<int>> &g) : g(g) {
        sz = 0;
        for (auto a : g) {
            sz += a.size();
        }
        appear.resize(g.size());
        sz = max(sz, 1);
        table.resize(32 - __builtin_clz(sz));
        eulerTour(0, -1, 0);
        solve();
    }

    pair<int, int> getLCAAll(int v1, int v2) {
        int L, R;
        if (appear[v1] > appear[v2]) swap(v1, v2);

        L = appear[v1];
        R = appear[v2] + 1;

        int lg = 31 - __builtin_clz(R - L);
        return min(table[lg][L], table[lg][R - (1 << lg)]);
    }

    int getLCA(int v1, int v2) { return getLCAAll(v1, v2).second; }

    int getLCADepth(int v1, int v2) {
        return getLCAAll(v1, v2).first;
    }

    int getDistance(int v1, int v2) {
        if (appear[v1] > appear[v2]) swap(v1, v2);
        return table[0][appear[v1]].first + table[0][appear[v2]].first -
               getLCAAll(v1, v2).first * 2;
    }

    int getFirstAppear(int v) { return appear[v]; }
};

void dfs(int v, int p, vector<vector<tuple<int, ll, int>>> &g, vector<int> &idx,
         vector<ll> &d, vector<tuple<int, int, ll>> &e) {
    static int cnt = 0;
    idx[v] = cnt;
    for (auto [a, w, num] : g[v]) {
        if (a != p) {
            e[num] = {cnt, 0, w};
            d[cnt] = w;
            ++cnt;

            dfs(a, v, g, idx, d, e);
            auto &[i, j, w] = e[num];
            d[cnt] = -w;
            
            ++cnt;
            j = cnt;
        }
    }

    return;
}

int main() {
    int n;

    cin >> n;

    vector<vector<tuple<int, ll, int>>> g(n);
    vector<vector<int>> g2(n);
    for (int i = 0, u, v, w; i < n - 1; ++i) {
        cin >> u >> v >> w;
        --u; --v;
        g[u].emplace_back(v, w, i); g[v].emplace_back(u, w, i);
        g2[u].emplace_back(v); g2[v].emplace_back(u);
    }

    vector<int> idx(n);   // Euler tour による頂点 i の index
    vector<ll> d(n * 2);  // 距離
    vector<tuple<int, int, ll>> e(n - 1);  // 辺
    dfs(0, -1, g, idx, d, e);

    BIT<ll> b(d);

    int q;

    cin >> q;

    LCA lca(g2);
    for (int i = 0, t, x, y; i < q; ++i) {
        cin >> t >> x >> y;
        if (t == 1) {
            auto &[u, v, w] = e[x - 1];
            b.add(u, y - w); b.add(v, w - y);
            w = y;
        } else if (t == 2) {
            int m = lca.getLCA(--x, --y);
            if (idx[x] > idx[y]) swap(x, y);
            cout << b.sum(idx[m], idx[x]) + b.sum(idx[m], idx[y]) << '\n';
        }
    }

    return 0;
}

Ex - K-Coloring

↓ こんな感じ。

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

AtCoder Beginner Contest 294

A - Filter

B - ASCII Art

C - Merge Sequences

D - Bank

E - 2xN Grid

F - Sugar Water 2

G - Distance Queries on a Tree

Ex - K-Coloring

Discussion

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