AtCoder Beginner Contest 434 【ABC 434】 A ~ E

AtCoder Beginner Contest 434に参加しました。
パフォーマンス 1933
レーティング 1156 → 1262 (+106)
となり、入水することができました！

A - Balloon Trip

問題文より $1000W < nB$ が必要です。両辺とも整数より、$1000W + 1 \leq nB$
これは、 $n \geq \frac{1000W + 1}{B} \Leftrightarrow n \geq \lceil \frac{1000W + 1}{B} \rceil$ と同値です。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int W, B;
    cin >> W >> B;
    cout << (1000 * W + B) / B << endl;
}

B - Bird Watching

問題文の通りに実装するだけです。

cpp

#include <bits/stdc++.h>
using namespace std;
#define SUM(v) accumulate((v).begin(), (v).end(), 0) 

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> bird(M);
    for (int i = 0; i < N; i++) {
        int A, B;
        cin >> A >> B;
        A--;
        bird[A].push_back(B);
    } 

    cout << setprecision(15);
    for (int k = 0; k < M; k++) {
        cout << double(SUM(bird[k])) / double(bird[k].size()) << endl;
    } 
}

C - Flapping Takahashi

$t_0 = 0$, $x \leq f(t_i) \leq y$ を満たすとします。また、 $f(t_0) = H$ です。
このとき、$d = t_{i + 1} - t_i$ とすると、　高橋君は $-d$ から $d$ まで動くことができるので、
$x - d\leq f(t_{i + 1}) \leq y + d$ となります。 $l_{i + 1} \leq f(t_{i + 1}) \leq u_{i + 1}$と合わせて、
$\max(x - d, l_{i + 1}) \leq f(t_{i + 1}) \leq \min(x + d, u_{i + 1})$ となるので、高橋君の高度の取り得る範囲が分かります。

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll N, H;
    cin >> N >> H;
    ll MIN = H, MAX = H, pre = 0;
    bool ans = true;
    for (int i = 0; i < N; i++) {
        ll t, l, r;
        cin >> t >> l >> r;
        MIN = max(l, MIN - (t - pre));
        MAX = min(r, MAX + (t - pre));
        pre = t;
        if (r < MIN || MAX < l) {
            ans = false;
        }
    }

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

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}

D - Clouds

雲 $k$ を一つ取り除いたとき、雲 $k$ にしか覆われてなかったマスの個数だけ、どの雲にも覆われていないマスは増えます。二次元imosを使うことによって、各マスが何個の雲で覆われているか高速に求まります。各クエリには、二次元累積和を用いると $O(1)$ で答えられるので、この問題を解くことができます。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> U(N), D(N), L(N), R(N);
    vector<vector<int>> imos(2001, vector<int>(2001)), S(2001, vector<int>(2001));
    for (int i = 0; i < N; i++) {
        cin >> U[i] >> D[i] >> L[i] >> R[i];
        U[i]--, L[i]--;
        imos[U[i]][L[i]]++;
        imos[U[i]][R[i]]--;
        imos[D[i]][L[i]]--;
        imos[D[i]][R[i]]++;
    }

    for (int i = 0; i < 2000; i++) for (int j = 1; j < 2000; j++) imos[i][j] += imos[i][j - 1];
    for (int j = 0; j < 2000; j++) for (int i = 1; i < 2000; i++) imos[i][j] += imos[i - 1][j]; 
    for (int i = 0; i < 2000; i++) for (int j = 0; j < 2000; j++) S[i + 1][j + 1] += S[i + 1][j] + S[i][j + 1] - S[i][j] + (imos[i][j] == 1 ? 1 : 0);

    int ans = 0;
    for (int i = 0; i < 2000; i++) for (int j = 0; j < 2000; j++) if (imos[i][j] == 0) ans++;
    for (int i = 0; i < N; i++) {
        int x = S[D[i]][R[i]] - S[U[i]][R[i]] - S[D[i]][L[i]] + S[U[i]][L[i]];
        cout << ans + x << endl;
    }
}

E - Clouds

各 $i$ について $x - r, x + r$ を辺で結んだグラフを考えます。
連結成分内で考えると、連結成分内の頂点の個数と辺の個数のうち小さいほうが種類数の最大値になります。
これを足し合わせれば答えとなります。

cpp

#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end())


struct UnionFind {
    vector<int> par, siz, edge;
    
    UnionFind(int n) : par(n), siz(n, 1), edge(n, 0) {
        for (int i = 0; i < n; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    void merge(int u, int v) {
        int x = root(u);
        int y = root(v);
        if (x == y) {
            edge[x]++;
            return;
        }
        if (siz[x] < siz[y]) swap(x, y);

        siz[x] += siz[y];
        edge[x] += edge[y] + 1;
        par[y] = x;
    }

    bool same(int u, int v) {
        return root(u) == root(v);
    } 

    int size(int x) {
        return siz[root(x)];
    }

    vector<vector<int>> groups() {
        vector<vector<int>> member(int(par.size())), res;
        for (int i = 0; i < int(par.size()); i++) member[root(i)].push_back(i);
        for (int i = 0; i < int(par.size()); i++) if (!member[i].empty()) res.push_back(member[i]);
        return res;
    }
};


int main() {
    int N;
    cin >> N;
    vector<int> a(N), b(N), c;
    for (int i = 0; i < N; i++) {
        int x, r;
        cin >> x >> r;
        a[i] = x - r;
        b[i] = x + r;
        c.push_back(a[i]);
        c.push_back(b[i]);
    }

    sort(all(c));
    UNIQUE(c);
    int M = c.size();
    UnionFind uf(M);
    for (int i = 0; i < N; i++) {
        int x = lower_bound(all(c), a[i]) - c.begin();
        int y = lower_bound(all(c), b[i]) - c.begin();
        uf.merge(x, y);
    }

    set<int> seen;
    int ans = 0;
    for (int i = 0; i < M; i++) {
        int r = uf.root(i);
        if (seen.count(r)) continue;
        seen.insert(r);
        ans += min(uf.edge[r], uf.size(r));
    }

    cout << ans << endl;
}