ABC404個人的備忘録[A-E]

いつも通りだったはず男の備忘録です

### コンテスト概要
AtCoder Beginner Contest 404（Promotion for Engineer Guild）

https://atcoder.jp/contests/abc404

開催日:2025年5月3日 21:00-22:40

## [A - Not Found](https://atcoder.jp/contests/abc404/tasks/abc404_a)
#### 考察
高々25文字なので何をやっても許されそう。
とりあえずvectorで文字が出た回数をメモ。その後回数が0だったものを出力。
チョイっとめんどくさいA問題

#### 提出
``` c++:A.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    
    //vectorで文字の出現回数を管理
    vector<int>num (26,0);
    for(auto x:s){
        num[x-'a']++;
    }

    for(int i=0;i<26;i++){
        //一回も出なかった文字を出力
        if(num[i] == 0){
            char ans = 'a' + i;
            cout << ans << endl;
            return 0;
        }

    }
}
```

## [B - Grid Rotation](https://atcoder.jp/contests/abc404/tasks/abc404_b)
#### 考察
グリッドが2つあるやつはちょっと難易度上がりがちだよね。

もし、グリッドが回せないなら色の異なるマスの数が答え。
じゃあ回すとどうなるか？結局色の異なるマスの数が答え。

なので4方向に関してマス目の異なる数を数えればOK。
ただ回す回数も1手なのでそれを足し忘れないように。

#### 提出
``` c++:B.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

//グリッドを90度回転させる関数
void trn(vector<vector<char>> &s,int n){
    vector<vector<char>>k (n,vector<char>(n));

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            //90ど回すとどこを参照するかちゃんと考える
            k[i][j] = s[n-1-j][i];
        }
    }

    s = k;
    return;
}

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

    vector<vector<char>>s (n,vector<char>(n)),t (n,vector<char>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin >> s[i][j];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin >> t[i][j];
    }

    //デカい値を仮置き
    int ans = 1e6;
    
    for(int i=0;i<4;i++){
        int cnt = 0;

        //色の違うマスを全探査
        for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                if(s[x][y] != t[x][y]) cnt++;
            }
        }

        //回転させた回数も忘れずにansを更新
        ans = min(ans,cnt+i);

        //グリッドを回転させる。
        trn(s,n);
    }

    cout << ans << endl;    
}
```

## [C - Cycle Graph?](https://atcoder.jp/contests/abc404/tasks/abc404_c)
#### 考察
ガチャガチャ言ってるが要するに「一直線に進んですべてのマスを通り元の場所に戻って来れるか？あと無駄な辺もないか？」が分かればよい。

なので、頂点数Nと辺の数Mが異なっている場合話にならない。
N=Mを前提とし、ある頂点から進みNマス後に元の場所に居ればOK。
実装がめんどいんだなこれが。

#### 提出
``` c++:C.cpp
#include <bits/stdc++.h>
using namespace std;

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

    //N≠Mは論外
    if(n != m){
        cout << "No" << endl;
        return 0;
    }

    //辺のつながりをメモ
    vector<vector<int>>num (n,vector<int>(0));

    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;

        num[x-1].push_back(y-1);
        num[y-1].push_back(x-1);
    }

    //頂点を通ったかを確認
    vector<bool>che (n,false);
    //とりあえず頂点１(0-indexで０)から始める
    int now = 0;

    while(now != -1){
        int nex = -1;

        for(auto x:num[now]){
            //辺のうち通ってないほうに向かう
            if(!che[x]){
                nex = x;
                che[x] = true;
                break;
            }
        }

        now = nex;
    }

    string ans = "Yes";
    //通ってない場所があったらNO
    for(auto x:che){
        if(!x) ans = "No";
    }

    cout << ans << endl;  

    
}
```

## [D - Goin' to the Zoo](https://atcoder.jp/contests/abc404/tasks/abc404_d)
#### 考察
もし動物を見る回数が1回以上ならbit全探査でおしまい。
だが、今回は2回以上見る必要がある。
ある動物園にしかいない動物がいたとき、この動物園は2回通う必要がある。逆に言えば特殊な動物園でも最大でも2回しか通わない。
ということでそれぞれの動物園について0回、1回、2回通った場合をすべて探査できればよい。
2進数を使えば0回を1回を全探査できるなら、3進数を使えば0回、1回、2回を調べられる。

というわけで、3進数を使ったbit全探査(?)を行えばOK。

