AtCoder Beginner Contest 380

A - 123233

O(N)
10個の要素を用意した配列か、mapを使用しましょう。
出現回数を数えて判定します。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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;
    map<int, int> mp;
    rep(i, 6) mp[S[i]]++;

    if(mp['1'] == 1 && mp['2'] == 2 && mp['3'] == 3){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
} 

B - Hurdle Parsing

O(N)
シミュレートしましょう。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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<int> A;
    repx(i, 0, N){
        if(S[i] == '|'){
            A.push_back(0);
        }else{
            A.back()++;
        }
    }
    A.pop_back();

    rep(i, A.size()){
        cout << A[i];
        if(i < A.size() - 1) cout << ' ';
        else cout << endl;
    }

    return 0;
} 

C - Move Segment

O(N)
シミュレートの問題です。
綺麗なコードが書きたいならランレングス圧縮です。
サンプル1を基準にしましょう。

15 3
010011100011001

の時にランレングス圧縮します。

{0, 1} {1, 1} {0, 2} {1, 3} {0,3} {1, 2} {0, 2} {1, 1}

{1, 3}の箇所か、{1, 2}の箇所で判定を行いましょう。
{0,3}, {1, 2}を入れ替えましょう。

C++

        if(rle[i].first == '1'){
            cnt++;
            if(cnt == K-1){
                swap(rle[i+2], rle[i+1]);
            }
        }

最後に文字列へ復元を行い出力します。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, K;
    cin >> N >> K;
    string S;
    cin >> S;

    vector<pair<char, int>> rle;
    for(auto c:S){
        if(rle.size() && rle.back().first == c){
            rle.back().second++;
        }else{
            rle.push_back({c, 1});
        }
    }

    int cnt = 0;
    for(int i=0; i<rle.size(); i++){
        if(rle[i].first == '1'){
            cnt++;
            if(cnt == K-1){
                swap(rle[i+2], rle[i+1]);
            }
        }
    }

    string ans;
    for(auto [c, cnt]:rle){
        for(int i=0; i<cnt; i++){
            ans += c;
        }
    }
    cout << ans << endl;

    return 0;
} 

D - Strange Mirroring

O(N)
K_i - 1の1のbitの数を数える問題です。
サンプル1を見ましょう。

aB
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

aBを基準に
「小文字を大文字に書き換えた文字列をT」
を作成し、
「SとTとをこの順に連結した文字列を新たなS」
を作成します。

aB Ab Ab aB Ab aB aB Ab

規則性が分かりません。
文字列の数は、

Sの文字数 = Sの文字数 * 2 

と増えていきます。
2進数が関係あるかもしません。

0	1	2	3	4	5	6	7
aB	Ab	Ab	aB	Ab	aB	aB	Ab
000	001	010	011	100	101	110	111

K_iをSの文字数で除算をし、1のbitの数を数えます。
1のbitの数の偶数、奇数か判定をします。
奇数の時に小文字を大文字、大文字を小文字に書き換えましょう。

• popcountはC++20の関数です
• 開発環境を構築しておきましょう

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, T;
    cin >> S;
    ll Q;
    cin >> Q;
    vector<ll> K(Q);
    rep(i, Q) cin >> K[i];

    int N = S.size();
    rep(i, Q){
        ll k = K[i] - 1;
        ll num = k / N;
        ll index = k % N;
        
        if(popcount((unsigned long long)num) % 2 == 0){
            cout << S[index];
        }else{
            if(isupper(S[index])) cout << (char)(S[index] + 32);
            else cout << (char)(S[index] - 32);
        }

        if(i < Q-1) cout << ' ';
        else cout << endl;
    }

    return 0;
}