【ABC415】AtCoder Beginner Contest 415【C++】

コンテスト名

日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）

コンテストURL

開催日

2025/07/19 21:00–22:40

---

A: Unsupported Type

解法

• set<int> に記録して判定する

ABC415A.cpp

#include <iostream>
#include <set>
using namespace std;

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

    set<int> S;
    int a;
    for(int i=0; i<n; i++){
        cin >> a;
        S.insert(a);
    }

    int x;
    cin >> x;
    if(S.count(x)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Pick Two

解法

• vector<int> に荷物が置かれている区間番号を記録する

ABC415B.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    string s;
    cin >> s;

    vector<int> V;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='#'){
            V.push_back(i+1);
        }
    }

    for(int i=0; i<V.size()-1; i+=2){
        cout << V[i] << ',' << V[i+1] << '\n';
    }

    return 0;
}

C: Mixture

解法

• メモ化再帰

ABC415C.cpp

#include <iostream>
#include <vector>
using namespace std;

int n;
string s;
vector<int> memo;

bool f(long long int sum, int num){
    if(num==n){
        return true;
    }

    if(memo[sum]!=-1){
        return memo[sum] == 1;
    }

    for(int i=0; i<n; i++){
        if(sum&(1LL<<i)){
            continue;
        }

        if(s[(sum|(1LL<<i))-1]=='1'){
            continue;
        }
        
        memo[sum] = 1;
        if(f((sum|(1LL<<i)), num+1)){
            return true;
        }
    }

    memo[sum] = 0;
    return false;
}

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

    while(t--){
        cin >> n;
        cin >> s;

        memo.assign((1LL<<n), -1);

        if(f(0, 0)){
            cout << "Yes" << '\n';
        }else{
            cout << "No" << '\n';
        }
    }

    return 0;
}

D: Get Many Stickers

解法

• $A_i - B_i$ の昇順にソートし、貪欲に繰り返す
• 同じ $A_i - B_i$ に対しては、一度に計算する

ABC415D.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

    vector<long long int> A(m), B(m);
    priority_queue<pair<long long int, long long int>, vector<pair<long long int, long long int>>, greater<pair<long long int, long long int>>> Q;
    for(int i=0; i<m; i++){
        cin >> A[i] >> B[i];
        Q.emplace(A[i]-B[i], A[i]);
    }

    long long int ans = 0;
    while(!Q.empty()){
        auto [c, a] = Q.top();

        if(a>n){
            Q.pop();
            continue;
        }

        long long int x = (n - a) / c + 1;
        n -= c * x;
        ans += x;
    }

    cout << ans << endl;

    return 0;
}