kmjp's blog

競技プログラミング参加記です

NJPC 2017 : C - ハードル走

いろいろグダグダな部分もあるけど、まぁこんなもんかな…。
http://njpc2017.contest.atcoder.jp/tasks/njpc2017_c

問題

N個のハードルがゴールに向けて一直線に並んでいる。
各ハードルはスタートからの位置X[i]に置かれている。

ゴールに向け一直線に走る際、ハードルで転ばないようにしたい。
走る途中でジャンプすると、そこから距離Lの地点まで空中を通る。すなわちその間のハードルでは躓かなくて済む。
ただし、着地後はもう距離Lの間はジャンプできない。

ジャンプは非整数の位置でも可能だが、ジャンプや着地の位置をハードルと重ねることはできない。
最適なタイミングでジャンプするとき、ハードルに躓かずゴールに到達可能か。

解法

尺取り法+貪欲法で飛ぶことができる。

今いる位置の次のハードルをi番とする。
i番を飛ぶ場合、その後距離(L-1)内のハードルjをすべて同じジャンプで飛ばなければならない。
そうでない場合、着地後しばらくジャンプできない条件により、後のハードルに躓いてしまう。

尺取り法の要領で一度に飛ぶ最遠のハードルを求めよう。
あとはそれらのハードルを飛びきるジャンプ位置のうち、できるだけ手前で飛ぶようにすればよい。

非整数の処理が面倒なので、自分は登場する座標をすべて2倍して偶数にし、ジャンプは奇数の位置でのみ行うようにした。

ll N,L;
ll A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	L*=2;
	
	FOR(i,N) {
		cin>>A[i];
		A[i]*=2;
	}
	
	ll cur=1;
	int nex=0;
	int R=0;
	while(nex<N) {
		while(R+1<N && A[R+1]-A[nex]<L) R++;
		
		cur=max(cur+L,A[R]+1);
		cur+=L;
		
		nex=R+1;
		if(nex<N && cur>A[nex]) return _P("NO\n");
		
	}
	cout<<"YES"<<endl;
	
	
}

まとめ

最初DPで解こうとしたけどなぜか満点とれず…。