同じ文字の個数をカウントしたい

Question

＜問題例＞
「以下の入力が与えられます。各Kjにつき、数列A内に存在する各Kjの個数（Kj = AiとなるようなAiの個数）を出力してください。」
N, M, X
A1, A2, ... , Ai, ... , An （1 <= Ai <= X）
K1, K2, ... , Kj, ... , Km
（1 <= N <= 10^5, 1 <= M <= 10^4, 1 <= X <= 10^5）

＜入力例＞
5 3 9
2 1 2 7 4
7 2 3
（答え：1 2 0）

これをバケットで考えて計算量をO(N+M)にしたコードは

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

int main(){
  int n,m,x;
  cin >> n >> m >> x;
  vector<int> buckets(10,0);
  for (int i=0;i<n;++i){
      int a; cin >> a;
      buckets[a]++;
  }
  for (int j=0;j<m;++j){
      int k; cin >> k;
      cout << buckets[k] << endl;
  }
}

のようにできたのですが計算量O(N*M)の2重ループでの実装ができません。

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

int main(){
  int n,m,x;
  cin >> n >> m >> x;
  vector<int> a(n),k(m);
  for (int i=0;i<n;++i) cin >> a[i];
  for (int j=0;j<m;++j) cin >> k[j];
  
  for (int j=0;j<m;++j){
      for (int i=0;i<n;++i){
          //処理
      }
  }
  cout <<  << endl;
}

上記のようなコードになるかと思うのですが処理に何を書けば実現できるか教えてくださると嬉しいです。よろしくお願い致します。

Comments

[kazuma-s]

bucket の宣言で x が使われていませんが、
vector<int> buckets(x+1, 0); ですよね。

[cunwe]

確かにそうですね、ご指摘ありがとうございます。

Answer 1

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

int main(){
  int n,m,x;
  cin >> n >> m >> x;
  vector<int> a(n),k(m);
  for (int i=0;i<n;++i) cin >> a[i];
  for (int j=0;j<m;++j) cin >> k[j];

    for ( int kj : k ) {
      cout << count(begin(a), end(a), kj) << ' ';
    }
    cout << endl;
}

Comments

[cunwe]

それでも通りますね、簡潔すぎてビビりました。毎回勉強させていただいてます。今回もありがとうございました。

Answer 2

問題文そのまま「各Kjにつき、数列A内に存在する各Kjの個数」を数えるコードを書けば良いと思います

int main(){
  int n,m,x;
  cin >> n >> m >> x;
  vector<int> a(n),k(m);
  for (int i=0;i<n;++i) cin >> a[i];
  for (int j=0;j<m;++j) cin >> k[j];

  for (int j=0;j<m;++j){
    int count_kj = 0;
    for (int i=0;i<n;++i){
      //処理
    }
    cout << count_kj << endl;
  }
  
}

Comments

[cunwe]

処理にif (k[j]==a[i]) count_kj++;を書くだけですね。。ありがとうございました。