AtCoder Beginner Contest 329 振り返り

# ABC329
## 概要
実力的には二年前に茶色になって放置して暫くぶりの参加なので詳しい解説などは期待しないでもらえると。
同じぐらいの初心者さんがこんな感じで解いたのかぁ的な見方か、上級者の方が愉悦として見ていただけると幸いです。

https://atcoder.jp/contests/abc329

コンテスト中に触ることができたのはA,B,C,D,F問題。ACできたのはD問題までです。
触れた問題で解説を見て理解できたものについては振り返っていきたいと考えています。

## A - Spread
__考えてたこと__
stringで受け取って一文字ずつ出力するだけの簡単な問題だと考えました。ただ、最後の一文字の場合どうやって空白を出力しないかな...という部分で悩みました。
今考えるより一旦強引に解決しようと思い、文字数をカウントして最後の文字の時だけ別の分岐に行くようにして解決しました。

__提出したもの__
```c++:a.cpp
int main() {
    string s;
    cin >> s;
    for(int i=0; i<s.size(); i++){
        if(i==s.size()-1){
            cout << s[i] << endl;
            return 0;
        }
        cout << s[i] << " " << endl;
    }
    return 0;
}
```

__振り返り__
解説を見てみたら、解説はfor文で最後から二文字目までfor文を回して最後の一文字のみ別で出力するという形だったので、まあ今回提出したコードでもよかったかなと思いました。

## B - Next
__考えてたこと__
一度N個の整数を全部受け取って、最大値を除外。その後に最大値を取得すれば良いかなと考えました。
重複を考えなくて良いこと、最大値を簡単に取得できることからsetを使えばすぐに解決できると考えました。
ただ、久々の参加のせいかsetについて覚えてなくて、調べるのに少し時間がかかってしまいました...。

__提出したもの__
```c++:b.cpp
int main() {
    int n;
    cin >> n;
    set<int>set;
    rep(i,0,n){
        int a;
        cin >> a;
        set.insert(a);
    }
    int max = *rbegin(set);
    set.erase(max);
    int max_second = *rbegin(set);
    cout << max_second << endl;
    return 0;
}
```
__振り返り__
解答ではvectorと __*max_element__ を用いて実装していました。
B問題なのでそれほど気にすることでもないですが、vectorを使った方が値を追加するときの計算量が減って全体的な計算量は減る？と考えました。

## C - Count xxx
__考えてたこと__
変数名が雑なのはご容赦を...。
for文で一文字ずつみて前の文字と同じ場合はnowという変数の後ろに追加してsetに保存、
前の文字と異なる場合はその文字をnowにしてsetに保存、これらのsetの数を最後にカウントするとしました。
これによって、全てのパターンを確認しながら重複するものを数えることはない実装になったと考えていました。
ただ、実際にはTLE, MLEが発生しました。

__提出したもの__
```c++:c.cpp
int main() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    set<string>set;

    string now;
    for(int i=0; i<s.size(); i++){
        if(i==0){
            now += s[i];
            set.insert(now);
        }
        else{
            if(s[i-1]==s[i]){
                now += s[i];
                set.insert(now);
            }
            else{
                now = s[i];
                set.insert(now);
            }
        }
    }
    cout << set.size() << endl;
    return 0;
}
```
__考えてたこと(二度目)__
なぜTLE, MLEなのか考えていたのですがsetの挿入にO(logN)かかるためそれが原因かと考えました。
(そもそも、setに入れる値の個数がとんでもないことになるため上のコードではメモリで落ちることは明らかなのですが本番中は気付けませんでした...メモリ使用量についても勉強します。)

その後、暫く考えても分からずD問題に行きました。D問題を考えている最中に、mapが使えるのではないかと気づきDをACした後C問題に帰ってきました。

実装としては、1文字目を確認した後に辞書のキーとして登録、値は1に。2文字目が同じ文字ならそのキーの値+1, 違う文字ならその文字を辞書のキーとして登録、値を1に。三文字目以降も同様の処理を行うという形です。
これにより、辞書のキーは最大でも26個。辞書の値に同じ文字が連続した回数がカウントされていて、辞書全体の値を足したとき解が求まるというものです。

__提出したもの(二度目)__
```c++:c.cpp
int main() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    map<char, int> map;

    int cnt = 0;

    for (int i = 0; i < n; i++) {
        if (i == 0) {
            cnt = 1;
            map[s[i]] = cnt;
        } else {
            if (s[i] == s[i - 1]) {
                cnt++;
                if (map[s[i]] < cnt) {
                    map[s[i]] = cnt;
                }
            } else {
                cnt = 1;
                if (map[s[i]] < cnt) {
                    map[s[i]] = cnt;
                }
            }
        }
    }

    ll ans=0;
    fore(a, map) {
        ans += a.second;
    }
    cout << ans << endl;
    
    return 0;
}
```

__振り返り__
メモリ使用量を考えていなかったという点がまず反省です。
解答を見ましたが __int c = s[l] - 'a';__　でvectorのキーを持ってきてるのが美しいなぁと思いました。
ランレングス圧縮については知らなかったので要チェックです。
やってること自体は同じ答えに辿り着けたので嬉しかったです。

