問題

問題文

N 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色1、色2、…、色10^9の、10^9種類の色のうちいずれかの色をしています。
i=1,2,…,Nについて、左から i 番目のキャンディの色は色 ci です。
高橋君は並んでいるキャンディのうち、連続して並んだ K 個のキャンディをもらうことができます。
すなわち、1≤i≤N−K+1を満たす整数 i を選んで、 左から i 番目、i+1番目、i+2番目、…、i+K−1番目のキャンディをもらうことができます。
高橋君はいろいろな色のキャンディを食べたいので、 もらうキャンディに含まれる色の種類数が多いほどうれしい気持ちになります。
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力してください。

制約

1 ≤ K ≤ N ≤ 3×10^5
1 ≤ ci ≤ 10^9
入力はすべて整数

考察

長さKの区間に含まれる色の種類数の最大値を求めます。この問題は愚直に計算していきますと、

K*(N-K)

回の計算で求めることが可能です。ちょっと計算の見積もりがややこしいですが、計算量は2乗のオーダーになりそうです。K=2.5*10^5,N=5*10^5のようなサンプルがあると流石に間に合いません。

ですので、C問題ではお馴染みの高速化をしましょう。今回は問題となるのは、

・KはN-K回ずらす必要がある（N-K回計算する必要がある）
・区間に含まれる色の種類数を判定するのにはK回の計算が必要

ということです。ですので、後者の「色の判定」に注目してみます。

今回は区間のKを一個ずらした時の変化を追っていきます。Kを一個ずらしますと、

1）長さKの区間の先頭の色がはみ出る
2）長さKの区間の次の色が加わる

この2つの変化が起こります。それ以外の色に関しては全く変わりません。ですので、長さKの区間に含まれている色を管理してあげれば、Kを変化させた時に、１）と２）だけ更新することで、あっという間に色数が分かります。図解すると次のような感じです。

こうなってしまえば、あとはKを端から端までずらして挙げれば全部のパターンが網羅できますので、そのうちの最大値を出力してあげれば答えになります。

実装に関して2点補足です。

１）色の管理にはmapを使う

色の範囲は10^9までありますので、この長さの配列を用意してしまうとメモリが足りなくなります。

２）Kの内部管理にはqueueかdequeを使う

配列でも同じような挙動を書くことができますが、配列番号の管理がややこしくなります。queueやdequeを使うとその点が非常に楽できますのでぜひともこちらを使いましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

int main()
{
   int n, k;
   cin >> n >> k;
   vector<int> c(n);
   rep(i, n) cin >> c[i];
   queue<int> q;
   map<int, int> mp;
   int now = 0;
   rep(i, k)
   {
       if (mp[c[i]] == 0) ++now;
       mp[c[i]]++;
       q.emplace(c[i]);
   }
   int ans = now;
   reps(i,k,n)
   {
       int p = q.front();
       q.pop();
       --mp[p];
       if (mp[p] == 0) --now;

       if (mp[c[i]] == 0) ++now;
       ++mp[c[i]];
       q.emplace(c[i]);
       ans = max(ans, now);
   }
   cout << ans << endl;
   return 0;
}

あとがき

こういう問題は尺取り法っていうのですかね。尺取り法の定義が余り分かっていませんが、区間をずらしながら先頭と末尾を操作していく感じです。補足でも書きましたが、queueやdequeを使うと非常に簡単に管理できますので、vectorで管理していた方もこれを機にぜひとも試してみてはいかがでしょうか。