問題の説明

霊夢は n 個の単語を覚えたいのですが、一つの文章の一部分を通じてこれらの単語を覚えようとしています。文章は m 個の単語から構成されており、彼女は文章の中から連続した一部分を見つけ出し、その中に含まれる覚えたい単語の数を最大にしたいと考えています（重複する単語は一つとしてカウントします）。そして、覚える単語の数を最大にした上で、選んだ文章の部分の長さをできるだけ短くすることで、より短い時間でより多くの単語を学習できるようにしたいと考えています。

入力形式

第1行に一つの整数 n が与えられます。次の n 行に、長さが10以下の文字列が一つずつ与えられ、覚えたい単語を表します。その後、一つの整数 m が与えられ、続く m 行に長さが10以下の文字列が一つずつ与えられ、文章の各単語を表します。

出力形式

出力は2行からなります。第1行には、文章の中で含まれる覚えたい単語の最大数を出力します。第2行には、覚えたい単語を最大数含む最短の連続した部分の長さを出力します。

入出力サンプル #1

入力 #1

3
hot
dog
milk
5
hot
dog
dog
milk
hot

出力 #1

3
3

データの規模と制約

• 30% のデータにおいて、n ≤ 50、m ≤ 500。
• 60% のデータにおいて、n ≤ 300、m ≤ 5000。
• 100% のデータにおいて、1 ≤ n ≤ 1000、1 ≤ m ≤ 10^5。

問題の理解

この問題の目的は二つあります。

1. 文章の中から連続した部分（部分配列）を見つけ、その中に含まれる異なる「覚えたい単語」の数を可能な限り多くすること。
2. 上記の条件を満たす部分の中から、長さが最も短いものを選び、その長さを出力すること。

部分の長さは、その連続した部分の単語の数で定義されます。

解法のアイデア

この問題は、スライディングウィンドウ（二重ポインタ）というアルゴリズムで効率的に解くことができます。覚えたい単語の集合と、現在のウィンドウ内の各単語の出現回数を管理しながら、ウィンドウを動かして最適な解を探索します。

コードの分析

以下のコードは、上記のアイデアを実装したものです。主要な部分は、二重ポインタ（leftPtr と rightPtr）を使用して文章をスキャンし、ウィンドウを動的に調整する部分です。

解答コード

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n;

    // 覚えたい単語をセットに格納
    std::unordered_set<std::string> targetWords;
    for (int i = 0; i < n; ++i) {
        std::string word;
        std::cin >> word;
        targetWords.insert(word);
    }

    std::cin >> m;
    std::vector<std::string> articleWords(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> articleWords[i];
    }

    // 現在のウィンドウ内の単語の出現回数を管理
    std::unordered_map<std::string, int> wordCounts;
    int leftPtr = 0;
    int currentUniqueCount = 0;
    int maxUniqueCount = 0;
    int minSegmentLength = m + 1; // 初期値は大きな値

    // 右ポインタで文章をスキャン
    for (int rightPtr = 0; rightPtr < m; ++rightPtr) {
        const std::string& currentWord = articleWords[rightPtr];

        // 覚えたい単語であれば、カウントを増やす
        if (targetWords.count(currentWord)) {
            wordCounts[currentWord]++;
            // この単語がウィンドウ内で初めて出現する場合
            if (wordCounts[currentWord] == 1) {
                currentUniqueCount++;
            }
        }

        // 現在のウィンドウが全ての覚えたい単語を含んでいる場合、
        // 左ポインタを動かしてウィンドウを最小化を試みる
        while (currentUniqueCount == targetWords.size()) {
            // 現在のウィンドウの長さをチェック
            int currentLength = rightPtr - leftPtr + 1;
            if (currentLength < minSegmentLength) {
                minSegmentLength = currentLength;
            }

            // 左端の単語をウィンドウから除外
            const std::string& leftWord = articleWords[leftPtr];
            if (targetWords.count(leftWord)) {
                wordCounts[leftWord]--;
                // もし単語が出現しなくなったら、ユニークカウントを減らす
                if (wordCounts[leftWord] == 0) {
                    currentUniqueCount--;
                }
            }
            leftPtr++;
        }

        // 新しい最大ユニーク数が見つかった場合、最小長をリセット
        if (currentUniqueCount > maxUniqueCount) {
            maxUniqueCount = currentUniqueCount;
            minSegmentLength = rightPtr - leftPtr + 1;
        }
    }

    std::cout << maxUniqueCount << std::endl;
    std::cout << minSegmentLength << std::endl;

    return 0;
}