AtCoder abc245 参加メモ

AtCoder Beginner Contest 245 - AtCoder の参加メモ

C - Choose Elements

直前の条件を満たす数を記憶しておいて、Nまで遷移可能であればYes

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

  set<int> st = { a[0], b[0] };
  REP(i,n-1) {
    set<int> nst;
    for(int v: st) {
      if ( abs(v-a[i+1]) <= k ) nst.insert(a[i+1]);
      if ( abs(v-b[i+1]) <= k ) nst.insert(b[i+1]);
    }
    swap(st,nst);
  }

  cout << (st.size() ? "Yes" : "No") << endl;
  return 0;
}

D - Polynomial division

$c / a$の割り算を高次の項からやっていく

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

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(n+1),c(n+m+1),b(m+1);
  REP(i,n+1) cin >> a[i];
  REP(i,n+m+1) cin >> c[i];
  reverse(a.begin(),a.end());
  reverse(c.begin(),c.end());

  REP(i,m+1) {
    b[i] = c[i] / a[0];
    REP(j,n+1) c[i+j] -= a[j] * b[i];
  }

  reverse(b.begin(),b.end());
  for(int v: b) cout << v << endl;
  return 0;
}

E - Wrapping Chocolate

Greedy。箱とチョコレートをそれぞれ高さで降順ソートする。大きいチョコレートから、高さがそのチョコレート以上の箱のうち、一番小さい箱を貪欲に選んでいく。最後まで遷移できたらYes

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

int main() {
  int n,m; cin >> n >> m;
  vector<pair<int,int>> p(n),q(m);
  REP(i,n) cin >> p[i].first;
  REP(i,n) cin >> p[i].second;
  REP(i,m) cin >> q[i].first;
  REP(i,m) cin >> q[i].second;

  sort(p.rbegin(),p.rend());
  sort(q.rbegin(),q.rend());

  int qi = 0;
  multiset<int> s;
  for(auto [x,y]: p) {
    while(qi < m) {
      auto [qx,qy] = q[qi];
      if (qx < x) break;
      s.insert(qy);
      qi++;
    }

    auto it = s.lower_bound(y);
    if (it == s.end()) {
      cout << "No" << endl;
      return 0;
    }
    s.erase(it);
  }

  cout << "Yes" << endl;
  return 0;
}