034.md

034 - There are few types of elements (★4)

解答

#include <iostream>
#include <vector>
#include <unordered_map>

int main()
{
	// 長さ N の数列, 部分列に含む要素は K 種類以下
	int N, K;
	std::cin >> N >> K;

	std::vector<int> A(N);
	for (auto& a : A)
	{
		std::cin >> a;
	}

	///////////////////////
	//
	// 尺取り法
	// [left, right)
	//

	int right = 0;

	// 部分列の最長の長さを記録する変数
	int answer = 0;

	// 現在の部分列に含まれる整数の種類
	int count = 0;

	// 現在の部分列に含まれる整数とその個数
	std::unordered_map<int, int> m;

	for (int left = 0; left < N; ++left)
	{
		while (right < N)
		{
			// 新しく部分列に含めようとしている要素
			const int current = A[right];

			// 現在の部分列に整数 current が含まれていなければ
			if (m[current] == 0)
			{
				// 現在の部分列にすでに K 種類の整数があれば
				if (count == K)
				{
					// 新しく部分列を広げると, 種類数がオーバーしてしまう
					break; // while から抜ける
				}

				// 現在の部分列が含む整数の種類を 1 増やす
				++count;		
			}

			++m[current];

			// 部分列を右側に広げる
			++right;
		}

		// 部分列の長さを調べて, これまでの記録を超えていたら更新
		answer = std::max(answer, (right - left));

		// 部分列の左側の移動に伴い除外された整数が, 
		// 元の部分列に 1 個しか含まれていない整数だった場合
		if (--m[A[left]] == 0)
		{
			// 現在の部分列が含む整数の種類を 1 減らす
			--count;
		}
	}

	// 解答を出力
	std::cout << answer << '\n';
}