【ABC418】AtCoder Beginner Contest 418【C++】

コンテスト名

AtCoder Beginner Contest 418

コンテストURL

https://atcoder.jp/contests/abc418

開催日

2025/08/09 21:00–22:40

---

A: I'm a teapot

解法

• $N-2$ 文字目、 $N-1$ 文字目、 $N$ 文字目について判定する

ABC418A.cpp

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

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

    if(n<3){
        cout << "No" << endl;
        return 0;
    }

    if(s[n-1]=='a' && s[n-2]=='e' && s[n-3]=='t'){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: You're a teapot

解法

• 部分文字列を全探索する

ABC418B.cpp

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

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

    int n = s.size();

    double maxv = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(!(s[i]=='t' && s[j]=='t')){
                continue;
            }

            double cnt = 0;
            for(int k=i+1; k<j; k++){
                if(s[k]=='t'){
                    cnt += 1;
                }
            }

            maxv = max(maxv, cnt/(j-i-1));
        }
    }

    printf("%.10f\n", maxv);

    return 0;
}

C: Flush

解法

• 累積和

ABC418C.cpp

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

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

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

    vector<long long int> V = S;
    for(int i=1000000-1; i>=0; i--){
        S[i] += S[i+1];
    }
    for(int i=0; i<1000000; i++){
        S[i+1] += S[i];
    }
    for(int i=0; i<=1000000; i++){
        S[i] -= n;
    }

    int b;
    while(q--){
        cin >> b;

        if(S[b-1]+1>S[1000000]){
            cout << -1 << '\n';
        }else{
            cout << S[b-1] + 1 << '\n';
        }
    }

    return 0;
}