Zenn
🔵

【ABC350】AtCoder Beginner Contest 350【C++】

2024/04/21に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）

コンテストURL

https://atcoder.jp/contests/abc350

開催日

2024/04/20 21:00-22:40

A: Past ABCs

解法

  • ABC000 や ABC316 に注意する
  1. 1 文字ずつ int 型に変換して番号を計算する方法
  2. 部分文字列を求めてから int 型に変換する方法
ABC350A_1.cpp
#include <iostream>
#include <string>
using namespace std;

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

    int num = 0;
    num += (s[3]-'0')*100;
    num += (s[4]-'0')*10;
    num += (s[5]-'0');

    if(num>0 && num<350 && num!=316){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
ABC350A_2.cpp
#include <iostream>
#include <string>
using namespace std;

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

    int num = stoi(s.substr(3, 3));

    if(num>0 && num<350 && num!=316){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Dentist Aoki

解法

  • 歯の状態を vector<int> で管理してシミュレーションする
ABC350B.cpp
#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> V(n, 1);
    int t;
    for(int i=0; i<q; i++){
        cin >> t;
        t--;
        if(V[t]==0){
            V[t]++;
        }else{
            V[t]--;
        }
    }

    int sum = 0;
    for(int i=0; i<n; i++){
        sum += V[i];
    }

    cout << sum << endl;
    return 0;
}

C: Sort

解法

  • 前から順番に正しい番号に入れ替える
  • unordered_map<int, int> で各整数がどこにあるかを記録する
ABC350C.cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

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

    vector<int> A(n);
    unordered_map<int, int> M;
    for(int i=0; i<n; i++){
        cin >> A[i];
        A[i]--;
        M[A[i]] = i;
    }

    vector<pair<int, int>> V;
    for(int i=0; i<n; i++){
        if(A[i]!=i){
            V.emplace_back(i+1, M[i]+1);
            M[A[i]] = M[i];
            A[M[i]] = A[i];
            M[i] = i;
            A[i] = i;
        }
    }

    cout << V.size() << endl;
    for(auto [x, y] : V){
        cout << x << " " << y << '\n';
    }

    return 0;
}

D: New Friends

解法

  • 人を頂点、友人関係を辺としたグラフを考える
  • 各連結成分を完全グラフにすることを考える
  • 各連結成分の頂点数を V 、辺数を E とすると全体の合計操作数は \sum ({}_V \mathrm{C}_2 - E) = \sum {}_V \mathrm{C}_2 - M
    • 各連結成分を完全グラフにするために加える辺数を求める
      • 完全グラフになったときの辺数からすでにある辺数を引く
      • すでにある辺数は連結成分ごとに求めなくても合計で M 本あるとわかっている
  1. Union-Find
    • Union-Find で各連結成分の頂点数を求める
    • 連結成分ごとに 1 回ずつ加算するために頂点が連結成分の根のときだけ size() を求める
  2. 深さ優先探索 (DFS)
    • DFS で頂点数と辺数を同時に求める
    • 辺数は 2 重にカウントされているため 2 で割る
ABC350D_1.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct UnionFind{
    vector<int> P;
    vector<int> S;

    UnionFind(int n) : P(n), S(n, 1){
        for(int i=0; i<n; i++){
            P[i] = i;
        }
    }

    int find(int x){
        if(x==P[x]){
            return x;
        }
        return P[x] = find(P[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);

        if(x==y){
            return;
        }

        if(S[x]<S[y]){
            swap(x, y);
        }

        P[y] = x;
        S[x] += S[y];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return S[find(x)];
    }
};

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

    UnionFind uf(n);
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--;
        b--;
        uf.unite(a, b);
    }

    long long int sum = 0;
    for(int i=0; i<n; i++){
        if(uf.find(i)==i){
            int cnt = uf.size(i);
            sum += (long long int)cnt*(cnt-1)/2;
        }
    }

    sum -= m;

    cout << sum << endl;
    return 0;
}
ABC350D_2.cpp
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> G;
vector<int> seen;

void dfs(int v, int &vcnt, int &ecnt){
    seen[v] = 1;
    vcnt++;

    for(int i=0; i<G[v].size(); i++){
        int next = G[v][i];
        ecnt++;
        if(seen[next]){
            continue;
        }
        dfs(next, vcnt, ecnt);
    }
}

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

    int a, b;
    G.resize(n);
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    seen.resize(n);
    long long int sum = 0;
    for(int i=0; i<n; i++){
        if(seen[i]){
            continue;
        }

        int vcnt = 0, ecnt = 0;
        dfs(i, vcnt, ecnt);
        ecnt /= 2;
        sum += (long long int)vcnt*(vcnt-1)/2 - ecnt;
    }

    cout << sum << endl;
    return 0;
}

E: Toward 0

解法

  • メモ化再帰
  • 問題文から漸化式を考える
    • X 円を払う操作： f(N) = X + f(\lfloor \frac{N}{A} \rfloor)
    • Y 円を払う操作： f(N) = Y + \lbrace \frac{1}{6} f(\lfloor \frac{N}{1} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{6} \rfloor) \rbrace
      • 両辺に f(N) = f(\lfloor \frac{N}{1} \rfloor) があるため右辺の f(\lfloor \frac{N}{1} \rfloor) を移項すると \frac{5}{6} f(N) = Y + \lbrace \frac{1}{6} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{6} \rfloor) \rbrace
      • 両辺に \frac{6}{5} をかけて f(N) = \frac{6}{5} Y + \lbrace \frac{1}{5} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{6} \rfloor) \rbrace
  • f(N) = min(X + f(\lfloor \frac{N}{A} \rfloor), \frac{6}{5} Y + \lbrace \frac{1}{5} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{6} \rfloor) \rbrace)
  • 小数の扱いに注意する
ABC350E.cpp
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstdio>
using namespace std;

int a, x, y;
unordered_map<long long int, double> M;

double f(long long int n){
    if(n==0){
        return 0;
    }

    if(M.count(n)){
        return M[n];
    }

    return M[n] = min(x + f(n/a), (double)6/5*y + (double)1/5*f(n/2) + (double)1/5*f(n/3) + (double)1/5*f(n/4) + (double)1/5*f(n/5) + (double)1/5*f(n/6));
}

int main(){
    long long int N;
    cin >> N >> a >> x >> y;

    printf("%.10f\n", f(N));
    return 0;
}

Discussion