【ABC388】AtCoder Beginner Contest 388【C++】

コンテスト名

HHKBプログラミングコンテスト2025（AtCoder Beginner Contest 388）

コンテストURL

開催日

2025/01/11 21:00-22:40

---

A: ?UPC

解法

• 問題文通りに結合する

ABC388A.cpp

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

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

    cout << s[0] << "UPC" << endl;

    return 0;
}

B: Heavy Snake

解法

• 各 $k$ について、毎回、すべてのヘビの重さを計算して最大値を求める

ABC388B.cpp

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

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

    vector<int> T(n), L(n);
    for(int i=0; i<n; i++){
        cin >> T[i] >> L[i];
    }

    for(int i=1; i<=d; i++){
        vector<int> V(n);
        for(int j=0; j<n; j++){
            V[j] = T[j]*(L[j]+i);
        }
        cout << *max_element(V.begin(), V.end()) << '\n';
    }

    return 0;
}

C: Various Kagamimochi

解法

• 二分探索
• 各餅 $A$ に対して、 $a \times 2$ 以上の大きさの餅が、いくつあるかを求める

ABC388C.cpp

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

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

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    vector<int> B = A;
    long long int cnt = 0;
    for(int i=0; i<n; i++){
        int idx = lower_bound(B.begin(), B.end(), A[i]*2) - B.begin();
        cnt += (n - idx);
    }

    cout << cnt << endl;

    return 0;
}

D: Coming of Age Celebration

解法

• 各宇宙人 $i$ が石を渡すことができる範囲を考える

1. いもす法
2. 優先度付きキュー

ABC388D_1.cpp

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

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

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    vector<int> S(n);
    for(int i=0; i<n-1; i++){
        if(A[i]){
            S[i+1]++;

            if(A[i]<n-1-i){
                S[A[i]+i+1]--;
                A[i] = 0;
            }else{
                A[i] -= n - 1 - i;
            }

            S[i+1] += S[i];
            A[i+1] += S[i+1];
        }
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;

    return 0;
}

ABC388D_2.cpp

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

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

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    priority_queue<int, vector<int>, greater<int>> Q;
    for(int i=0; i<n; i++){
        A[i] += Q.size();
        int rest = min(A[i], n - 1 - i);
        A[i] -= rest;
        Q.push(i + rest);

        while(!Q.empty() && Q.top()<=i){
            Q.pop();
        }
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;

    return 0;
}

E: Simultaneous Kagamimochi

解法

• 答えを二分探索する
• 昇順にソートされているため、両端から $K$ 個を貪欲にとって組み合わせればよい

ABC388E.cpp

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

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

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    int low = -1, high = n/2+1;
    while(high-low>1){
        int mid = low + (high - low)/2;

        bool flag = true;
        for(int i=0; i<mid; i++){
            if(A[i]*2>A[n-mid+i]){
                flag = false;
                break;
            }
        }

        if(flag){
            low = mid;
        }else{
            high = mid;
        }
    }

    cout << low << endl;

    return 0;
}