yukicoder : No.2698 Many Asakatsu

なるほど。
https://yukicoder.me/problems/no/2698

問題

N個の問題セットがある。
各セットはM個の問題からなり、i番のセットのうちj番目の問題の難易度をD(i,j)とする。
D(i,j)は以下を満たす。

• D(i,*)は等差数列を成す。
• D(i,j)＜D(i+1,j)

レートXの人が問題セットを選ぶとき、レートと各問題の差の絶対値の総和が最小となるものを選ぶとする。
Q回、レート増加のクエリが与えられるので、そのつど選ぶべき問題セットを答えよ。

解法

f(i,x) := レートxの人がi番の問題セットを選んだ時の、レートと各問題の差の絶対値の総和
とする。この値はO(1)で算出可能である。
g(x) = min(f(i,x))とすると、レートXの際にg(X)=f(i,X)となるiを求める問題となる。

Dに関する条件から、f(i+1,x)とf(i,x)は、xが小さいうちはf(i,x)が小さく、途中でf(i+1,x)が大きくなる。
よって、g(x)=f(i,x)となるiは単調増加になる。
そこでCHTの要領で、g(x)=f(i,x)となるiが切り替わるxの値とその時のiの値を最初に列挙しておこう。
そうすればクエリ毎に、xの値を列挙した配列を二分探索すればよい。

int N;
ll M;
ll A[202020],B[202020];
ll D[202020],C[202020];
int Q;
ll X;
__int128 get(int id,ll v) {
	if(id<0||id>=N) return 1LL<<60;
	__int128 num=0;
	if(v>=A[id]) {
		if(B[id]==0) num=M;
		else num=min(M,(v-A[id])/B[id]+1);
	}
	
	__int128 pre=(__int128)A[id]*num+(__int128)B[id]*num*(num-1)/2;
	__int128 suf=(__int128)A[id]*M+(__int128)B[id]*M*(M-1)/2-pre;
	__int128 ret=(2*num-M)*v-pre+suf;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i]>>B[i];
	}
	cin>>Q>>X;
	vector<pair<ll,int>> V;
	FOR(i,N) {
		cin>>C[i];
		
		if(i==0) {
			V.push_back({0,0});
		}
		else {
			while(V.size()) {
				int pre=V.back().second;
				ll cur=1LL<<60;
				for(j=59;j>=0;j--) if(get(i,cur-(1LL<<j))<get(pre,cur-(1LL<<j))) cur-=(1LL<<j);
				if(V.back().first<cur) {
					V.push_back({cur,i});
					break;
				}
				V.pop_back();
			}
		}
	}
	
	
	while(Q--) {
		x=lower_bound(ALL(V),make_pair(X+1,0))-V.begin()-1;
		cout<<V[x].second+1<<" ";
		
		X+=C[V[x].second];
		
	}
	cout<<endl;
}

まとめ

こういうCHT風テクの応用は初めてかも。