AtCoder abc342 参加メモ

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342） - AtCoder

B - Which is ahead?

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<int> p(n);
  REP(i,n) cin >> p[i];
  vector<int> m(n+1);
  REP(i,n) m[p[i]] = i;
  int q; cin >> q;
  REP(_,q) {
    int a,b; cin >> a >> b;
    int v1 = m[a], v2 = m[b];
    if (v1 > v2) swap(a,b);
    cout << a << endl;
  }
  return 0;
}

C - Many Replacement

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,q; string s;
  cin >> n >> s >> q;
  vector<char> c(26);
  REP(i,26) c[i] = char('a' + i);
  REP(_,q) {
    char a,b; cin >> a >> b;
    REP(i,26) if (c[i] == a) c[i] = b;
  }
  for(auto v: s) cout << c[v-'a'];
  return 0;
}

D - Square Pair

A について素因数分解して平方数で割った残りの数を計算する。 map でその数をカウントしておいて、各値xに対して (map[x] * (map[x]-1)) / 2 の数だけ組み合わせが作れる。 0 のケースの扱いに気をつける。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

vector<ll> prime_factorize(ll n) {
  vector<ll> res;
  for(ll a = 2; a*a <= n; a++) {
    if (n%a != 0) continue;
    ll ex = 0;
    while(n%a == 0) { ex++; n /= a; }
    if (ex % 2) res.emplace_back(a);
  }
  if (n != 1) res.emplace_back(n);
  return res;
}

int main() {
  int n; cin >> n;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];

  map<ll,ll> mp;
  REP(i,n) {
    auto pf = prime_factorize(a[i]);
    ll now = 1;
    for(auto v: pf) now *= v;
    mp[now]++;
  }

  ll ans = 0;
  for(auto [k,v]: mp) {
    if (k == 0) ans += (n-1)*v;
    else ans += (mp[0] + (v-1))*v;
  }
  cout << ans/2 << endl;
  return 0;
}