AtCoder Beginner Contest 183 に参加しました

全完！嬉しくなっちゃったので書きます。

成績

Highest！！！！！！サイコーーーーーー

A - ReLU

問題：（リンク）
定義通りに書く。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x;
    cin >> x;
    if (x >= 0)
        cout << x << '\n';
    else
        cout << 0 << '\n';
}

B - Billiards

問題：（リンク）
相似なつかし〜〜。 を に内分する点が答え。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    double sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    cout << fixed << setprecision(10) << (sx * gy + gx * sy) / (sy + gy)
         << '\n';
}

C - Travel

問題：（リンク）
の順列を全部試せばOK。最後スタートに戻ってくるん見落として少しモタモタしてもうた。巡回セールスマンあるある

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<vector<ll>> t(n, vector<ll>(n));
    rep(i, n) rep(j, n) cin >> t[i][j];
    vector<int> p;
    rep(i, n - 1) p.push_back(i + 1);
    int ans = 0;
    do {
        ll now = 0;
        int x = 0;
        rep(i, n - 1) {
            now += t[x][p[i]];
            x = p[i];
        }
        now += t[x][0];
        ans += (now == k);
    } while (next_permutation(p.begin(), p.end()));
    cout << ans << '\n';
}

D - Water Heater

問題：（リンク）
「区間 に 加算」という操作を 回行えば、各時刻について合計で何リットルのお湯が使われるかが求められる。いもす法。使われるお湯が より多い時刻があれば No。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main() {
    int n;
    ll w;
    cin >> n >> w;
    vector<ll> v(200200);
    rep(i, n) {
        int s, t;
        ll p;
        cin >> s >> t >> p;
        v[s] += p;
        v[t] -= p;
    }
    rep(i, 200200 - 1) v[i + 1] += v[i];
    if (*max_element(v.begin(), v.end()) <= w)
        cout << "Yes\n";
    else
        cout << "No\n";
}

E - Queen on Grid

問題：（リンク）
DP。愚直にやると遷移が忙しすぎるので、縦横斜めの累積和を持っておいて一気に更新。
いやめっっちゃ時間つかってもうた！！！「愚直DPはキツいな→累積和」までがまず遅かったし、焦ってもうて実装もミスしまくりやった……。落ち着いていこ〜〜〜

コードを表示

#include <bits/stdc++.h>
#include <atcoder/modint>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using mint = atcoder::modint1000000007;
int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    vector<vector<mint>> l(h, vector<mint>(w));
    vector<vector<mint>> u(h, vector<mint>(w));
    vector<vector<mint>> lu(h, vector<mint>(w));
    vector<vector<mint>> dp(h, vector<mint>(w));
    dp[0][0] = 1;
    rep(i, h) rep(j, w) {
        if (s[i][j] == '#') {
            l[i][j] = u[i][j] = lu[i][j] = 0;
            continue;
        }

        if (i - 1 >= 0) dp[i][j] += u[i - 1][j];
        if (j - 1 >= 0) dp[i][j] += l[i][j - 1];
        if (i - 1 >= 0 && j - 1 >= 0) dp[i][j] += lu[i - 1][j - 1];

        if (i - 1 >= 0)
            u[i][j] = u[i - 1][j] + dp[i][j];
        else
            u[i][j] = dp[i][j];

        if (j - 1 >= 0)
            l[i][j] = l[i][j - 1] + dp[i][j];
        else
            l[i][j] = dp[i][j];

        if (i - 1 >= 0 && j - 1 >= 0)
            lu[i][j] = lu[i - 1][j - 1] + dp[i][j];
        else
            lu[i][j] = dp[i][j];
    }
    cout << dp[h - 1][w - 1].val() << '\n';
}

F - Confluence

問題：（リンク）
少子化
もし生徒全員が同じクラスだったら UnionFind （ACLでいうDSU）一発で解けるのになあ〜〜〜という気持ちを起点に考えた。UnionFind が高速なのは所謂「マージテク」のおかげで、ということはクラスの情報も同じようにマージしていけばいい感じになりそう？→なりました　AC

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
struct UnionFind {
    vector<int> data;
    vector<map<int, int>> mp;
    UnionFind(int size, vector<map<int, int>> _mp) : data(size, -1), mp(_mp) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
            for (auto [key, num] : mp[y]) {
                mp[x][key] += num;
            }
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
int main() {
    int n, q;
    cin >> n >> q;
    vector<map<int, int>> mp(n);
    rep(i, n) {
        int c;
        cin >> c;
        mp[i][c] = 1;
    }
    UnionFind uf(n, mp);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            uf.unite(a, b);
        }
        if (t == 2) {
            int x, y;
            cin >> x >> y;
            x--;
            cout << uf.mp[uf.root(x)][y] << '\n';
        }
    }
}

完