AtCoder abc252 参加メモ

AtCoder Beginner Contest 252 - AtCoder の参加メモ

B - Takahashi's Failure

#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<int> a(n),b(k);
  int mx = -1;
  REP(i,n) { cin >> a[i]; mx = max(mx,a[i]); }
  REP(i,k) { cin >> b[i]; b[i]--; }

  bool yes = false;
  REP(i,n) {
    if (mx != a[i]) continue;
    REP(j,k) yes |= (i == b[j]);
  }

  cout << (yes ? "Yes" : "No") << endl;
  return 0;
}

C - Slot Strategy

• 0〜9それぞれで揃える最短ケースを求める
• 同じ時間に複数押せる候補がある場合は、どれから押しても問題はない

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

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

  int ans = 1e9;
  REP(x,10) {
    vector<bool> m(n);
    int cnt = 0;
    REP(t,n*10) {
      REP(i,n) {
        if (m[i] || x != s[i][t%10] - '0') continue;
        m[i] = true;
        cnt++;
        break;
      }
      if (cnt == n) { ans = min(ans,t); break; }
    }
  }

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

D - Distinct Trio

• 解説にある通り、 問題文を $ A_i < A_j < A_k A を満たす (i,j,k) の組の個数を求めよ $ に読み変えることができれば簡単になる

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

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

  ll ans = 0;
  for(int j = 1; j < n; j++) {
    auto it1 = lower_bound(a.begin(), a.begin()+j, a[j]) - 1;
    auto it2 = upper_bound(a.begin()+j, a.end(), a[j]);
    ans += (it1 - a.begin() + 1) * (n - (it2 - a.begin()));
  }
  cout << ans << endl;
  return 0;
}