POJ1989 The Cow Lineup

問題

牛がN頭ならんでおり、各牛は1〜Kまでの番号が付けられている。
各牛の並びが与えられるので、先頭から適当に牛を選んでその番号を使って作ることができるの部分列をK+1進数の数字とみなした場合、作ることができない数字のケタ数を返す。

N<=10^5
K<=10^4

考え方

ある牛i以降でM桁のK+1進数がすべて作れる場合、0〜i-1まででM+1桁目の1〜Kが出てきていればM+1桁を作ることができる。
ここで、M+2桁目以上のことを考えると、M+1桁のとき1〜Kまですべてが出てくるできるだけ後ろのインデクスでM+1桁が作れた方がよい。

なので、配列の後ろから前方向に1〜Kがすべてでてくる塊がいくつ作れるか？を数えればよい。
適当にvectorやbool配列などで番号jがすでに出てきているか保存し、でていなければ入れて、異なり数を+1、リセットするときは、fill()などで値をクリアすればよい。
または、fillしないで、埋める時桁数で埋めてあげれば区別できる。

面倒で、mapでsizeがKになるたびにclearしていたらTLEしてしまったので、N個map作ったら通ってしまった・・・