いろいろグダグダな部分もあるけど、まぁこんなもんかな…。
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で解こうとしたけどなぜか満点とれず…。