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; }