【ABC393】AtCoder Beginner Contest 393【C++】

コンテスト名

AtCoder Beginner Contest 393

コンテストURL

https://atcoder.jp/contests/abc393

開催日

2025/02/15 21:00-22:40

---

A: Poisonous Oyster

解法

• 4 通りをすべて列挙して判定する

ABC393A.cpp

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

int main(){
    string s1, s2;
    cin >> s1 >> s2;

    if(s1=="fine" && s2=="fine"){
        cout << 4 << endl;
    }else if(s1=="fine" && s2=="sick"){
        cout << 3 << endl;
    }else if(s1=="sick" && s2=="fine"){
        cout << 2 << endl;
    }else{
        cout << 1 << endl;
    }

    return 0;
}

B: A..B..C

解法

• A、B、C の位置をそれぞれ記録し、3 重ループで全探索する

ABC393B.cpp

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

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

    vector<int> A, B, C;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='A'){
            A.push_back(i);
        }else if(s[i]=='B'){
            B.push_back(i);
        }else if(s[i]=='C'){
            C.push_back(i);
        }
    }

    int cnt = 0;
    for(int i=0; i<A.size(); i++){
        for(int j=0; j<B.size(); j++){
            for(int k=0; k<C.size(); k++){
                if(A[i]<B[j] && B[j]<C[k] && B[j]-A[i]==C[k]-B[j]){
                    cnt++;
                }
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

C: Make it Simple

解法

• set<pair<int, int>> に辺を記録する
  • $u_i \leqq v_i$ となるようにしてから記録する
• 自己ループは不要であるため、記録せずに無視する

ABC393C.cpp

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

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

    int u, v;
    set<pair<int, int>> S;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        u--;
        v--;

        if(u==v){
            continue;
        }

        if(u>v){
            swap(u, v);
        }
        S.emplace(u, v);
    }
    
    cout << m - S.size() << endl;

    return 0;
}

D: Swap to Gather

解法

• 1 だけを抜き出した配列を考えたときの中央値の位置にすべての 1 を集める

ABC393D.cpp

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

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

    vector<int> V;
    for(int i=0; i<n; i++){
        if(s[i]=='1'){
            V.push_back(i);
        }
    }

    int size = V.size();
    int mid = V[size/2];

    long long int cnt = 0;
    if(size%2==0){
        int half = size/2;
        for(int i=0; i<half; i++){
            cnt += (mid-half+i) - V[i];
        }
        for(int i=half+1; i<V.size(); i++){
            cnt += V[i] - (mid+half-1-(size-i-1));
        }
    }else{
        int half = size/2;
        for(int i=0; i<half; i++){
            cnt += (mid-half+i) - V[i];
        }
        for(int i=half; i<V.size(); i++){
            cnt += V[i] - (mid+half-(size-i-1));
        }
    }

    cout << cnt << endl;

    return 0;
}

E: GCD of Subset

解法

• 動的計画法 (DP)
• $C[i]$ := $A$ に含まれる $i$ の倍数の個数
• $V[i]$ := $i$ を含むように $K$ 個の要素を $A$ から選ぶときの最大公約数の最大値

ABC393E.cpp

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

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

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

    int maxv = *max_element(A.begin(), A.end());
    vector<int> C(maxv+1);
    for(int i=0; i<n; i++){
        C[A[i]]++;
    }
    for(int i=1; i<=maxv; i++){
        for(int j=2; j<=maxv/i; j++){
            C[i] += C[i*j];
        }
    }

    vector<int> ans(maxv+1);
    for(int i=1; i<=maxv; i++){
        if(C[i]>=k){
            ans[i] = i;
        }
    }
    for(int i=maxv; i>=1; i--){
        for(int j=2; j<=maxv/i; j++){
            ans[i*j] = max(ans[i*j], ans[i]);
        }
    }
    
    for(int i=0; i<n; i++){
        cout << ans[A[i]] << '\n';
    }

    return 0;
}