SRM513 Div1 Easy - YetAnotherIncredibleMachine

問題

2次元平面に横長の板がn枚浮いていて、それぞれ高さが違う
板は1刻みで横に動かせる 動かせる範囲の上限はある
いくつかのボールがいろいろなx座標に落とされるとき、全てのボールが地面に落ちるようにする板の配置は何通りあるか

解法

前準備として、ボールが落ちる位置の累積和を取っておき、ある範囲に板があるときにボールにぶつからないかをO(1)で判定できるようにしておく
あとはそれぞれの板について全てのボールにぶつからない配置を数え上げて、それらの積を取ればいい

自分は問題文を誤読して時間がかかった
板を動かせる範囲が「left endの座標が〜で、right endの座標が〜」とちゃんと書いてあるんだけど、↓みたいな勘違いをしてた

ボールは板の端にぶつかっても止まるとも書いてあるしね

実装

板とボールの位置がマイナスのとき困るから全ての座標に適当に3万足す
→その座標で累積和をとる
→各板の有効な配置を数え上げて積をとっていく
数え上げは右端の座標でループを回してる

class YetAnotherIncredibleMachine {
	public:
	int countWays(vector<int> x, vector<int> s, vector<int> b) {
		ll n = x.size(), res = 1;
		each(i,x) i += 30000;
		each(i,b) i += 30000;
		int ng[114514] = {};
		each(i,b) ng[i]++;
		reps(i,1,114514) ng[i] += ng[i-1];
		
		rep(i,n) {
			ll p = 0;
			reps(r,x[i],x[i]+s[i]+1) if (ng[r]-ng[r-s[i]-1]==0) p++;
			(res *= p) %= mod;
		}
		return res;
	}
};