問題概要

本問題では、Rh陰性血（パンダ血）に関するデータを処理します。入力として与えられるパンダ血型データと、クエリとして与えられる血型データに対して、各クエリがパンダ血かどうかを判定し、全体のパンダ血の割合と最も頻繁にクエリされたパンダ血型を出力します。

入力形式

まず、N個のパンダ血型データが与えられます。Nは最大10,000です。次に、M個のクエリが与えられ、それぞれのクエリは8文字以内のアルファベットと数字で構成されます。Mは最大100,000です。

出力形式

1. 各クエリに対応する0または1の文字列（パンダ血なら1、そうでないなら0） 2. パンダ血を持つ人数の割合（小数点以下2桁） 3. 最も頻繁にクエリされたパンダ血型のID

サンプル入力

3
RH0ABP1
RH0APY
BPYORH0
9
BPYORH1
RH0ABP2
RH0APY
APYORH0
RH0OPY
BPYORH0
RH1APY
RH0APY
ABPYRH0

サンプル出力

001001010
33.33
RH0APY

解法

この問題を効率的に解くには、以下の手順を踏むことが推奨されます：

1. セットを使用してパンダ血型のデータを記録する。
2. 各クエリについて、セットに含まれているかを確認する。含まれている場合、対応するカウンタを増やし、結果文字列に1を追加。含まれていない場合は、結果文字列に0を追加。
3. 最終的に、パンダ血の割合と最も頻繁にクエリされた血型を計算し、出力する。

時間計算量は、セットの操作がO(log N)であるため、全体の計算量はO(M log N)になります。

実装例

#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;

int main() {
    int n, m;
    cin >> n;
    set<string> blood_types;
    map<string, int> query_counts;
    string blood_type;
    
    for (int i = 0; i < n; ++i) {
        cin >> blood_type;
        blood_types.insert(blood_type);
    }
    
    cin >> m;
    string result;
    int panda_count = 0;
    string most_frequent_type;
    int max_count = 0;
    
    for (int i = 0; i < m; ++i) {
        cin >> blood_type;
        if (blood_types.count(blood_type)) {
            result += "1";
            query_counts[blood_type]++;
            panda_count++;
            if (query_counts[blood_type] > max_count) {
                max_count = query_counts[blood_type];
                most_frequent_type = blood_type;
            }
        } else {
            result += "0";
        }
    }
    
    cout << result << endl;
    printf("%.2f\n", (double)panda_count / m * 100);
    cout << most_frequent_type << endl;
}