【ABC426】AtCoder Beginner Contest 426【C++】

コンテスト名

AtCoder Beginner Contest 426

コンテストURL

https://atcoder.jp/contests/abc426

開催日

2025/10/04 21:00–22:40

---

A: OS Versions

解法

• map<string, int> でバージョンを数に変換する

ABC426A.cpp

#include <iostream>
#include <map>
using namespace std;

int main(){
    string x, y;
    cin >> x >> y;

    map<string, int> M;
    M["Ocelot"] = 0;
    M["Serval"] = 1;
    M["Lynx"] = 2;

    if(M[x]>=M[y]){
        cout << "Yes" << endl;
    }else{
       cout << "No" << endl; 
    }

    return 0;
}

B: The Odd One Out

解法

• map<char, int> に各文字の数を記録する

ABC426B.cpp

#include <iostream>
#include <map>
using namespace std;

int main(){
    string s;
    cin >> s;

    map<char, int> M;
    for(int i=0; i<s.size(); i++){
        M[s[i]]++;
    }

    for(auto [c, cnt] : M){
        if(cnt==1){
            cout << c << endl;
            return 0;
        }
    }
}

C: Upgrade Required

解法

• 各操作が終わると、 $X_i$ 以前のバージョンは考慮しなくてよくなることに着目する
• 計算量は $\mathrm{O} (N + Q)$

ABC426C.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, q;
    cin >> n >> q;

    vector<int> V(n, 1);

    int x, y, minidx = 0;
    while(q--){
        cin >> x >> y;
        x--;
        y--;

        int sum = 0;
        for(int i=minidx; i<=x; i++){
            sum += V[i];
            V[i] = 0;
            minidx = x + 1;
        }
        V[y] += sum;
        cout << sum << '\n';
    }

    return 0;
}

D: Pop and Insert

解法

• ランレングス圧縮によって、0 と 1 それぞれについて最長連続部分列を発見する
• 最長連続部分列の前後の文字を操作する必要がある
• 0 に揃える場合は、もともと 0 の箇所は $2$ 回、もともと 1 の箇所は $1$ 回操作する必要がある
• 1 に揃える場合は、もともと 0 の箇所は $1$ 回、もともと 1 の箇所は $2$ 回操作する必要がある

ABC426D.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    string s;
    while(t--){
        cin >> n >> s;

        vector<pair<char, int>> V;
        V.emplace_back(s[0], 1);
        for(int i=1; i<n; i++){
            if(V.back().first==s[i]){
                V.back().second++;
            }else{
                V.emplace_back(s[i], 1);
            }
        }

        int max0cnt = 0, max1cnt = 0;
        for(auto [c, num] : V){
            if(c=='0'){
                max0cnt = max(max0cnt, num);
            }else if(c=='1'){
                max1cnt = max(max1cnt, num);
            }
        }

        int cnt0 = 0, cnt1 = 0;
        for(int i=0; i<n; i++){
            if(s[i]=='0'){
                cnt0++;
            }else if(s[i]=='1'){
                cnt1++;
            }
        }

        cout << min((cnt0-max0cnt)*2 + cnt1, (cnt1-max1cnt)*2 + cnt0) << '\n';
    }
}