AtCoder ARC #150 : F - Constant Sum Subsequence

よくこういう問題考えるなぁ。
https://atcoder.jp/contests/arc150/tasks/arc150_f

問題

N^2要素の整数列Aが与えられる。
このAは周期Nである。

整数Sが与えられる。
Aのprefixのうち、総和がSとなる正整数列がすべて部分列として含まれるような最小の長さを求めよ。

解法

整数列Xに対し、f(X)を総和がsとなる正整数列をすべて含むようなsの最大値とする。
求めるのは、AのprefixであるA'のうちf(A')≧Sとなる最短のA'である。

dp(i) = f(A[0...i])として、dp(i)を求めることを考える。
dp(i)を求める際、1,2,....,Sが最後に登場する位置から算出できる。
dp(i)を全部保持するとO(N^2)だけテーブルがあって難しいが、dp(i)が単調増加であることを利用して更新していく。

int N,S;
int A[2020202];
set<int> V[202020];

ll ret[202020];

ll front(ll p,int v) {
	p--;
	return (*V[v].lower_bound(p%N+1)-(p%N)+p+1);
}
ll bef(ll p,int v) {
	if(p==0) return 0;
	p--;
	return (p-((p%N)-*prev(V[v].lower_bound(p%N))))+1;
}

int dp(ll p) {
	if(p<0) return 0;
	return lower_bound(ret,ret+200001,p+1)-ret-1;
}

ll L,T[402020];
vector<int> cand[402020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	
	if(N==1) {
		cout<<1<<endl;
		return;
	}
	
	FOR(i,N) {
		cin>>A[i];
		V[A[i]].insert(i);
	}
	FOR(i,200001) ret[i]=1LL<<60;
	ret[0]=0;
	
	for(i=1;i<=S;i++) {
		x=*V[i].begin();
		y=*V[i].rbegin();
		V[i].insert(y-N);
		V[i].insert(x+N);
	}
	for(i=1;i<=S;i++) {
		T[i]=i-1;
		cand[T[i]].push_back(i);
	}
	for(i=0;i<S;i++) {
		FORR(x,cand[i]) {
			if(bef(L,x)<=0) {
				T[x]=x-1;
			}
			else {
				T[x]=dp(bef(L,x)-1)+x;
			}
			if(T[x]<=i) {
				L=front(L,x);
				T[x]=i+x;
			}
			cand[T[x]].push_back(x);
		}
		ret[i+1]=L;
	}
	cout<<L<<endl;
}

まとめ

考察ステップだいぶ多いけど複数名時間内に解き切ってるんだよな…。