yukicoder : No.2735 Demarcation

最初問題文の理解に手間取った。
https://yukicoder.me/problems/no/2735

問題

整数列Aが与えられる。
以下のクエリに順次答えよ。

• 部分列B=A[L..R]と、正整数Sが指定される。
• f(k)を、Bを複数の連続部分列に分割するとき、各連続部分列がk種類以下の値で構成されるような分割の仕方とする。f(k)≦Sとなるkの最大値を求めよ。

解法

f(2)はfib(|B|)以上である。Sの上限が2^60以下であることから、|B|がある程度大きいとf(2)＞Sであることが確定する。

• |B|が大きい場合、f(1)≦Sかどうかを判定すればよい。f(1)は、B[i]=B[i+1]となるiの個数をnとしたとき2^n通りなので、B[i]=B[i+1]となるiの累積和をあらかじめ求めておけばO(1)で処理できる。
• |B|が小さい場合、kを2分探索しよう。kが定まれば尺取り法の要領でO(|B|)のDPでf(k)を求めることができる。

int N,Q;
int X[1010101];
int same[1010101];
ll S;
int L,R;

ll dp[101];
int num[1010101];
ll hoge(int k,vector<int>& V) {
	int i;
	int B=V.size();
	dp[0]=1;
	ll sum=1;
	int cnum=0;
	int cur=1,pre=0;
	FORR(v,V) num[v]=0;
	for(;cur<=B;cur++) {
		if(num[V[cur-1]]++==0) cnum++;
		while(cnum>k) {
			sum-=dp[pre];
			if(--num[V[pre]]==0) cnum--;
			pre++;
		}
		dp[cur]=sum;
		if(sum>1LL<<60) return sum;
		sum+=dp[cur];
	}
	return dp[B];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i];
		if(i) same[i]=same[i-1]+(X[i]==X[i-1]);
	}
	cin>>Q;
	while(Q--) {
		cin>>L>>R>>S;
		L--;
		if(R-L>=100) {
			int cand=same[R-1]-same[L];
			if(cand>=61||S<(1LL<<cand)) {
				cout<<0<<endl;
			}
			else {
				cout<<1<<endl;
			}
			continue;
		}
		vector<int> V;
		for(i=L;i<R;i++) V.push_back(X[i]);
		int TL=0,TR=V.size()+2;
		while(TL+1<TR) {
			int TM=(TL+TR)/2;
			ll ret=hoge(TM,V);
			if(ret<=S) {
				TL=TM;
			}
			else {
				TR=TM;
			}
		}
		if(TL>V.size()) {
			cout<<-1<<endl;
		}
		else {
			cout<<TL<<endl;
		}
		
	}
}

まとめ

f(1)の扱いとか丁寧に詰めてかないといけない問題。