AtCoder abc250 参加メモ

AtCoder Beginner Contest 250 - AtCoder の参加メモ

B - Enlarged Checker Board

適当に実装してif文だらけになるとバグらせやすいので注意する。

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

int main() {
  int n,a,b; cin >> n >> a >> b;

  REP(i,n) REP(_i,a) {
    REP(j,n) REP(_j,b) {
      cout << ((i%2) ^ (j%2) ? "#" : ".");
    }
    cout << endl;
  }
}

C - Adjacent Swaps

右端は左端と交換と読み違えないように問題文はちゃんと読もう

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

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

  REP(i,q) {
    int x; cin >> x;
    x--;
    int idx = pos[x];
    int nidx = (idx == n-1) ? idx-1 : idx+1;

    swap(s[idx], s[nidx]);
    swap(pos[s[idx]], pos[s[nidx]]);
  }

  REP(i,n) cout << s[i]+1 << " ";
  cout << endl;
  return 0;
}

D - 250-like Number

素数列挙
二分探索
条件を満たす素数が10⁶以下であることに気づけるかどうか

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

vector<int> eratosthenes(int n) {
  vector<int> p, is_prime(n+1, 1);
  for(int i=2; i<=n; i++) {
    if(is_prime[i]) {
      for(int j=2*i; j<=n; j+=i) is_prime[j] = 0;
      p.push_back(i);
    }
  }
  return p;
}

ll n;
bool f(ll p, ll q) {
  REP(_,3) {
    if (n/q < p) return false;
    p *= q;
  }
  return true;
}

int main() {
  cin >> n;
  auto p = eratosthenes(1e6);
  p.push_back(1e9);
  int sz = p.size();

  ll ans = 0;
  REP(i,sz) {
    int ok = i;
    int ng = sz-1;
    while (abs(ok-ng)>1) {
      int mid = (ok+ng)/2;
      if (f(p[i],p[mid])) ok = mid;
      else ng = mid;
    }
    ans += ok - i;
  }

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

E - Prefix Equality

他にも解法は色々ありそうだが今回取った方針は

整数列A,Bに対して0...N 各時点での集合の合計値とサイズを記録しておく
整数列Aに対してある数が最初に集合に追加される位置を記録しておく
Q個のクエリに対して、集合Ax,Byの合計値とサイズが同じ、かつByの値が集合Axに一つでも含まれていればYes

#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),b(n);
  REP(i,n) cin >> a[i];
  REP(i,n) cin >> b[i];
  int q; cin >> q;

  vector<pair<ll,int>> ma(n+1), mb(n+1); // ma[i] = { i番目の集合の和, i番目の集合のサイズ }
  map<int,int> mp; // [i] = 最初にiが出た位置
  unordered_set<int> sa,sb;

  REP(i,n) {
    ma[i+1] = ma[i];
    mb[i+1] = mb[i];
    if (!sa.count(a[i])) {
      sa.insert(a[i]);
      ma[i+1].first += a[i];
      ma[i+1].second++;
      mp[a[i]] = i+1;
    }
    if (!sb.count(b[i])) {
      sb.insert(b[i]);
      mb[i+1].first += b[i];
      mb[i+1].second++;
    }
  }

  REP(i,q) {
    int x,y; cin >> x >> y;
    int pos = mp[b[0]];
    bool ok = ma[x] == mb[y] && 0 < pos && pos <= x;

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