接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 385（ABC385）

AtCoder Beginner Contest 385（ABC385）

AtCoderBeginnerContest AtCoderBeginnerContest385 ABC ABC385

atcoder.jp

A - Equally

分け方を全通り試す

提出コード

void solve() {
    int A, B, C;
    cin >> A >> B >> C;
    if (A == B and B == C) {
        cout << "Yes" << endl;
    }
    else if (A + B == C or B + C == A or C + A == B) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

B - Santa Claus 1

シミュレーションする

提出コード

void solve() {
    int H, W, X, Y;
    cin >> H >> W >> X >> Y;
    --X, --Y;
    vector<string> S(H);
    REP(H) cin >> S[i];
    string T;
    cin >> T;
    vector<vector<int>> cnt(H, vector<int>(W, 0));
    for (auto c : T) {
        int dx = 0, dy = 0;
        if (c == 'U') dx = -1;
        if (c == 'D') dx = 1;
        if (c == 'L') dy = -1;
        if (c == 'R') dy = 1;
        if (0 <= X + dx and X + dx < H and 0 <= Y + dy and Y + dy < W and S[X + dx][Y + dy] != '#') {
            X += dx;
            Y += dy;
            if (S[X][Y] == '@') {
                cnt[X][Y]++;
                S[X][Y] = '.';
            }
        }
    }
    int ans = 0;
    REP(H) REP(j, W) ans += cnt[i][j];
    cout << X + 1 << " " << Y + 1 << " " << ans << endl;
}

C - Illuminate Buildings

$ dp[i][j] := i $ 番目まで見たときに、$ j $ 間隔で並んでいるときの最大としてDPをする

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> H(N);
    REP(N) cin >> H[i];
    vector<vector<int>> dp(N, vector<int>(N));
    REP(i, N) {
        REP(w, 0, N) {
            if (i - w < 0) chmax(dp[i][w], 1);
            else if (H[i] == H[i - w]) chmax(dp[i][w], dp[i - w][w] + 1);
            else chmax(dp[i][w], 1);
        }
    }

    int ans = 0;
    REP(i, N) REP(j, N) chmax(ans, dp[i][j]);
    cout << ans << endl;
}

D - Santa Claus 2

家の数のみを考えると頂点は高々 $ 2 \times 10^5 $ となり、訪れた頂点を適宜消していくことで全体でも最大で家の数しか走査する必要がない
各x, y軸ごとに存在する頂点をsetなどで管理することで全体で $ O(N \log N) $ で解くことができる

提出コード

