🔵

【ABC434】AtCoder Beginner Contest 434【C++】

に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

Ｓｋｙ株式会社プログラミングコンテスト2025（AtCoder Beginner Contest 434）

コンテストURL

https://atcoder.jp/contests/abc434

開催日

2025/11/29 21:00–22:40

A: Balloon Trip

解法

  • 最低の n を探索する
ABC434A.cpp
#include <iostream>
using namespace std;

int main(){
    int w, b;
    cin >> w >> b;

    w *= 1000;
    for(int i=0; ; i++){
        if(w<i*b){
            cout << i << endl;
            return 0;
        }
    }
}

B: Bird Watching

解法

  • 各種類について、大きさの合計と羽数を記録する
ABC434B.cpp
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    vector<double> V(m), B(m);
    int a;
    double b;
    for(int i=0; i<n; i++){
        cin >> a >> b;
        a--;
        V[a] += 1;
        B[a] += b;
    }

    for(int i=0; i<m; i++){
        printf("%.10f\n", B[i]/V[i]);
    }

    return 0;
}

C: Flapping Takahashi

解法

  • 条件を満たす飛行が可能かを順番に確認する
  • 時刻 t_{i} から t_{i+1} の間に到達できるのは、 高度 \min(1, l_i - (t_{i+1} - t_{i})) 以上 u_i + (t_{i+1} - t_{i}) 以下
ABC434C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

int main(){
    int t;
    cin >> t;

    while(t--){
        long long int n, h;
        cin >> n >> h;

        long long int t, l, u;
        vector<tuple<long long int, long long int, long long int>> V;
        V.emplace_back(0, h, h);
        for(long long int i=0; i<n; i++){
            cin >> t >> l >> u;

            V.emplace_back(t, l, u);
        }

        sort(V.begin(), V.end());
        bool flag = true;
        for(long long int i=0; i<n; i++){
            auto [a, b, c] = V[i];
            auto [d, e, f] = V[i+1];

            long long int low = max(1LL, b - (d - a));
            long long int high = c + (d - a);

            if(low>f || high<e){
                flag = false;
                break;
            }

            long long int nlow = low, nhigh = high;
            if(low<e){
                nlow = e;
            }
            if(high>f){
                nhigh = f;
            }
            V[i+1] = {d, nlow, nhigh};
        }

        if(flag){
            cout << "Yes" << '\n';
        }else{
            cout << "No" << '\n';
        }
    }

    return 0;
}

D: Clouds

解法

  • 2 次元のいもす法と累積和
    1. 2 次元いもす法で、各マスについて、覆っている雲の数を求める
    2. 雲を 1 つ取り除いたときにどの雲にも覆われなくなるマスは、もともとどの雲にも覆われていないマスか、ただ 1 つの雲に覆われているマス
    3. ただ 1 つの雲に覆われているマスを 1 、それ以外のマスを 0 として 2 次元累積和を求めておき、各雲 k だけに覆われているマスの数を計算できるようにする
ABC434D.cpp
#include <iostream>
#include <vector>
using namespace std;

int main(){
    const int NUM = 2000;

    int n;
    cin >> n;

    vector<vector<int>> G(NUM+1, vector<int>(NUM+1));
    int u, d, l, r;
    vector<int> U(n), D(n), L(n), R(n);
    for(int i=0; i<n; i++){
        cin >> U[i] >> D[i] >> L[i] >> R[i];
        U[i]--;
        D[i]--;
        L[i]--;
        R[i]--;

        G[U[i]][L[i]]++;
        G[U[i]][R[i]+1]--;
        G[D[i]+1][L[i]]--;
        G[D[i]+1][R[i]+1]++;
    }

    for(int i=0; i<NUM; i++){
        for(int j=0; j<NUM; j++){
            G[i][j+1] += G[i][j];
        }
    }
    for(int i=0; i<NUM; i++){
        for(int j=0; j<NUM; j++){
            G[j+1][i] += G[j][i];
        }
    }

    vector<vector<int>> G2(NUM+1, vector<int>(NUM+1));
    int cnt = 0;
    for(int i=0; i<NUM; i++){
        for(int j=0; j<NUM; j++){
            if(G[i][j]==0){
                cnt++;
            }
            if(G[i][j]==1){
                G2[i][j] = 1;
            }
        }
    }

    vector<vector<int>> S(NUM+1, vector<int>(NUM+1));
    for(int i=0; i<NUM; i++){
        for(int j=0; j<NUM; j++){
            S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + G2[i][j];
        }
    }

    for(int i=0; i<n; i++){
        cout << cnt + (S[D[i]+1][R[i]+1] - S[U[i]][R[i]+1] - S[D[i]+1][L[i]] + S[U[i]][L[i]]) << '\n';
    }

    return 0;
}

Discussion