AtCoder ABC #158 : F - Removing Robots

前回のFよりは良心的。
https://atcoder.jp/contests/abc158/tasks/abc158_f

問題

数直線上にN体のロボットがいる。
それぞれ初期位置は異なる。また、それぞれ移動距離D[i]が設定されている。

あるロボットを動かすと、数直線の正方向にD[i]だけ動く。その際他のロボットjに触れると、そのロボットもD[j]だけ動く。
動いたロボットは動き終わったのち数直線から取り除かれる。

今、任意の順で(残った範囲で)任意の数直線上のロボットを動かす指定をできるものとする。
ただしロボットが1体でも動いている間は次の指定はできない。
最終的に残るロボットの組み合わせ何通りか。

解法

まずロボットを座標順にソートしておき、以下を求める。
f(i) := i番目のロボットを動かそうとしたとき、連鎖的にどこまでのロボットが動くか

i番のロボットが直接触れるロボットが[i+1,j]であるとき、f(i) = max(f(i+1),f(i+2)...f(j))となる。
よって、f(i)をiの降順に求めていこう。
jはlower_boundで求められるので、f(i)はRMQで求めることができる。

次に以下を求める。
g(i) := i番のロボットに動かす指示をしたとき、それ以降のロボットの残るパターン
h(i) := i番以降のロボットが残っている場合、それらの残るパターン

何も起きない場合を考えると、h(N)=1としておくとやりやすい。
g(i)は、iを倒すことでf(i)までのロボットが動くことを考えるとg(i) = h(f(i)+1)である。
h(i)は最寄りの倒すロボットをg(i),g(i+1),...のどれにするかを考えると、h(i)=g(i)+g(i+1)+...+g(N)+1だが、これはh(i)=h(i+1)+g(i)と置ける。
よってg(i)とh(i)も降順に処理して、h(0)を答えればよい。

int N;
pair<ll,ll> T[202020];
const ll mo=998244353;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	// static V const def=1LL<<60; min
	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]);
	}
};
SegTree_1<int,1<<20> st;
int nex[202020];
ll dp[202020];
ll sum[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i].first>>T[i].second;
	sort(T,T+N);
	
	sum[N]=1;
	for(i=N-1;i>=0;i--) {
		x=lower_bound(T+i+1,T+N,make_pair(T[i].first+T[i].second,0LL))-T;
		nex[i]=max(i+1,st.getval(i+1,x));
		st.update(i,nex[i]);
		dp[i]=sum[nex[i]]%mo;
		sum[i]=(sum[i+1]+dp[i])%mo;
	}
	cout<<sum[0]<<endl;
}

まとめ

これ解くの200人ぐらいかな？と思ってたら割と近かった。