AtCoder Beginner Contest 394

A - 22222

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

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

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

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

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

WWA
WAC
ACC

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

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

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

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

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

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

勉強予定

C++