AtCoder Beginner Contest 404

Last updated at 2025-05-06Posted at 2025-05-06

A - Not Found

問題文
O(N)
アルファベット26文字をハッシュで保持します。
sの文字列にある文字をハッシュから削除します。
ハッシュに残っている文字が答えです。

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;

    set<char> st;
    rep(i, 26) st.insert('a'+i);
    int n = st.size();
    rep(i, n){
        st.erase(s[i]);
    }
    cout << *st.begin() << endl;

    return 0;
}

B - Grid Rotation

問題文
O(N^2)
全探索。

4つの回転の方向全て探索
一致していない数を計測
回転数+一致していない数の合計の最小値を求める

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;
    cin >> N;
    vector<string> S(N), T(N);
    rep(i, N) cin >> S[i];
    rep(i, N) cin >> T[i];

    vector<vector<string>> C(4, vector<string>(S));
    rep(y, N){
        rep(x, N){
            C[1][y][N-x-1] = S[x][y];
            C[2][N-x-1][N-y-1] = S[x][y];
            C[3][N-y-1][x] = S[x][y];
        }
    }

    vector<int> cnt(4, 0);
    rep(y, N){
        rep(x, N){
            rep(i, 4){
                if(C[i][y][x] != T[y][x]) cnt[i]++;
            }
        }
    }

    int num = 1e9;
    rep(i, 4){
        num = min(num, cnt[i] + i);
    }
    cout << num << endl;

    return 0;
}

C - Cycle Graph?

問題文

O((N+M)α(N))
unionfindの問題です。

問題文の意味を理解することが大事な問題です。

サイクルグラフとは、閉路のあるグラフです

サイクルグラフにさらに条件がついています。

v_1, v_2, V_i, ...., v_{n-1}の要素が全て同一のグラフにある

上記の条件から以下の事が分かります。

辺のMの数はNと同じである
全ての頂点は2個の辺と繋がっている

２つだけではWAになるパターンがあります。
N個の頂点が8個の場合を考察します。

1→3→2→4→1
5→7→6→8→5

と繋がっているグラフは、

辺の数がN＝M
全ての頂点は2個の辺と繋がっている
の条件を満たしますが、全ての頂点は同一のグループである条件を満たしていないのでNoです。

unionfindで全ての頂点が同一のグループにあるか判定します。

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; }

struct UnionFind{
    vector<int> par, rank, siz;

    UnionFind(int N): par(N,-1), rank(N, 0), siz(N, 1){}

    int root(int x){
        if(par[x]==-1) return x;
        else return par[x] = root(par[x]);
    }

    bool isSame(int x, int y){
        return root(x) == root(y);
    }

    bool unite(int x, int y){
        int rx = root(x), ry = root(y);
        if(rx == ry) return false;
        if(rank[rx]<rank[ry]) swap(rx, ry);
        par[ry] = rx;
        if(rank[rx]==rank[ry]) rank[rx]++;
        siz[rx] += siz[ry];
        return true;
    }

    int size(int x){
        return siz[root(x)];
    }
};

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

    UnionFind uni(N);
    vector<vector<int>> graph(N);
    rep(i, M){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
        uni.unite(a, b);
    }

    if(M != N){
        cout << "No" << endl;
        return 0;
    }

    rep(i, N){
        if(graph[i].size() != 2){
            cout << "No" << endl;
            return 0;
        }
    }

    rep(i, N){
        if(uni.size(i) != N){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

D - Goin' to the Zoo

問題文

O(3^n)
N進数の全探索

bit全探索は2^nの判定ですが、今回はm＾nの判定を行う問題です。
全ての動物園は１箇所、最大で２回行く可能性があります。
m＾nは、3＾nの判定と読み解く事ができます。
まずは、3＾nの判定を行うためにデータ、配列を作成しましょう。

C++

    vector<vector<int>> num;
    auto dfs = [&](auto dfs, vector<int> v) -> void {
        if(v.size() == N){
            num.push_back(v);
            return;
        }
    
        for(int i=0; i<3; i++){
            v.push_back(i);
            dfs(dfs, v);
            v.pop_back();
        }
    };
    dfs(dfs, vector<int>());

このコードにより、Nの動物園に0~2回ほど行ったか判定する配列を作成を作成します。
次に動物園_iに行くとどの種類の動物を見ることができるか管理するデータを用意します。
サンプル入力1で考察します。

4 3
1000 300 700 200
3 1 3 4
3 1 2 4
2 1 3

動物園の入場料は1次元配列で良さそうです。
動物園に入場すると見る事ができる動物のデータは、

K A_0_0 A_0_1 A_0_2 A_0_{K-1}

から２次元配列で用意することが分かります。

A[入場する動物園][動物の数] = 動物の種類

から以下のコードになります。

C++

    int N, M;
    cin >> N >> M;
    vector<ll> C(N);
    rep(i, N) cin >> C[i];
    vector<vector<ll>> A(N);
    rep(i, M){
        int K;
        cin >> K;
        rep(j, K){
            int a;
            cin >> a;
            a--;
            A[a].push_back(i);
        }
    }

これをbit全探索の要領で、n進数版の全探索を行います。

どの動物園に何回行ったかvector<vector<int>> numでループ
行った動物園にどの動物がいるかカウント
M種類の動物は全て２回以上見ているか
M種類の動物は全て２回以上見ていたのならC[i]円をcntに加算
最も小さいcntを求めます

C++

    ll ans = 2e18;
    for(vector<int> nu:num){
        vector<int> anumal(M);
        ll cnt = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<nu[i]; j++){
                for(int k=0; k<A[i].size(); k++){
                    anumal[A[i][k]]++;
                }
                cnt += C[i];
            }
        }
        bool ok = true;
        rep(i, M){
            if(anumal[i] < 2) ok = false;
        }
        if(ok) ans = min(ans, cnt);
    }
    cout << ans << endl;

考察が終わりました。
コーディングしましょう。

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, M;
    cin >> N >> M;
    vector<ll> C(N);
    rep(i, N) cin >> C[i];
    vector<vector<ll>> A(N);
    rep(i, M){
        int K;
        cin >> K;
        rep(j, K){
            int a;
            cin >> a;
            a--;
            A[a].push_back(i);
        }
    }

    vector<vector<int>> num;
    auto dfs = [&](auto dfs, vector<int> v) -> void {
        if(v.size() == N){
            num.push_back(v);
            return;
        }
    
        for(int i=0; i<3; i++){
            v.push_back(i);
            dfs(dfs, v);
            v.pop_back();
        }
    };
    dfs(dfs, vector<int>());

    ll ans = 2e18;
    for(vector<int> nu:num){
        vector<int> anumal(M);
        ll cnt = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<nu[i]; j++){
                for(int k=0; k<A[i].size(); k++){
                    anumal[A[i][k]]++;
                }
                cnt += C[i];
            }
        }
        bool ok = true;
        rep(i, M){
            if(anumal[i] < 2) ok = false;
        }
        if(ok) ans = min(ans, cnt);
    }
    cout << ans << endl;

    return 0;
}

記事について

Qiitaのmarkdownの仕様が変更されました。
それに伴い記載を少し変えています。
大変なので過去の記事は修正しません。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up