AtCoder Beginner Contest 137 の振り返り

AtCoder Beginner Contest 137に参加したので備忘録。

急いでA〜Dまで解いた結果、パフォーマンス的には1600を超えていたので、安定して速く解けるようになると青になれるのかな。

A - +-x

実装のみのスピード勝負。

B - One Clue

これまたスピード勝負。

C - Green Bin

文字列のソートして、配列全体もソートして、あとは数え上げる。

D - Summer Vacation

公式の解説にも書いてあるけどM日後から逆に見ていくパターン。

日数を前にさかのぼっていって、選べる報酬額を全部プライオリティキューにいれていく。

typedef long long ll;

// 報酬でかい順に出てくるキュー
priority_queue<int> pq;

// 日数と報酬のマップ
map<int, vector<int> > mp;

int main(int argc, char *argv[]) {
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    mp[a].push_back(b);
  }
  ll res=0;
  for(int i=1;i<=m;i++){
    for(auto t : mp[i]) {
      pq.push(t);
    }
    if(pq.empty())continue;
    res+=pq.top();
    pq.pop();
  }
  cout<<res<<endl;

  return 0;
}

E - Coins Respawn

挑戦したけど本番中は解けず。復習した。

F - Polynomial Construction

そっ閉じした。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?