AtCoder Beginner Contest 372

## [A - delete .](https://atcoder.jp/contests/abc372/tasks/abc372_a)

O(N)
下記の時だけ文字を表示します。

```
'.' != S[i]
```

```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();
    for(int i=0; i<n; i++){
        if(s[i] != '.') cout << s[i];
    }
    cout << endl;
    return 0;
} 
```

## [B - 3^A](https://atcoder.jp/contests/abc372/tasks/abc372_b)

O(N)
整数列a_nの 
M > ３^a_i
のa_iを求めます。
Mより低い３^a_iの最大値を求めます。
M = M - ３^a_i
を行い、Mが0になるまで続けます。

```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 sum(vector<int> A){
    int n = A.size();
    int ans = 0;
    rep(i, n) ans += A[i];
    return ans;
}

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

    vector<int> A;
    while(0<M){
        int a = 0;
        while(pow(3, a + 1) <= M) a++;
        A.push_back(a);
        M -= pow(3, a);   
    }

    cout << A.size() << endl;
    for(int i=0; i<A.size(); i++){
        cout << A[i];
        if(i+1<A.size()) cout << ' ';
        else cout << endl;
    }

    return 0;
} 
```

## [C - Count ABC Again](https://atcoder.jp/contests/abc372/tasks/abc372_c)

O(5 * Q)
1クエリ毎にNだけ探索するとTLEになります。
事前にABCの数cntを計測します。
クエリ毎に、

1. C[i]で書き換えて減るABCの数を計測
2. cntから減算
3. S[i]をC[i]に置き換える
4. C[i]で書き換えて増えるABCの数を計測
5. cntから加算
6. cntを出力します

このようにする事で、
「S[i]をC[i]に置き換える」をした文字の周辺の５文字を探索するだけで答えが求まります。

```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, Q;
    cin >> N >> Q;
    string S;
    cin >> S;

    int cnt = 0;
    for(int i=2; i<N; i++){
        if(S[i-2] == 'A' && S[i-1] == 'B' && S[i] == 'C') cnt++;
    }

    vector<int> X(Q);
    vector<char> C(Q);
    rep(i, Q){
        cin >> X[i] >> C[i];
        X[i]--;
    }

    rep(i, Q){
        for(int j=max(2, X[i]); j<min(X[i]+3, N); j++){
            if(S[j-2] == 'A' && S[j-1] == 'B' && S[j] == 'C') cnt--;
        } 
        S[X[i]] = C[i];
        for(int j=max(2, X[i]); j<min(X[i]+3, N); j++){
            if(S[j-2] == 'A' && S[j-1] == 'B' && S[j] == 'C') cnt++;
        }
        cout << cnt << endl; 
    }

    return 0;
}
```

## [D - Buildings](https://atcoder.jp/contests/abc372/tasks/abc372_d)

O(N)
H_iをi=0から順番に「ビルiとビルjの間にビルjより高いビルが存在しない。」を判定していくとTLEになります。
これはデータ構造と処理の手順を考える問題です。

スタックを使用して、
i=0からではなく、i=N-1から処理をしていくと、
「ビルiとビルjの間にビルjより高いビルが存在しない。」
をO(N)で判定できます。

```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<int> H(N);
    rep(i, N) cin >> H[i];

    stack<int> st;
    vector<int> ans(N);
    for(int i=N-1; i>=0; i--){
        ans[i] = st.size();
        while(!st.empty() && st.top() < H[i]) st.pop();
        st.push(H[i]);
    }
    
    for(int i=0; i<N; i++){
        cout << ans[i];
        if(i<N-1) cout << ' ';
        else cout << endl;
    }

    return 0;
} 
```