AtCoder abc260 参加メモ
AtCoder Beginner Contest 260 - AtCoder
B - Better Students Are Needed!
- sortする際に
同点の場合は番号の小さい方を優先するとなっていることに気をつける
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' using P = pair<int,int>; int main() { int n,x,y,z; cin >> n >> x >> y >> z; vector<int> a(n),b(n); REP(i,n) cin >> a[i]; REP(i,n) cin >> b[i]; vector<P> ap(n),bp(n),abp(n); REP(i,n) { ap[i] = {a[i],-i}; bp[i] = {b[i],-i}; abp[i] = {a[i]+b[i],-i}; } sort(ap.rbegin(),ap.rend()); sort(bp.rbegin(),bp.rend()); sort(abp.rbegin(),abp.rend()); set<int> st; REP(i,x) st.insert(-ap[i].second); REP(i,n) { if ((int)st.size()-x == y) break; st.insert(-bp[i].second); } REP(i,n) { if ((int)st.size()-(x+y) == z) break; st.insert(-abp[i].second); } for(int v: st) cout << v+1 << endl; return 0; }
C - Changing Jewels
#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,x,y; cin >> n >> x >> y; vector<ll> r(n+1), b(n+1); r[n] = 1; for(int i = n; i > 1; i--) { // red r[i-1] += r[i]; b[i] += r[i] * x; // blue r[i-1] += b[i]; b[i-1] += b[i] * y; } cout << b[1] << endl; return 0; }
D - Draw Your Cards
- 二分探索
- 場に見えている表向きのカードをうまく管理する
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' int main() { int n,k; cin >> n >> k; set<int> st; vector<vector<int>> g(n); vector<int> ans(n,-1); REP(i,n) { int p; cin >> p; p--; auto it = st.upper_bound(p); if(it == st.end()) { st.insert(p); } else { swap(g[*it],g[p]); st.erase(*it); st.insert(p); } g[p].push_back(p); if ((int)g[p].size() == k) { for(int v: g[p]) ans[v] = i+1; st.erase(p); } } for(int v: ans) cout << v << endl; return 0; }
雑感
今更endlの遅さに気づいたので、#define endl '\n' をテンプレに追加した