けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CODE FESTIVAL 2017 qual B B - Problem Set (4Q, 茶色, 200 点)

AtCoder AtCoder200点 AGC-B 茶色diff NoviSteps4Q 連想配列(setやmap) setやmap:検索や削除が速いこと 計算量改善:setやmapの活用 Yes/No判定問題 易しいYes/No判定問題

素朴な map の練習問題

問題概要

りんごさんは N 個の問題案を持っており、 i 個目の問題案の難易度は D_{i} である。

ここから、配点が T_{1}, T_{2}, \dots, T_{M} であるような M 問からなる問題セットを作ることは可能か？

制約

  • 1 \le N, M \le 2 \times 10^{5}
  • 1 \le T_{i}, D_{i} \le 10^{9}

考えたこと

連想配列 (C++ ならば map) の練習問題。次のような連想配列を用意しよう。

  • problems[x]：残っている問題案の中に、配点 x の問題は何問あるか？

そうして、 i = 1, 2, \dots, M に対して、problems[T[i]] の値を 1 減らしていけば良い。途中で負の値になったら不可能だとわかる。

計算量は O((N + M) \log N) となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, D, T;
    cin >> N;
    map<int, int> problems;
    for (int i = 0; i < N; i++) {
        cin >> D;
        problems[D]++;
    }

    cin >> M;
    bool res = true;
    for (int i = 0; i < M; i++) {
        cin >> T;
        problems[T]--;
        if (problems[T] < 0) res = false;
    }
    cout << (res ? "YES" : "NO") << endl;
}