AtCoder ARC #131 : D - AtArcher

割としんどい…。
https://atcoder.jp/contests/arc131/tasks/arc131_d

問題

1次元の数直線上に的があり、N本の矢を放つ。
昇順の整数列Rと、降順の整数列Sが与えられる。
[-R[1],R[1]]の範囲に矢を当てると、スコアS[0]を得られる。
[-R[i+1],-R[i])または(R[i],R[i+1]]のに矢を当てると、スコアS[i+1]を得られる。

N本の矢を互いにD以上の間隔をあけて放つとき、得られる総スコアの最大値はいくつか。

解法

無駄に間隔をあけていいことはないので、N本は互いにちょうどDの間隔で放つのが良い。
中央の矢の位置を0～Dまでずらしたとき、各矢について総スコアがどう変動するかを考えよう。

矢をずらしても互いにカバーする範囲は変わらないので、矢の位置がずれるにつれ、スコアが増えたり減ったりしてもその総変動回数は高々O(|R|)回となる。

int N;
int M;
ll D;
ll R[101010];
ll S[101010];
ll dif[2020202];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>D;
	FOR(i,M+1) {
		cin>>R[i];
	}
	FOR(i,M) cin>>S[i];
	
	vector<pair<ll,ll>> add,sum;
	add.push_back({-1LL<<60,0});
	sum=add;
	FOR(i,M) {
		add.push_back({R[i+1]+1,S[i+1]-S[i]});
		add.push_back({-R[i+1],S[i]-S[i+1]});
	}
	sort(ALL(add));
	for(i=1;i<add.size();i++) {
		sum.push_back(add[i]);
		sum.back().second=sum[sum.size()-2].second+add[i].second;
	}
	
	map<ll,ll> dif;
	ll cur=0;
	ll ret=0;
	FOR(i,N) {
		ll p=0;
		if(i>=1) {
			if(i%2==1) {
				p=-(i+1)/2*D;
			}
			else {
				p=i/2*D;
			}
		}
		x=lower_bound(ALL(sum),make_pair(p+1,-1LL<<60))-sum.begin()-1;
		cur+=sum[x].second;
		while(x+1<sum.size()&&add[x+1].first<=p+D) {
			x++;
			dif[add[x].first-p]+=add[x].second;
		}
	}
	ret=cur;
	FOR(i,D) {
		cur+=dif[i];
		ret=max(ret,cur);
	}
	cout<<ret<<endl;
}

まとめ

手間取ったけど1発ACできてよかった。