AtCoder Beginner Contest 394

## [A - 22222](https://atcoder.jp/contests/abc394/tasks/abc394_a)

O(N)
s[i]が`2`の時だけ、ansの末尾に`2`を追加しましょう。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    string ans;
    rep(i, s.size()){
        if(s[i] == '2') ans += s[i];
    }
    cout << ans << endl;
    return 0;
} 
```

## [B - cat](https://atcoder.jp/contests/abc394/tasks/abc394_b)

O(logN)
文字列を長さの昇順に並べ替えます。
比較関数を自作するか、長さと文字列のpairのデータを用意してソートしましょう。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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<int, string>> S(N);
    rep(i, N){
        string s;
        cin >> s;
        S[i] = {s.size(), s};
    } 
    
    sort(S.begin(), S.end());

    rep(i, N){
        cout << S[i].second;
    }
    cout << endl;

    return 0;
} 
```

## [C - Debug](https://atcoder.jp/contests/abc394/tasks/abc394_c)

O(N)
`WA`を`AC`へ変換する順番を考える問題です。
`WWA`を変換した時、

```
WWA
WAC
ACC
```

となります。
`WA`を`AC`に変換する時、`A`の位置は元の位置より１つ前のインデックスになります。
先頭から処理するのではなく、最後から逆に処理をしましょう。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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=N-1; i>0; i--){
        if(S[i-1] == 'W' && S[i] == 'A'){
            S[i-1] = 'A';
            S[i] = 'C';
        }
    }
    
    cout << S << endl;

    return 0;
} 
```

## [D - Colorful Bracket Sequence](https://atcoder.jp/contests/abc394/tasks/abc394_d)

O(N)
`([])<>()`という文字列を左から順番に処理をしましょう。

```
(
([
([]
ここで[]が消える
()
ここで()が消える
<
<>
ここで<>が消える
(
()
ここで()が消える
```

この処理を見た時に基本情報でよく出題される逆ポーランド記法が思い浮かびます。
これはデータ構造、スタックの問題です。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    stack<char> sk;

    int N = s.size();
    rep(i, N){
        if(sk.size() > 0 && ((sk.top() == '[' && s[i] == ']') || (sk.top() == '(' && s[i] == ')') || (sk.top() == '<' && s[i] == '>'))){
            sk.pop();
        }else{
            sk.push(s[i]);
        }
    }

    if(sk.size() == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
} 
```

## [E - Palindromic Shortest Path](https://atcoder.jp/contests/abc394/tasks/abc394_e)

勉強予定

```C++:C++
```