POJ 1989 The Cow Lineup

問題
http://poj.org/problem?id=1989
(翻訳)K種類の整数N個からなる整数列が与えられるので、その部分列とならない整数列のうち最短のものの長さを答えろ。
解法
整数列の先頭から、K種類の整数が一通り出るところまで進み、さらにその場所からまたK種類の整数が出そろうところまで進み...を繰り返していき、繰り返した数+1が答え。

適当な証明
上のアルゴリズムをn回繰り返したとする。
入力の整数列を繰り返しによって進んだところで切って、整数列の集合{s1, s2, ... ,sn}が出来る。(全てのsはそれぞれK種類の整数を全て含んでいる)

まず、長さn以下の任意の整数列が{s}に部分列として出現することを示す。
整数列{a1, a2, ... , ai} (i <= n)とおくと、整数列s1は全ての種類の整数を含んでいるので、当然a1もs1の要素である。
同様にajはsjの要素である。
従って、a1∈s1, a2∈s2, ... ,ai∈si となるのでsから適当に要素を選ぶことにより、{s}から長さn以下の任意の整数列を部分列として作ることが出来る。

次に、長さn+1で{s}の部分列でない整数列を作ることが出来ることを示す。
各sの末尾の整数は1回しか現れない（∵そうでないと、アルゴリズムでK種類の整数がちょうど出そろうところまで進むことに矛盾する）
各sから末尾の整数を取り出して出来た整数列を{b1, b2, ... , bn} とする。
この整数列は{s}の部分列として一つだけ存在する。
ここで入力の整数列にアルゴリズムを実行して余った部分（bnの末尾以降）に出現しない整数を{b}の末尾に加えると
{b1, b2, ... , bn, bn+1}となる。
bn+1はbn以降には存在しない整数だから{b1, b2, ... , bn, bn+1}は{s}の部分列としては存在しない。

以上よりn+1が最小の長さであることが示された。
終わり

#include <cstdio>
#include <algorithm>
using namespace std;

int N, K;
bool used[10000];
int m;
int main(){
	scanf("%d %d", &N, &K);
	int ans = 0;
	m = 0;
	for(int i = 0; i < N; i++){
		int t;
		scanf("%d", &t);
		if(!used[t-1]){
			used[t-1] = true;
			m++;
			if(m == K){
				ans++;
				m = 0;
				fill(used, used + K, false);
			}
		}
	}
	printf("%d\n", ans + 1);
	return 0;
}