## D - Election Quick Report
__考えてたこと__
正直解けないかなぁと思って、最初は受け取った値を全部vectorに入れてその後M回表を確認、N人の票数を確認するというコードを書いて提出してTLEになりました。
ただ、解法自体はあっていそうだと思ったのでTLE解消の術を考え始めました。
__提出したもの__
```c++:d.cpp
int main() {
    int n,m;
    cin >> n >> m;
    vector<int>vec(m);
    rep(i,0,m){
        cin >> vec[i];
    }

    vector<int>candidate(n+1);
    fore(a,vec){
        candidate[a]++;
        int max=0;
        int max_candidate = 0;
        for(int i=1; i<=n; i++){
            if(max<candidate[i]){
                max = candidate[i];
                max_candidate = i;
            }
        }
        cout << max_candidate << endl;
    }
    return 0;
}
```
__考えてたこと(二度目)__
二重for文をどうやって解決するか考えて、常にその時点での最高票数、最高票数を持っている候補者を保持すればいいんじゃないか？と考えました。
最高票数を保持して、更新された票によって最高票数未満なら無視、同値なら候補者の番号を比較して低い番号に更新、上回ったら票数・候補者を共に更新としました。
これで二重for文を解消し無事ACでした。

あと、これを解いている最中、C問題でmapを使うという方針を閃いたのですが、今振り返るとどのタイミングで閃いたのか全く思い出せません...。候補者と票数をmapで保持するとか最初考えてたのかな...?
__提出したもの(二度目)__
```c++:d.cpp
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> vec(m);
    rep(i, 0, m) {
        cin >> vec[i];
    }

    vector<int> candidate(n + 1);

    int max = 0;
    int max_candidate = 0;

    fore(a, vec) {
        candidate[a]++;
        if (max == candidate[a]) {
            if (a < max_candidate) {
                max_candidate = a;
            }
        } else if (max < candidate[a]) {
            max = candidate[a];
            max_candidate = a;
        }
        cout << max_candidate << endl;
    }
    return 0;
}
```
__振り返り__
解説を見てみたら、だいたい方針は同じで嬉しかったです。
ただ、最大票数は保持しなくても最大得票者さえ持っていればアクセスは簡単なことがちょっと反省です。
実装自体に問題はないけど可読性そっちの方が良さそうな気がする...。
あと、この問題に限った話じゃないですが、全体的にmax,minを用いて可読性を高められました...。


## F - Colored Ball
__考えてたこと__
終了数分前に取り組んだのでどうせ解けないだろと思っていたのですが実装だけはできてしまった問題。
ただ、問題の核心は実装ではなく時間削減だった気がします。


__提出したもの__
```c++:f.cpp
int main() {
    int n, q;
    cin >> n >> q;

    vector<set<int>> vec(n);

    rep(i, 0, n) {
        int c;
        cin >> c;
        vec[i].insert(c);
    }

    rep(i, 0, q) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        fore(ball, vec[a]) {
            vec[b].insert(ball);
        }
        vec[a].clear();
        cout << vec[b].size() << endl;
    }
    return 0;
}
```
__振り返り__
解説を見てみましたが実装自体は上でもあってるぐらい簡単なものでした。
ただ、setのinsertがO(logN)で、それが原因でTLEを引き起こしているということに気づけませんでした。
というか、一回上の回答出した時点でもう時間切れでした。
時間があっても気づけたとは思えないので悔いはないです、勉強です。

__提出したもの(コンテスト後)__
```c++:f.cpp
int main() {
    int n, q;
    cin >> n >> q;

    vector<set<int>> vec(n);

    rep(i, 0, n) {
        int c;
        cin >> c;
        vec[i].insert(c);
    }

    rep(i, 0, q) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if (vec[a].size() < vec[b].size()) {
            fore(ball, vec[a]) {
                vec[b].insert(ball);
            }
            vec[a].clear();
            cout << vec[b].size() << endl;
        } else {
            fore(ball, vec[b]) {
                vec[a].insert(ball);
            }
            vec[b].clear();
            cout << vec[a].size() << endl;
            swap(vec[a], vec[b]);
        }
    }
    return 0;
}
```
コンテスト中に出したものに、条件分岐を一つ足しただけです。

## 総括
- max,minを使ってコードの可読性を上げよう。
- コンテスト中みたいな急いで書いてる時でもわかりやすい変数名を付けやすいように努力。
- B,C,Fでsetで詰まった。こういう基礎知識復習していきたい...。
- メモリ使用量についても勉強、感覚掴む。

## 感想
就職後、部署に所属してから半年が経ち少し余裕ができたため、娯楽やスキルアップを目的に久々にやってみたのですが、楽しかったです。D問題まで解けたのはbit全探索、優先探索のようなアルゴリズム系統が出てなくてアドリブでなんとかなる系統だったからだと思っているので、急ぎその辺りを復習したいです。
unratedで参加していましたがこんな感じでした。
![Screenshot 2023-11-20 at 22.23.15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1396642/e7e94ce1-05cc-8612-5454-c7e6531bac1a.png)


## 終わり
普段は記事を見て勉強させてもらっているだけで、自分で書くのは初めてだったので気がむくままに書いたのですがどうだったでしょうか、これからも振り返りで発信していきたいなぁと考えています。
ここまでお付き合いいただきありがとうございます。