【ABC416】AtCoder Beginner Contest 416【C++】

コンテスト名

AtCoder Beginner Contest 416

コンテストURL

https://atcoder.jp/contests/abc416

開催日

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

---

A: Vacation Validation

解法

• 問題文通りに判定する

ABC416A.cpp

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

int main(){
    int n, l, r;
    cin >> n >> l >> r;
    l--;
    r--;
    string s;
    cin >> s;

    for(int i=l; i<=r; i++){
        if(s[i]=='x'){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    
    return 0;
}

B: 1D Akari

解法

• 新しく # があるたびに、o を一つ配置できる

ABC416B.cpp

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

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

    string t = s;
    bool flag = true;
    for(int i=0; i<t.size(); i++){
        if(t[i]=='#'){
            flag = true;
        }else{
            if(flag){
                t[i] = 'o';
                flag = false;
            }
        }
    }

    cout << t << endl;

    return 0;
}

C: Concat (X-th)

解法

• $N^k$ 個の文字列を再帰関数ですべて求めてから、昇順にソートする

ABC416C.cpp

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

int n, k, x;
vector<string> S;
vector<string> V;

void f(string t, int cnt){
    if(cnt==k){
        V.push_back(t);
        return;
    }

    for(int i=0; i<n; i++){
        f(t+S[i], cnt+1);
    }
}

int main(){
    cin >> n >> k >> x;
    x--;

    string s;
    for(int i=0; i<n; i++){
        cin >> s;
        S.push_back(s);
    }

    f("", 0);

    sort(V.begin(), V.end());

    cout << V[x] << endl;

    return 0;
}

D: Match, Mod, Minimize 2

解法

• $A_i + B_i \geqq M$ を満たす組み合わせの数の最大値 $C$ を求める
• 求める答えは $\min\left(\sum\limits_{i=1}^N \left(\left(A_i + B_i\right) \mod M\right)\right) = \sum\limits_{i=1}^N \left(A_i + B_i\right) - C \times M$

ABC416D.cpp

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

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

    while(t--){
        int n, m;
        cin >> n >> m;

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

        long long int cnt = 0;
        sort(A.rbegin(), A.rend());
        sort(B.begin(), B.end());
        int idx = 0;
        for(int i=0; i<n; i++){
            while(idx<n && A[i]+B[idx]<m){
                idx++;
            }

            if(idx>=n){
                break;
            }

            cnt++;
            idx++;
        }

        cout << sum - m * cnt << '\n';
    }

    return 0;
}