【ABC427】AtCoder Beginner Contest 427【C++】

コンテスト名

パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 427）

コンテストURL

https://atcoder.jp/contests/abc427

開催日

2025/10/11 21:00–22:40

---

A: ABC -> AC

解法

• 問題文通りに操作する

ABC427A.cpp

#include <iostream>
#include <string>
using namespace std;

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

    for(int i=0; i<s.size(); i++){
        if(i==s.size()/2){
            continue;
        }

        cout << s[i];
    }
    cout << endl;

    return 0;
}

B: Sum of Digits Sequence

解法

• 問題文通りに順番に計算する

ABC427B.cpp

#include <iostream>
#include <vector>
using namespace std;

int f(int x){
    int res = 0;

    while(x){
        res += x % 10;
        x /= 10;
    }

    return res;
}

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

    vector<int> A(n+1);
    A[0] = 1;
    for(int i=0; i<n; i++){
        if(i){
            A[i+1] = f(A[i]) + A[i];
        }else{
            A[i+1] = f(A[i]);
        }
    }

    cout << A[n] << endl;

    return 0;
}

C: Bipartize

解法

• bit 全探索
• 頂点の色分けを bit 全探索して、二部グラフにするために削除する辺の数を求める

ABC427C.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<vector<int>> G(n);
    int u, v;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        u--;
        v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int minv = m;
    for(int i=0; i<(1<<n); i++){
        int cnt = 0;
        for(int j=0; j<n; j++){
            for(int k=0; k<G[j].size(); k++){
                if(((i>>j)&1)==((i>>G[j][k])&1)){
                    cnt++;
                }
            }
        }

        minv = min(minv, cnt/2);
    }

    cout << minv << endl;

    return 0;
}