#### 提出
``` c++:D.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    //動物園ごとにいる動物を管理
    vector<vector<int>>num (n,vector<int>(0));
    //動物園の入場料を管理
    vector<ll>cst (n);

    for(int i=0;i<n;i++)cin >> cst[i];
    for(int i=0;i<m;i++){
        int k;
        cin >> k;

        //動物園ごとに動物を追加
        for(int j=0;j<k;j++){
            int x;
            cin >> x;
            num[x-1].push_back(i);
        }
    }

    //bit全探査の範囲は(0,2^n]なので、応用して(0,3^n]
    int pt = pow(3,n);
    ll ans = (1LL<<60);

    for(int i=0;i<pt;i++){
        int c = i;
        vector<int>ct (m,0);
        ll fe = 0;
        
        for(int j=0;j<n;j++){
            //iを三進数で見たときのj桁目が通う回数
            int s = c%3;
            fe += cst[j] * s;
            
            //通う回数分だけ動物を見る
            if(s!=0) for(auto x:num[j])ct[x] += s;
            //次の桁をチェック
            c /= 3;
        }

        int cnt = 0;
        for(auto x:ct){
            if(x > 1) cnt++;
        }

        //ちゃんと全部の動物を見れたら答えを更新
        if(cnt == m) ans = min(ans,fe);
    }

    cout << ans << endl;
    
}
```

## [E - Bowls and Beans](https://atcoder.jp/contests/abc404/tasks/abc404_e)
#### 考察
何をしたいのかわかりづらい問題。しっかりとかみ砕いていく。
「まず茶碗を一列に並べる。」
「ある茶碗の豆を最大C個前の茶碗に移動させれる。」
「豆を一番前に集めるのに最大何手必要か？」というのが概要。

ここで移動させる豆の数は任意という設定。だが、例えば3つの豆を1つずつ3手で送るより一気に1手で送るほうがいいに決まってる。なので豆は全部一気に送ることにする。

さて、ここで豆はちまちま送るより一気に送るほうが効率がいいはず。なので、豆は後ろから順に合わせていくのが最短手っぽい。これを端的に言えば「茶碗0と豆のある茶碗を最短ですべて通れ」という問題になる。ここまでくればあとは最短経路問題になる。

茶碗０から「豆のある手前の茶碗」に最短で向かう。その茶碗から「豆のある手前の茶碗」に最短で向かい...を最後までやって経由した茶碗の個数が答え。

とまあ簡単に言ってますがこの考察までに50分くらいかかってます...

#### 提出
``` c++:E.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T> using p_que = priority_queue<T,vector<T>,greater<T>>;

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

    //豆が送られてくる茶碗のリスト
    vector<vector<bool>>path (n,vector<bool>(n,false));
    for(int i=1;i<n;i++){
        int x;
        cin >> x;

        //茶碗iから手前x個の茶碗は、茶碗iは豆が送られてくる。
        for(int j=0;j<x;j++){
            path[i-1-j][i] = true;
        }
    }

    //豆のある場所だけに興味がある
    queue<int>bn;
    for(int i=1;i<n;i++){
        int x;
        cin >> x;

        if(x == 1) bn.push(i);
    }

    int now = 0;
    int ans = 0;
    while(!bn.empty()){
        //今の茶碗と最も手前の茶碗の最短距離を考える
        int nex = bn.front();
        bn.pop();

        vector<int>gone (n,1e6);
        gone[now] = 0;

        //茶碗iから茶碗jまでの最短距離をダイクストラで
        p_que<pair<int,int>> que;
        que.push({0,now});

        while(!que.empty()){
            auto[x,p] = que.top();
            que.pop();
            if(gone[p] != x) continue;

            //現在地から目的地までで経路がある場所を確認
            for(int i=p+1;i<=nex;i++){
                if(!path[p][i]) continue;

                if(gone[i] > gone[p] + 1){
                    gone[i] = gone[p] + 1;
                    que.push({gone[i],i});
                }
            }
        }

        ans += gone[nex];
        now = nex;
    }

    cout << ans << endl;
}
```

## 結果
ABCD(1)E(2)　5完　105:34

順位　1708位
パフォーマンス　1290

## 感想
んー。ペースはいつも通りだったんですがちょっと成績が振るわなかった。
タイムも回答数もここ4回のABCと変わらないんですがねぇ。

やっぱり早解きは苦手だ。