CPSCO2019 Session1 : G - Game with Division

ちょっと手間取った。
https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_g

問題

整数XとN要素の整数列Aが与えられる。
手持ちの値Xに対し、Aの各要素を順に、下記いずれかの処理を行うことを選択できるとする。

• なにもしない。
• 手持ちの値をfloor(A[i]/X)で置き換える。その際、置き換え後の値の分の得点を得る。

総得点の最大値を求めよ。

解法

まず思いつく解はこれである。
dp(i,x) := i番目まで処理を行った場合、手持ちの値がxであるときの最大総得点
ただ、このDPを愚直に行うとO(NX)かかり間に合わない。

ここで、floor(A[i]/X)はO(√A[i])通り程度しかないことに着目する。
dp(i,x)からdp(i+1,y)の遷移を考えよう。
xが√A[i+1]ごろまでは愚直にdp(i+1,y) = max(dp(i+1,y), dp(i,x)+floor(A[i+1]/x)を計算すればよい。
xが√A[i+1]以上の場合、y=floor(A[i+1]/x)の値はO(√A[i])通り程度しかないので、dp(i,x)をRange Maximum Queryが解けるSegTreeを持っておけば、複数のxをまとめて処理できる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};


int N,X;
SegTree_1<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X;
		vector<pair<int,int>> ret;
		for(j=1;j<=1000;j++) {
			if(j<=X) ret.push_back({X/j,st.getval(j,j+1)+X/j});
			
			x=X/(j+1)+1;
			y=X/j;
			if(x<=y) ret.push_back({j,st.getval(x,y+1)+j});
		}
		FORR(r,ret) st.update(r.first,r.second);
	}
	cout<<st.getval(0,(1<<20)-1)<<endl;
	
}

まとめ

これ系の平方分割（？）、Codeforcesでしばしば見かける。