Code Festival 2018 予選A D - 通勤

問題

家がx軸上の点0にあり、オフィスがdにある
またx軸上にはn個のガソリンスタンドがあり、これらの座標はx1,x2,...,xnである
家からオフィスまで一直線に、燃料タンクの容量がfで、距離1移動するたびに燃料を1使うような車で移動する
途中でガソリンスタンドを通るたびに
・燃料がt以上残っている場合 -> 補給しない
・そうでない場合 -> 燃料タンクが満タンになるまで補給する
ガソリンスタンドでもオフィスでもない場所で燃料タンクが空になった場合はオフィスへの移動は失敗する
n個のガソリンスタンドのうちのいくつか(0個でも良い)を書店に建て替えたい
書店に建て替えるガソリンスタンドの集合であって、建て替えの後も家からオフィスまで移動できるようなものの個数を求めよ

0 < t <= f <= 10^9
1 <= n <= 10^5
0 < x1 < x2 < ... < xn < d <= 10^9

解法

p[i] = i番目のガソスタで最後に補給するような場合の数 として左から順にガソスタを1個ずつ見ていく
まずi番目のガソスタからオフィスまでの距離がf以下の場合、当然もう残りのガソスタはあってもなくてもどうでもいいから、答えに p[i] * 2^(残りのガソスタの個数) を足せばいい

そうではない場合、次に補給するのはx座標がk+t+1以上(かつf以下)のガソリンスタンドになる
x座標がk+t+1以上f以下のガソスタの番号をle, le+1, ..., riとする (leとriは二分探索で高速に求められる)
x座標がk+1以上k+t以下のガソリンスタンドがm個あった場合、そのm個のガソリンスタンドではどうせ補給はしないから、それらは消しても消さなくてもどっちでもよくて、とりあえず場合の数はp[i] *2^m に増える
で、この場合の数はp[le](le〜riのガソスタを1個も消さない場合), p[le+1](leを消す場合), p[le+2](leとle+1を消す場合), ..., p[ri](leからri-1まで全部消す場合)に足してやる必要がある
これをそのままやるとすごく時間がかかるから累積和を使えばいい

実装

mop = modpow

なんかdpって名前ついた配列あるけど別にこれがdpテーブルってわけではない
dp[0] = 1から発展してほしいだけ
dpとsumを1個にまとめるとdp[0] = 1を累積和で引きずっておかしくなるから分けてある
でも冷静に考えるとdp[0]以外全部空だからめっちゃ無駄なんだよねこれ
i=0のときだけ1かけるみたいな処理した方が良いかも

あと俺は二分探索してるからO(NlogN)だけどしゃくとり法っぽくやればO(N)で行けるらしい
あと累積和じゃなく遅延セグ木とかBIT使ってる人もいたっぽい
今回は別に何使っても実装量はあんま変わらなそう

#define int long long

int d, f, t, n, res;
vector<int> x;
int dp[114514], sum[114514];

signed main() {
	cin >> d >> f >> t >> n;
	x.resize(n+1);
	rep(i,n) cin >> x[i+1];
	n++;
	dp[0] = 1;
	rep(i,n) {
		if (i) (sum[i] += sum[i-1]) %= mod;
		int p = (dp[i] + sum[i]) %mod;
		// オフィスまで行けることが確定した場合
		if (d-x[i]<=f) {
			(res += p * mop(2,n-i-1)) %= mod;
			continue;
		}
		int le = upper_bound(all(x),f-t+x[i]) - x.begin(),
			ri = upper_bound(all(x),f+x[i]) - x.begin() - 1;
		(p *= mop(2,le-i-1)) %= mod;
		(sum[le] += p) %= mod;
		(sum[ri+1] += mod-p) %= mod;
	}
	cout << res << endl;
}

↓こっちのが自然か!

int d, f, t, n, res;
vector<int> x;
int dp[114514];

signed main() {
	cin >> d >> f >> t >> n;
	x.resize(n+1);
	rep(i,n) cin >> x[i+1];
	n++;
	rep(i,n) {
		if (i) (dp[i] += dp[i-1]) %= mod;
		int p = (i==0 ? 1 : dp[i]);
		// ゴールまで行けることが確定
		if (d-x[i]<=f) {
			(dp[n] += p * mop(2,n-i-1)) %= mod;
			continue;
		}
		int le = upper_bound(all(x),f-t+x[i]) - x.begin(),
			ri = upper_bound(all(x),f+x[i]) - x.begin() - 1;
		(p *= mop(2,le-i-1)) %= mod;
		if (ri<le) continue;
		(dp[le] += p) %= mod;
		if (ri+1<n) (dp[ri+1] += mod-p) %= mod;
	}
	cout << dp[n] << endl;
}

やっぱ累積和だとこの細かいとこがめんどい
思考停止でデータ構造使ったほう良いかも