【ABC375】AtCoder Beginner Contest 375【C++】

コンテスト名

パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 375）

コンテストURL

https://atcoder.jp/contests/abc375

開催日

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

---

A: Seats

解法

• 問題文通りに判定する

ABC375A.cpp

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

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

    int cnt = 0;
    for(int i=0; i<n-2; i++){
        if(s[i]=='#' && s[i+1]=='.' && s[i+2]=='#'){
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

B: Traveling Takahashi Problem

解法

• 最初と最後に原点 $(0, 0)$ を追加して、問題文通りに計算する

ABC375B.cpp

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

double dist(long long int a, long long int b, long long int c, long long int d){
    return sqrt((a-c)*(a-c) + (b-d)*(b-d));
}

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

    vector<int> X(n+2), Y(n+2);
    for(int i=1; i<=n; i++){
        cin >> X[i] >> Y[i];
    }

    double sum = 0;
    for(int i=0; i<n+1; i++){
        sum += dist(X[i], Y[i], X[i+1], Y[i+1]);
    }

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

    return 0;
}

C: Spiral Rotation

解法

• $(x,y) → (y,N+1−x) → (N+1−x,N+1−y) → (N+1−y,x) → (x,y)$ と 4 回周期で変化することに注意する
• 90 度回転をイメージする

ABC375C.cpp

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

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

    vector<vector<char>> A(n, vector<char>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> A[i][j];
        }
    }
    
    vector<vector<char>> B(n, vector<char>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int cnt = min({i+1, n-i, j+1, n-j});
            int x = i, y = j;
            for(int k=0; k<cnt%4; k++){
                int tmpx = y, tmpy = n - 1 - x;
                x = tmpx;
                y = tmpy;
            }
            B[x][y] = A[i][j];
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << B[i][j];
        }
        cout << '\n';
    }

    return 0;
}

D: ABA

解法

• 累積和
• vector<vector<int>> に各文字の出現回数の累積和を記録する
• 真ん中の文字 $S_j$ に対して、 $S_i = S_k$ である組み合わせの数を計算する

ABC375D.cpp

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

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

    int n = s.size();

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

    vector<vector<int>> V(10+26, vector<int>(n+1));
    for(int i=0; i<n; i++){
        V[s[i]-'A'][i+1] = 1;
    }

    for(int i=0; i<10+26; i++){
        for(int j=0; j<n; j++){
            V[i][j+1] += V[i][j];
        }
    }

    long long int cnt = 0;
    for(int j=1; j<n-1; j++){
        for(int i=0; i<10+26; i++){
            cnt += (long long int)(V[i][j]-V[i][0])*(V[i][n]-V[i][j+1]);
        }
    }

    cout << cnt << endl;

    return 0;
}