AtCoder abc249 参加メモ

Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） - AtCoder の参加メモ

B - Perfect String

• 大文字、小文字の判定
• 配列のユニーク判定

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

int main() {
  string s; cin >> s;
  int n = s.size();
  bool l = false, u = false;
  set<char> st;
  for(char c: s) {
    if ('a' <= c && c <= 'z') l = true;
    if ('A' <= c && c <= 'Z') u = true;
    st.insert(c);
  }

  bool ok = l && u && (int)st.size() == n;
  cout << (ok ? "Yes" : "No") << endl;

  return 0;
}

C - Just K

• bit全探索

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

int main() {
  int n,k; cin >> n >> k;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  int ans = 0;
  REP(bit, (1<<n)) {
    vector<int> m(26);
    REP(i,n) {
      if (bit >> i & 1) {
        for(auto c: s[i]) m[c-'a']++;
      }
    }
    int cnt = 0;
    for(int v: m) if (v == k) cnt++;
    ans = max(ans,cnt);
  }

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

D - Index Trio

• 約数列挙
• 数え上げ

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

vector<int> divisor(int n) {
  vector<int> res;
  for(int i = 1; i*i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n/i) res.push_back(n/i);
    }
  }
  return res;
}

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

  vector<int> m(200001);
  vector<bool> used(200001);
  REP(i,n) m[a[i]]++;

  ll ans = 0;
  for(int i: a) {
    if (used[i]) continue;
    used[i] = true;
    for(int j: divisor(i)) {
      int k = i / j;
      ans += (ll)m[i] * m[j] * m[k];
    }
  }
  cout << ans << endl;
  return 0;
}