yukicoder : No.3284 Picnic with Friends

今回いつもと終了時間が違っていてびっくりした。
https://yukicoder.me/problems/no/3284

問題

N人のフレンズがおり、それぞれパラメータS[i]を持つ。
ここで、Q回のイベントが行われる。
各イベントはパラメータT[i],F[i]で表現される。

• もし時刻T[i]にピクニックが行われていなければ、時刻T[i]～(T[i]+F[i]+0.5)の間ピクニックを行う。
• もし時刻T[i]にピクニックが行れていれば、その時間をF[i]延長する。

各フレンズは、1回のピクニック時間をXとするとfloor(X/S[i])の石を見つける。
各フレンズが得る石の数を答えよ。

解法

まず、連続するピクニックをそれぞれあらかじめ連続しておこう。
その時間からなる配列をAとすると、各フレンズに対しはバラバラだが、sum(A)は高々max(F)*Qである点に留意する。
以後、平方分割で解く。適当なブロックサイズBを取る。

• s≦Bについて、aごとに愚直にsum(floor(a/s))を求めておけば、S[i]≦sの時の解を求められる。
• s＞Bについて、解は高々sum(A)/sなので、i*s≦aであるようなsに、iを足しこむ、というのをSを座標圧縮した状態でsに対応するカウンタに対し適用すればよい。

int N;
ll S[505050];
int Q;
ll T[505050],F[505050];

ll small[1010];
ll big[501101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> Ss;
	FOR(i,N) {
		cin>>S[i];
		if(S[i]>1000) Ss.push_back(S[i]);
	}
	sort(ALL(Ss));
	Ss.erase(unique(ALL(Ss)),Ss.end());
	
	cin>>Q;
	FOR(i,Q) {
		cin>>T[i]>>F[i];
		if(i&&(T[i-1]+F[i-1])>=T[i]) {
			F[i-1]+=F[i];
			i--;
			Q--;
		}
	}
	ll FS=0;
	FOR(i,Q) {
		FS+=F[i];
		for(j=1;j<=1000;j++) small[j]+=F[i]/j;
		for(ll step=1;step*1000<=F[i];step++) {
			ll add=F[i]/step;
			big[0]++;
			x=lower_bound(ALL(Ss),add+1)-Ss.begin();
			big[x]--;
		}
	}
	for(i=1;i<Ss.size();i++) big[i]+=big[i-1];
	
	FOR(i,N) {
		if(S[i]<=1000) {
			cout<<small[S[i]]<<endl;
		}
		else {
			x=lower_bound(ALL(Ss),S[i])-Ss.begin();
			cout<<big[x]<<endl;
		}
	}
}

まとめ

ピクニックを連結する部分、なくても良かった気がするけど、ストーリー的に元ネタに関連付けたかったのかな。