void solve() {
    ll N, M, Sx, Sy;
    cin >> N >> M >> Sx >> Sy;

    vector<pair<ll, ll>> houses;
    map<ll, vector<ll>> x_map;
    map<ll, vector<ll>> y_map;

    REP(N) {
        ll Xi, Yi;
        cin >> Xi >> Yi;
        houses.push_back({Xi, Yi});
        x_map[Xi].push_back(Yi);
        y_map[Yi].push_back(Xi);
    }

    for (auto &[x, ys] : x_map) {
        sort(ys.begin(), ys.end());
    }
    for (auto &[y, xs] : y_map) {
        sort(xs.begin(), xs.end());
    }

    ll current_x = Sx;
    ll current_y = Sy;
    ll count = 0;

    REP(M) {
        string Di;
        ll Ci;
        cin >> Di >> Ci;

        if (Di == "U") {
            ll target_y = current_y + Ci;
            auto &ys = x_map[current_x];

            auto left = upper_bound(ys.begin(), ys.end(), current_y);
            auto right = upper_bound(ys.begin(), ys.end(), target_y);

            vector<ll> found_ys(left, right);
            count += found_ys.size();

            x_map[current_x].erase(left, right);
            for (ll y : found_ys) {
                auto &xs = y_map[y];
                auto it = lower_bound(xs.begin(), xs.end(), current_x);
                if (it != xs.end() && *it == current_x) {
                    xs.erase(it);
                    if (xs.empty()) {
                        y_map.erase(y);
                    }
                }
            }
            current_y = target_y;
        }
        else if (Di == "D") {
            ll target_y = current_y - Ci;
            auto &ys = x_map[current_x];

            auto left = lower_bound(ys.begin(), ys.end(), target_y);
            auto right = lower_bound(ys.begin(), ys.end(), current_y);

            vector<ll> found_ys(left, right);
            count += found_ys.size();

            x_map[current_x].erase(left, right);
            for (ll y : found_ys) {
                auto &xs = y_map[y];
                auto it = lower_bound(xs.begin(), xs.end(), current_x);
                if (it != xs.end() && *it == current_x) {
                    xs.erase(it);
                    if (xs.empty()) {
                        y_map.erase(y);
                    }
                }
            }
            current_y = target_y;
        }
        else if (Di == "R") {
            ll target_x = current_x + Ci;
            auto &xs = y_map[current_y];

            auto left = upper_bound(xs.begin(), xs.end(), current_x);
            auto right = upper_bound(xs.begin(), xs.end(), target_x);

            vector<ll> found_xs(left, right);
            count += found_xs.size();

            y_map[current_y].erase(left, right);
            for (ll x : found_xs) {
                auto &ys = x_map[x];
                auto it = lower_bound(ys.begin(), ys.end(), current_y);
                if (it != ys.end() && *it == current_y) {
                    ys.erase(it);
                    if (ys.empty()) {
                        x_map.erase(x);
                    }
                }
            }
            current_x = target_x;
        }
        else if (Di == "L") {
            ll target_x = current_x - Ci;
            auto &xs = y_map[current_y];

            auto left = lower_bound(xs.begin(), xs.end(), target_x);
            auto right = lower_bound(xs.begin(), xs.end(), current_x);

            vector<ll> found_xs(left, right);
            count += found_xs.size();

            y_map[current_y].erase(left, right);
            for (int x : found_xs) {
                auto &ys = x_map[x];
                auto it = lower_bound(ys.begin(), ys.end(), current_y);
                if (it != ys.end() && *it == current_y) {
                    ys.erase(it);
                    if (ys.empty()) {
                        x_map.erase(x);
                    }
                }
            }
            current_x = target_x;
        }
    }

    cout << current_x << " " << current_y << " " << count << endl;
}

E - Snowflake Tree

中心にする頂点 $ u $ と $ x $ を全探索する
予め頂点 $ u $ に隣接する頂点について次数の降順にソートしておくと、$ y = deg_{v_x} - 1 $ となるユ木を構築できるためその最小値を求めれば良い

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> deg(N);
    vector<vector<int>> G(N);
    REP(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        deg[a]++;
        deg[b]++;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ans = N;
    REP(i, N) {
        vector<int> idx(G[i].size());
        iota(ALL(idx), 0);
        sort(ALL(idx), [&](int a, int b) { return deg[G[i][a]] > deg[G[i][b]]; });
        int x = 0, y = 0;
        REP(x, 1, G[i].size() + 1) {
            int v = G[i][idx[x - 1]];
            int y = deg[v] - 1;
            chmin(ans, N - (1 + x + x * y));
        }
    }
    cout << ans << endl;
}

F - Visible Buildings

二分探索で最大値を求める
各判定問題は前から順に見たときに、条件を満たすためには各ビルを見るのに必要な角度が単調増加になっているかを判定すれば良い
long double だと精度が足りないため、 __float128 を使うと通る

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> X(N), H(N);
    REP(N) cin >> X[i] >> H[i];
    int ma = *max_element(ALL(H));
    auto check = [&](__float128 m) {
        __float128 ma = -1e18;
        REP(i, N) {
            __float128 S = ((__float128)H[i] - m) / (__float128)X[i];
            if (S > ma) {
                ma = S;
            }
            else return false;
        }
        return true;
    };
    if (check(0)) {
        cout << -1 << endl;
        return;
    }
    __float128 ng = 0, ok = 1e18;
    REP(i, 100) {
        __float128 mid = (ok + ng) / 2;
        if (check(mid)) ok = mid;
        else ng = mid;
    }
    cout << setprecision(20) << (long double)ok << endl;
}