AtCoder Beginner Contest 375

## [A - Seats](https://atcoder.jp/contests/abc375/tasks/abc375_a)

O(1)
シミュレートしましょう。
「座席i,i+2には人が座っており、座席i+1には人が座っていない」は、
```
if(S[i] == '#' && S[i+1] == '.' && S[i+2] == '#'){
```
と条件式を組むことができます。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    int ans = 0;
    for(int i=0; i<N-2; i++){
        if(S[i] == '#' && S[i+1] == '.' && S[i+2] == '#'){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
} 
```

## [B - Traveling Takahashi Problem](https://atcoder.jp/contests/abc375/tasks/abc375_b)

O(N)
2点間の距離を求める問題です。
2点間の距離は、
```math
dist = \sqrt{(x2 - x1) ^ 2 + (y2 - y1) ^ 2}\
```
プログラムでは、
```C++:C++
auto dist = [](const pair<double, double>& p1, const pair<double, double>& p2) -> double {
    return sqrt((p2.first - p1.first) * (p2.first - p1.first) + (p2.second - p1.second) * (p2.second - p1.second));
};
```
コーディングできます。
```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<pair<double, double>> P(N+2, {0.0, 0.0});
    rep(i, N) cin >> P[i+1].first >> P[i+1].second;

    double ans = 0.0;
    for(int i=1; i<N+2; i++){
        auto dist = [](const pair<double, double>& p1, const pair<double, double>& p2) -> double {
            return sqrt((p2.first - p1.first) * (p2.first - p1.first) + (p2.second - p1.second) * (p2.second - p1.second));
        };
        ans += dist(P[i], P[i-1]);
    }
    cout << fixed << setprecision(6) << ans << endl;
    
    return 0;
} 
```

## [C - Spiral Rotation](https://atcoder.jp/contests/abc375/tasks/abc375_c)

O(N^2)
２次元配列の要素を回転させる問題です。
一番の外側のマスから順に右側へ90度ずつ回転させる問題です。
シミュレートを行うと計算量はO(N^3)になりTLEとなります。

```
.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########
```
この図形の回転の規則性は、
1. 外側から1番目のマスは90度
2. 外側から2番目のマスは180度
3. 外側から3番目のマスは270度 
4. 外側から4番目のマスは360度
5. 外側から5番目のマスは450度
6. 外側から6番目のマスは540度
7. 外側から7番目のマスは630度 
8. 外側から8番目のマスは720度  

90度の回転なので4回転毎に周期性があります。
外側からN番目のマスか判定をして、0~360度の回転までの処理を作成すると実装できそうです。
0~360度の回転までの処理は、プログラムで実行し確認しましょう。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<string> A(N), B(N, string(N, ' '));
    rep(i, N) cin >> A[i];

    rep(y, N){
        rep(x, N){
            // 全パターンを実行確認する
            B[x][y] = A[x][y]; 
            //B[N - x - 1][y] = A[x][y]; 
            //B[x][N - y - 1] = A[x][y]; 
            //B[N - x - 1][N - y - 1] = A[x][y]; 
            //B[y][x] = A[x][y]; 
            //B[N - y - 1][x] = A[x][y];
            //B[y][N - x - 1] = A[x][y];
            //B[N - y - 1][N - x - 1] = A[x][y];
        }
    }

    rep(y, N){
        cout << B[y] << endl;
    }

    return 0;
} 
```

このコードから

```C++:C++
B[y][N - x - 1] = A[x][y]; // 90
B[N - x - 1][N - y - 1] = A[x][y]; // 180
B[N - y - 1][x] = A[x][y]; // 270
B[x][y] = A[x][y]; // 360
```

と分かります。
外側からN番目のマスは、x, y, N - x - 1, N - y - 1の４つの中で最小の値になります。

```C++:C++
min(min(x, y), min(N - x - 1, N - y - 1));
```

実装しましょう。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<string> A(N), B(N, string(N, ' '));
    rep(i, N) cin >> A[i];

    rep(y, N){
        rep(x, N){
            int i = min(min(x, y), min(N - x - 1, N - y - 1));
            if(i%4==0) B[y][N - x - 1] = A[x][y]; // 90
            if(i%4==1) B[N - x - 1][N - y - 1] = A[x][y]; // 180
            if(i%4==2) B[N - y - 1][x] = A[x][y]; // 270
            if(i%4==3) B[x][y] = A[x][y]; // 360
        }
    }

    rep(y, N){
        cout << B[y] << endl;
    }

    return 0;
} 
```

## [D - ABA](https://atcoder.jp/contests/abc375/tasks/abc375_d)

O(N)
3重ループで全探索するとO(N^3)でTLEになります。

この問題は回文、組み合わせ、累積和の問題です。
まず問題文から回文の条件を比較して読みといていきます。
回文の条件は、S_jを固定した時、

```math
\ S_i == S_k \
```

の時に回文となります。
サンプル１の「ABCACC」で考察します。
3番目のCをS_jとします。
i < jの各アルファベットの数は、

```
Aが1個
Bが1個
Cが1個
```

j < kの各アルファベットの数を

```
Aが1個
Bが0個
Cが2個
```

回文となる組み合わせは、

```
A = 1 * 1 = 1
B = 1 * 0 = 0
C = 1 * 2 = 2
```

となります。
Jを固定した時の回文の個数を求めることができました。
ここまで考察すると、
i < jの各アルファベットの数、j < kの各アルファベットの数は、累積和で求めることができると分かります。
実装してみましょう。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string S;
    cin >> S;
    int N = S.size();
    vector<vector<int>> total(N+1, vector<int>(26, 0));
    rep(i, N) total[i+1][S[i] - 'A']++;
    rep(i, N){
        rep(j, 26) total[i+1][j] = total[i+1][j] + total[i][j];
    }

    ll ans = 0;
    repx(i, 1, N){
        rep(j, 26){
            ll l = total[i][j] - total[0][j];
            ll r = total[N][j] - total[i][j];
            if(S[i] - 'A' == j) r--;
            ans += l * r;
        }
    }
    cout << ans << endl;
    
    return 0;
}
```