Codeforces #945 : Div2 D. Cat, Fox and Maximum Array Split

Eが詰め切れなかった。
https://codeforces.com/contest/1973/problem/D

問題

1～Nで構成されるN要素の整数列Aがある。
f(L,R) = max(A[L...R])*(R-L+1)、すなわちA[L...R]の最大値に、区間長を掛けた値とする。

N,Kが与えられるので、AをK個の連続した部分列に分割したとき、それぞれの区間[L,R]に対するf(L,R)が等しくmとなるようにしたい。
可能なmの最大値を求めよ。

なお、Aは明に与えられないが、以下のクエリを2N回まで行うことができる。
2値L,Xを指定すると、f(L,R)=XとなるRが存在すればその最小値を返す。

解法

Aの各要素は正なので、f(L,R)はRに対し狭義単調増加。よってクエリに対してはRは存在するなら1つだけであり、それを返す。

まずAの最大値を求めよう。
これはL=0とし、XにN*N、N*(N-1)、N*(N-2)…を順に指定して、R=N-1となるタイミングを見つければよい。

f(L,R)の定義より、Aの最大値A[v]を含む区間[L,R]に対しf(L,R)はA[v]の倍数である。
よって、mはA[v]に、1～floor(N/K)のいずれかを掛けた値しかとりえない。
あとはそれぞれのケースを試し、クエリをK回実行して数列をK個に分解できるか試せばよい。

int T,N,P[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> S;
		int minL=N+1,maxR=0;
		for(i=1;i<=N;i++) {
			cin>>P[i];
			if(i!=P[i]) {
				S.insert(i+P[i]);
				maxR=max(maxR,i);
				minL=min(minL,i);
			}
		}
		if(maxR==0) {
			cout<<1LL*2*N*(2*N+1)/2<<endl;
			continue;
		}
		
		ll ret=0;
		if(S.size()==1) ret++;
		else if(S.empty()) ret+=2*N;
		for(int L=1;L<=minL+N;L++) {
			x=max(maxR+1,L+1);
			ret+=2*N+1-x;
		}
		
		
		cout<<ret<<endl;
	}
}

まとめ

本番まぁまぁ苦労しているな。
まぁこれクエリ回数を適切に見積もるのがちょっとしんどい。