AtCoder Beginner Contest 240（ABC240）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 240での成績：925位
パフォーマンス：1508相当
レーティング：1518→1517 (-1) :(#AtCoder #ABC240 https://t.co/8ikD3OSmtZ

— ボンド@競プロ (@bond_cmprog) February 20, 2022

A - Edge Checker

$ a + 1 = b $、もしくは $ a = 1 $ かつ $ b = 10 $ のときYes

提出コード

void solve(){
    int a, b;
    cin >> a >> b;
    if(a + 1 == b or (a == 1 and b == 10)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Count Distinct Integers

setで種類数を数える

提出コード

void solve(){
    int N;
    cin >> N;
    set<int> st;
    REP(i,N){
        int a;
        cin >> a;
        st.insert(a);
    }
    cout << st.size() << endl;
}

C - Jumping Takahashi

$ dp[i][j] := i $ 回目までに $ j $ にたどり着けるかどうかでDPをする

提出コード

void solve(){
    int N, X;
    cin >> N >> X;
    vector<int> dp(101010);
    dp[0] = 1;
    REP(i,N){
        int a, b;
        cin >> a >> b;
        vector<int> nxt(101010);
        REP(j,101010) if(dp[j]){
            if(j + a < 101010) nxt[j+a] = 1;
            if(j + b < 101010) nxt[j+b] = 1;
        }
        swap(dp, nxt);
    }
    cout << (dp[X] ? "Yes" : "No") << endl;
}

D - Strange Balls

stackでボールに書かれた総数とその並んでいる個数の情報を持ってシミュレートをする

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<pair<int, int>> v;
    int sum = 0;
    REP(i,N){
        if(v.empty()){
            v.emplace_back(A[i], 1);
            sum += 1;
        }
        else{
            if(v.back().first == A[i]){
                if(v.back().second + 1 >= A[i]){
                    sum -= v.back().second;
                    v.pop_back();
                }
                else{
                    v.back().second++;
                    sum++;
                }
            }
            else{
                v.emplace_back(A[i], 1);
                sum++;
            }
        }
        cout << sum << endl;
    }
}

E - Ranges on Tree

葉同士はお互いに独立になっているのでそれぞれ別の数字を割り当てる必要がある
それ以外の頂点では、部分木に含まれる葉に割り当てた数字のminとmaxを求めればいい

提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    REP(i,N-1){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<pair<int, int>> dp(N, {INF, 0});
    int leaf = 1;
    auto dfs = [&](auto && self, int v, int par=-1, int mi=INF, int ma=0) -> pair<int, int>{
        bool is_leaf = true;
        for(auto nv : g[v]){
            if(nv == par) continue;
            auto [a, b] = self(self, nv, v, mi, ma);
            chmin(dp[v].first, a);
            chmax(dp[v].second, b);
            is_leaf = false;
        }
        if(is_leaf){
            dp[v].first = leaf;
            dp[v].second = leaf;
            leaf++;
        }
        return dp[v];
    };
    dfs(dfs, 0);
    for(auto [a, b] : dp) cout << a << " " << b << endl;
}