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' をテンプレに追加した