【ABC379】AtCoder Beginner Contest 379【C++】

コンテスト名

トヨタ自動車プログラミングコンテスト2024#11（AtCoder Beginner Contest 379）

コンテストURL

https://atcoder.jp/contests/abc379

開催日

2024/11/09

---

A: Cyclic

解法

• 問題文通りに $N$ を $a, b, c$ に分けて計算してから出力する

ABC379A.cpp

#include <iostream>
using namespace std;

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

    int a = n/100, b = (n/10)%10, c = n%10;

    cout << b*100+c*10+a << " " << c*100+a*10+b << endl;

    return 0;
}

B: Strawberries

解法

• 問題文通りに左からシミュレーションする

ABC379B.cpp

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

int main(){
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int o = 0, cnt = 0;
    for(int i=0; i<n; i++){
        if(s[i]=='O'){
            o++;
        }else{
            o = 0;
        }

        if(o==k){
            cnt++;
            o = 0;
        }
    }

    cout << cnt << endl;

    return 0;
}

C: Sowing Stones

解法

• $X_i$ の昇順にソートする
• 累積和を求めて各地点で石が足りているかを判定する
• 石が $N$ 個ちょうどであるかを判定する
• $N$ 個の石すべてがマス $1$ にある場合の操作回数 $\frac{N(N+1)}{2}$ から $\sum\limits_{i=1}^M X_i \times A_i$ だけ省略できる

ABC379C.cpp

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

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

    vector<long long int> X(m), A(m);
    for(int i=0; i<m; i++){
        cin >> X[i];
    }
    for(int i=0; i<m; i++){
        cin >> A[i];
    }

    vector<pair<long long int, long long int>> XA;
    for(int i=0; i<m; i++){
        XA.emplace_back(X[i], A[i]);
    }
    sort(XA.begin(), XA.end());
    for(int i=0; i<m; i++){
        auto [x, a] = XA[i];
        X[i] = x;
        A[i] = a;
    }

    if(X[0]!=1){
        cout << -1 << endl;
        return 0;
    }

    vector<long long int> S(m+1);
    for(int i=0; i<m; i++){
        S[i+1] += S[i] + A[i];
    }

    if(S[m]!=n){
        cout << -1 << endl;
        return 0;
    }

    for(int i=0; i<m-1; i++){
        if(S[i+1]<X[i+1]-1){
            cout << -1 << endl;
            return 0;
        }
    }

    long long int cnt = (long long int)n*(n+1)/2;
    for(int i=0; i<m; i++){
        cnt -= X[i]*A[i];
    }

    cout << cnt << endl;

    return 0;
}

D: Home Garde

解法

• キュー
• queue<long long int> で各植物の植えられた日付を記録する
• 現在の日付を記録しておき、植えられた日付との差（植物の高さ）と $H$ の大小関係で収穫するかを判定する

ABC379D.cpp

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

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

    int num, t, h;
    long long int daycnt = 0;
    queue<long long int> Q;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            Q.push(daycnt);
        }else if(num==2){
            cin >> t;
            daycnt += t;
        }else{
            cin >> h;
            int cnt = 0;
            while(!Q.empty() && daycnt-Q.front()>=h){
                cnt++;
                Q.pop();
            }
            cout << cnt <<'\n';
        }
    }

    return 0;
}