AtCoder Beginner Contest 289（ABC289）

atcoder.jp

Bondo416さんのＳｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）での成績：510位
パフォーマンス：1841相当
レーティング：1406→1458 (+52) :)#AtCoder #Ｓｋｙ株式会社プログラミングコンテスト2023（ABC289） https://t.co/eZxNZlaKX7

— ボンド@競プロ (@bond_cmprog) February 11, 2023

A - flip

1文字ずつ見ていき、各文字を反転させたものを出力する

提出コード

void solve() {
    string S;
    cin >> S;
    for (char c : S) {
        if (c == '1') cout << 0;
        else cout << 1;
    }
    cout << endl;
}

B - レ

連結成分をUnionFindで管理する
連結成分に含まれる頂点を降順ソートし、出力する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    REP(i, M) {
        int a;
        cin >> a;
        --a;
        uf.unite(a, a + 1);
    }
    map<int, vector<int>> mp;
    vector<int> used(N);
    REP(i, N) mp[uf.root(i)].emplace_back(i);
    REP(i, N) if (!used[i]) {
        auto v = mp[uf.root(i)];
        sort(ALL(v));
        reverse(ALL(v));
        for (auto x : v) {
            cout << x + 1 << " ";
            used[x] = 1;
        }
    }
    cout << endl;
}

C - Coverage

bit全探索で条件を満たすものを数える

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> a(M);
    REP(i, M) {
        int C;
        cin >> C;
        REP(j, C) {
            int num;
            cin >> num;
            --num;
            a[i].emplace_back(num);
        }
    }
    int ans = 0;
    REP(i, 1 << M) {
        int bits = 0;
        REP(j, M) if (i >> j & 1) {
            REP(k, a[j].size()) { bits |= (1 << a[j][k]); }
        }
        if (__builtin_popcount(bits) == N) ans++;
    }
    cout << ans << endl;
}

D - Step Up Robot

$ dp[i] := i $ 段目にたどり着けるかどうかをDPで求める

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    int M;
    cin >> M;
    vector<int> B(101010);
    REP(i, M) {
        int b;
        cin >> b;
        B[b] = 1;
    }
    int X;
    cin >> X;
    vector<int> dp(101010);
    dp[0] = 1;
    REP(i, 101010) if (dp[i] and !B[i]) {
        REP(j, N) {
            int nxt = i + A[j];
            if (nxt < 101010 and !B[nxt]) dp[nxt] = 1;
        }
    }
    cout << (dp[X] ? "Yes" : "No") << endl;
}

E - Swap Places

高橋くんが頂点 $ i $、青木くんが頂点 $ j $ にいる状態を一つの頂点とみなす
その頂点上でBFSを行うことで行動回数の最小値を求めることができる

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> C(N);
    REP(i, N) cin >> C[i];
    vector<vector<int>> g(N);
    REP(i, M) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector dist(N, vector(N, INF));
    dist[0][N - 1] = 0;
    queue<P> q;
    q.emplace(0, N - 1);
    while (!q.empty()) {
        auto [u, v] = q.front();
        q.pop();
        for (auto nu : g[u]) {
            for (auto nv : g[v]) {
                if (C[nu] == C[nv]) continue;
                if (dist[nu][nv] < INF) continue;
                dist[nu][nv] = dist[u][v] + 1;
                q.emplace(nu, nv);
            }
        }
    }
    cout << (dist[N - 1][0] == INF ? -1 : dist[N - 1][0]) << endl;
}