【ABC342】AtCoder Beginner Contest 342【C++】

コンテスト名

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）

コンテストURL

開催日

2024/02/24 21:00-22:40

---

A: Yay!

解法

• 異なる文字は 1 文字であるため当該文字は必ず前後の文字と異なる
  • 前後の文字と比較して異なるものを見つける
  • 1 文字目と最後の文字は別に処理する

ABC342A.cpp

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

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

    for(int i=1; i<s.size()-1; i++){
        if(s[i]!=s[i-1] && s[i]!=s[i+1]){
            cout << i+1 << endl;
            return 0;
        }
    }

    if(s[0]!=s[1]){
        cout << 1 << endl;
        return 0;
    }
    if(s[s.size()-1]!=s[s.size()-2]){
        cout << s.size() << endl;
        return 0;
    }
}

B: Which is ahead?

解法

• 人の番号 $P_i$ をインデックスにして並び順の番号 $i$ をもつ
  • $Q[P_i] = i$

ABC342B.cpp

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

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

    vector<int> P(n+1);
    int x;
    for(int i=1; i<=n; i++){
        cin >> x;
        P[x] = i;
    }

    int q;
    cin >> q;
    int a, b;
    for(int i=0; i<q; i++){
        cin >> a >> b;
        if(P[a]<P[b]){
            cout << a << endl;
        }else{
            cout << b << endl;
        }
    }

    return 0;
}

C: Many Replacement

解法

• アルファベット 26 文字 abcdefghijklmnopqrstuvwxyz の配列で先にシミュレーションしてから最後に反映させる
• 計算量はアルファベットの文字数を $\alpha = 26$ とおくと $O(\alpha Q + N)$
  • 直接操作すると $O(QN)$ になってしまう

ABC342C.cpp

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

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

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

    char c, d;
    for(int i=0; i<q; i++){
        cin >> c >> d;

        int num1 = (int)(c - 'a');
        int num2 = (int)(d - 'a');

        
        for(int i=0; i<26; i++){
            if(A[i]==num1){
                A[i] = num2;
            }
        }
    }

    for(int i=0; i<n; i++){
        int num = (int)(s[i] - 'a');

        cout << (char)('a' + A[num]);
    }

    cout << endl;
    return 0;
}

D: Square Pair

解法

• 各整数を平方数で割れるだけ割る
• $A_i, A_j$ をそれぞれ平方数で割れるだけ割った数 $A_i' = A_j'$ ならば $A_i A_j$ は平方数になる
• 平方数で割れるだけ割ったあとの数をキーにして unordered_map でそれぞれの個数を管理する
• 平方数になる組み合わせの数はそれぞれ ${}_n \mathrm{C}_2$ で求められる
• いずれかが 0 の場合は必ず平方数になるので別に処理する

ABC342D.cpp

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

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

    for(int i=0; i<n; i++){
        for(int j=(int)pow(A[i], 0.5); j>=2; j--){
            while(A[i]%(j*j)==0){
                A[i] /= (j*j);
            }
        }
    }

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

    long long int ans = 0;
    ans += (M[0]*(M[0]-1))/2;
    ans += M[0]*(n-M[0]);
    for(unordered_map<int, long long int>::iterator it=M.begin(); it!=M.end(); it++){
        if(it->first!=0){
            ans += (it->second*(it->second-1))/2;
        }
    }

    cout << ans << endl;
    return 0;
}