CODE FESTIVAL 2018 Qual A : D - 通勤

FAでした。
https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d

問題

座標0の位置からDの位置まで、前進しかできない車で移動する。
その際、間にN個のガソリンスタンドiがあり、その座標X[i]が与えられる。

この車は初期状態でガソリンが満タン要領のFある。
ガソリンスタンド経由時、残量がT以下なら満タンにする。
移動中ガソリンが切れたら移動失敗である。

一部のガソリンスタンドをつぶすことを考える。
ガソリンスタンドのつぶし方のうち、車がDの位置に到達できるつぶし方は何通りか。

解法

ガソリンスタンド1～Nの位置をX[i]とするとき、初期位置をX[0]=0、ゴールをX[N+1]=Dとするとやりやすい。
f(i) := ガソリンスタンドiでガソリンを満タンにするとき、ゴールに至れるi番以降のガソリンスタンドのつぶし方の組み合わせ
とする。f(N+1)=1としてiの大きい順にf(i)を埋めていき、最後f(0)が解となる。

i番でガソリンを満タンとすると、次にガソリンを補給するのはX[i]+F-T+1≦X[j]≦X[i]+Fを満たすガソリンスタンドjのいずれかである。
(ただし例外としてゴールX[N+1]だけはガソリン残量に依存しないのでX[i]≦X[N+1]であれば移動可能であるとする)

上記条件を満たすjがある区間L≦j≦Rとする。L,RはXが昇順列なので二分探索で求められる。
その場合、f(i) = sum(f(L)...f(R))としよう。これはBITでもよいし、逆向きに累積和をとっても求められる。

ll D,T,F;
int N;
ll X[101010];
ll dp[101010];
ll p2[101010];
ll mo=1000000007;
template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	BIT_mod(){ZERO(bit);};
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	V add(int e,V v) { e++; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<ll,20> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D>>F>>T>>N;
	for(i=1;i<=N;i++) cin>>X[i];
	X[N+1]=D;
	X[N+2]=1LL<<60;
	dp[N+1]=1;
	bt.add(N+1,1);
	
	p2[0]=1;
	FOR(i,101000) p2[i+1]=p2[i]*2%mo;
	
	for(i=N;i>=0;i--) {
		ll L=X[i]+F-T+1;
		ll R=X[i]+F;
		x=lower_bound(X+i+1,X+N+2,L)-X;
		y=lower_bound(X+i+1,X+N+2,R+1)-X;
		if(x==N+2) x=N+1;
		y--;
		if(y<x) continue;
		dp[i]=((bt(y)-bt(x-1))%mo+mo)*p2[x-i-1]%mo;
		bt.add(i,dp[i]);
	}
	cout<<(bt(0)%mo)<<endl;
}

まとめ

Eに比べると典型的なテクの集合体の問題なので、発想より経験で解ける問題。