問題概要

$N$ 本のパスタがあって、それぞれ長さは $A_{1}, A_{2}, \dots, A_{N}$ である。

高橋君は $M$ 日間パスタを食べる。 $1, 2, \dots, M$ 日目にはそれぞれ長さが $B_{1}, B_{2}, \dots, B_{M}$ であるようなパスタを食べたい。

一度食べたパスタは無くなってしまう。

高橋君が全 $M$ 日間、食べたいパスタを食べられるかどうかを判定してください。

制約

$1 \le M \le N \le 1000$

解法 (1)：各パスタが残っているかを管理する

たとえば、

$A = (3, 1, 4, 1, 5)$
$B = (1, 3, 5, 1)$

としてみましょう。

高橋君は 1 日目には長さが 1 であるパスタが食べたいです。そのようなパスタは 2 本あるので、そのうちの 1 本を食べることにします (どっちを食べてもよい)。2日目は長さが 3 のパスタが食べたいので食べます......といったことを繰り返して、この場合は 4 日間すべて食べたい長さのパスタを食べることができたので "Yes" を返します。

フラグ配列

以上のロジックを実装するためには、「各パスタがまだ残っているかを管理するフラグ配列」があるとよいでしょう。下図のように、長さ $N$ の配列を用意して、

パスタが残っているとき：true
パスタが残っていないとき：false

というようにします。

これで実装できます。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];
    
    // パスタが残っているか
    vector<bool> can(N, true);
    
    // M 日間食べていく
    for (int i = 0; i < M; ++i) {
        // 長さ B[i] のパスタを探す
        int j;
        for (j = 0; j < N; ++j) {
            if (can[j] && A[j] == B[i]) break;
        }
        
        // なかったらダメ
        if (j == N) {
            cout << "No" << endl;
            return 0;
        }
        
        // 一度食べたらもう食べられない
        can[j] = false;
    }
    
    // 完遂したら Yes
    cout << "Yes" << endl;
}

解法 (2)：map や Counter を使って集計する

もう一つ、標準ライブラリを使いこなせるならより簡単にできる方法もあります。たとえば、

$A = (3, 1, 4, 1, 1, 3)$
$B = (1, 3, 1, 3, 3)$

としてみましょう。パスタの長さごとに個数を求めます。そうすると、

用意されているパスタ：(長さ 1 が 3 個), (長さ 3 が 2 個), (長さ 4 が 1 個)
食べたいパスタ：(長さ 1 が 2 個), (長さ 3 が 3 個)

というようになります。これらの個数を比較しましょう。長さ 1 のパスタについては、2 個食べたいのに対して 3 個用意されているので大丈夫。しかし、長さ 3 のパスタについては、3 個食べたいのに 2 個しかないのでダメ。よって、答えは "No" となります。

一般に、全ての長さについて、

(用意されているパスタの本数) ≧ (食べたいパスタの個数)

であれば "Yes" と言えます。そうでなければ "No" です。

パスタの本数を長さごとに集計するためには、C++ では map 型、Python では Counter を使うのが便利です。C++ については、次のコードで map 型の使い方を感じ取っていただけたらと思います。Python についてはここに解説があります。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    
    // 用意パスタ (prepare[長さ] = 個数)
    map<int,int> prepare;
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        ++prepare[a];
    }
    
    // 食べたいパスタ (want[長さ] = 個数)
    map<int,int> want;
    for (int i = 0; i < M; ++i) {
        int b; cin >> b;
        ++want[b];
    }
 
    // 食べたいパスタの個数が充足されているかを調べる
    bool res = true;
    for (auto [length, num] : want) {
        if (prepare[length] < num) res = false;
    }
    cout << (res ? "Yes" : "No") << endl;
}