【ABC360】AtCoder Beginner Contest 360【C++】

コンテスト名

AtCoder Beginner Contest 360

コンテストURL

https://atcoder.jp/contests/abc360

開催日

2024/06/30 21:00-22:40

---

A: A Healthy Breakfast

解法

• R か M が来たら答えを出力してプログラムを終了する
  • R が先に来たら Yes を出力してプログラムを終了する
  • M が先に来たら No を出力してプログラムを終了する

ABC360A.cpp

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

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

    for(int i=0; i<s.size(); i++){
        if(s[i]=='M'){
            cout << "No" << endl;
            return 0;
        }else if(s[i]=='R'){
            cout << "Yes" << endl;
            return 0;
        }
    }
}

B: Vertical Reading

解法

• $w$ と $c$ を全探索する
• $\text{S} [i \times w + c] = \text{T} [i]$ がすべての $i$ について成り立つ $w$ と $c$ を全探索する

ABC360B.cpp

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

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

    for(int w=1; w<s.size(); w++){
        for(int c=1; c<=w; c++){
            bool flag = true;
            int i;
            for(i=0; i*w+c-1<s.size(); i++){
                if(i>=t.size()){
                    flag = false;
                    break;
                }
                if(s[i*w+c-1]!=t[i]){
                    flag = false;
                    break;
                }
            }

            if(flag && i==t.size()){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

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

C: Move It

解法

• 箱に入っている荷物のうち、最も重い荷物以外を移動させるのが最適である
• vector<vector<int>> で各箱に入っている荷物を管理する
• 各箱の荷物を重さの昇順にソートして、最も重い荷物以外の重さを加算する
• 荷物が入っていない箱の size() に注意する

ABC360C.cpp

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

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

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

    vector<vector<int>> B(n);
    for(int i=0; i<n; i++){
        B[A[i]].push_back(W[i]);
    }

    int sum = 0;
    for(int i=0; i<n; i++){
        if(B[i].size()>0){
            sort(B[i].begin(), B[i].end());
            for(int j=0; j<B[i].size()-1; j++){
                sum += B[i][j];
            }
        }
    }

    cout << sum << endl;
    return 0;
}

D: Ghost Ants

解法

• 二分探索
• 負の方向を向いている蟻 $A_{0i}$ とすれ違うのは、正の方向を向いている蟻のうち、蟻 $A_{0i}$ よりも負の方向にいて、蟻 $A_{0i}$ との距離が $2T$ 以下の蟻である
• 負の方向を向いている蟻 $A_{0i}$ と正の方向を向いている蟻 $A_{1j}$ がすれ違う条件は、 $X_i - 2T \leqq X_j < X_i$
• 条件を満たす蟻 $A_{1j}$ の数を各蟻 $A_{0i}$ について求める
• $- 2T$ によってオーバーフローすることがあるため、long long int にする必要があることに注意する

ABC360D.cpp

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

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

    string s;
    cin >> s;

    int x;
    vector<long long int> V0, V1;
    for(int i=0; i<n; i++){
        cin >> x;
        if(s[i]=='0'){
            V0.push_back(x);
        }else{
            V1.push_back(x);
        }
    }

    sort(V1.begin(), V1.end());
    long long int cnt = 0;
    for(int i=0; i<V0.size(); i++){
        cnt += upper_bound(V1.begin(), V1.end(), V0[i]) - lower_bound(V1.begin(), V1.end(), V0[i]-2*t);
    }

    cout << cnt << endl;
    return 0;
}