ABC329 参加記(ABCD+F)

ABCD四完+(終了後のおまけF)です。

一応温まりました。

A - Spread

やるだけ

最後の空白に注意

abc329_a.cpp

#include<bits/stdc++.h>
using namespace std;

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

    for(int i = 0; i < S.size(); ++i)
    {
        cout << S[i] << (i != S.size() - 1 ? " " : "\n");
    }

    return 0;
}

B - Next

std::setで全部管理して、最大値を消した後にもう一度最大値を取得する

abc329_b.cpp

#include<bits/stdc++.h>
using namespace std;

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

    set<int> dat;
    for (int i = 0; i < N; ++i){
        int A;
        cin >> A;

        dat.emplace(A);
    }

    dat.erase(*dat.rbegin());

    cout << *dat.rbegin() << endl;

    return 0;
}

C - Count xxx

文字が最大で何個連続してるかをstd::mapで管理して、その全ての値の合計が答え。

cntの初期値が1なのと、最後の文字は勝手に処理されないことに注意

abc329_c.cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N;
    string S;
    cin >> N >> S;

    map<char, int> dat;
    char mae = S[0];
    int cnt = 1;

    for (int i = 1; i < N; ++i){
        if(S[i]!=mae){
            dat[mae] = max(dat[mae], cnt);
            cnt = 1;
        }else{
            cnt++;
        }
        mae = S[i];
    }

    dat[mae]=max(dat[mae], cnt);

    int ans = 0;
    for(auto x:dat){
        ans += x.second;
    }

    cout << ans << endl;

    return 0;
}

D - Election Quick Report

「$i$票目時点で一番票がある人」を管理すればok

自分はstd::pairで管理した

abc329_d.cpp

#include<bits/stdc++.h>
using namespace std;

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

    vector<int> dat(N, 0);
    pair<int, int> tmp;

    for (int i = 0; i < M; ++i){
        int A;
        cin >> A;

        A--;
        dat[A]++;

        if (dat[A] > tmp.second || (dat[A] == tmp.second && A < tmp.first))
        {
            tmp.first = A;
            tmp.second = dat[A];
        }

        cout << tmp.first + 1 << endl;
    }

    return 0;
}

F - Colored Ball

解説AC。ちょっと変えれば動いて悔しい

マージテクって何だよ

abc329_f.cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N,Q;
    cin>>N>>Q;

    vector<int> C(N);
    for (int i = 0; i < N; ++i){
        cin >> C[i];
    }

    vector<set<int>> dat(N);
    for(int i = 0; i < N; ++i){
        dat[i].emplace(C[i]);
    }

    while(Q--){
        int a,b;
        cin >> a >> b;

        a--;
        b--;

        if(dat[a].size()<dat[b].size()){
            dat[b].merge(dat[a]);
            dat[a].clear();
        }
        else{
            dat[a].merge(dat[b]);
            dat[b].clear();
            swap(dat[a],dat[b]);
        }

        cout << dat[b].size() << endl;
    }

    return 0;
}

今日の教訓

マージは小さい方から大きい方に向かってやれ。