【ABC377】AtCoder Beginner Contest 377【C++】

コンテスト名

トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377)

コンテストURL

開催日

2024/10/26 21:00-22:40

---

A: Rearranging ABC

解法

• 文字列を昇順にソートして ABC と一致するか判定する

ABC377A.cpp

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

int main(){
    string s;
    cin >> s;
    
    sort(s.begin(), s.end());

    if(s=="ABC"){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Avoid Rook Attack

解法

• コマが一つも置かれていない列数と行数の積が求める答えである

ABC377B.cpp

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

int main(){
    vector<string> G(8);
    for(int i=0; i<8; i++){
        cin >> G[i];
    }

    int cnt1 = 0, cnt2 = 0;
    for(int i=0; i<8; i++){
        bool flag1 = true, flag2 = true;
        for(int j=0; j<8; j++){
            if(G[i][j]=='#'){
                flag1 = false;
            }
            if(G[j][i]=='#'){
                flag2 = false;
            }
        }
        if(flag1){
            cnt1++;
        }
        if(flag2){
            cnt2++;
        }
    }

    cout << cnt1 * cnt2 << endl;

    return 0;
}

C: Avoid Knight Attack

解法

• コマが置かれているマスとコマが移動できるマスを set<pair<int, int>> に記録する
• マス数 $N^2$ からコマが置かれているマスとコマが移動できるマスの合計を引いた数が求める答えである

ABC377C.cpp

#include <iostream>
#include <set>
#include <cmath>
using namespace std;

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

    set<pair<int, int>> S;
    int a, b;
    int cnt = 0;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        S.insert({a, b});

        for(int j=-2; j<=2; j++){
            for(int k=-2; k<=2; k++){
                if(j==0 || k==0 || abs(j)==abs(k)){
                    continue;
                }
                if(abs(j)==abs(k)){
                    continue;
                }
                if(a+j<1 || a+j>n || b+k<1 || b+k>n){
                    continue;
                }

                S.insert({a+j, b+k});
            }
        }
    }

    
    cout << n*n - S.size() << endl;

    return 0;
}

D: Many Segments 2

解法

• 区間の右端を固定して条件を満たす左端の個数を数える
• 各右端について、最も大きい左端を vector<int> に記録しておく

ABC377D.cpp

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

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

    vector<int> V(m+1);
    int l, r;
    for(int i=0; i<n; i++){
        cin >> l >> r;
        if(V[r]<l){
            V[r] = l;
        }
    }

    for(int i=1; i<=m; i++){
        if(V[i]<V[i-1]){
            V[i] = V[i-1];
        }
    }

    long long int cnt = 0;
    for(int i=1; i<=m; i++){
        cnt += i - V[i];
    }

    cout << cnt << endl;

    return 0;
}