AtCoder ABC #146 : F - Sugoroku

Fとしては比較的簡単？
https://atcoder.jp/contests/abc146/tasks/abc146_f

問題

(N+1)マスからなる双六を考える。
端から端まで、1回に(1～M)マスずつ進んで移動したい。
ただし、途中で分では行けないマスがある。

移動回数が最小となる移動法のうち、移動マス数を並べると辞書順最小となる移動法を求めよ。

解法

f(n) := nマス目からゴールに至るまでの最小移動回数(ただしnマス目が移動不可能な時は∞)
とする。
nマス目の次の遷移先は、(n+1)～min(N+1,(n+M))マス目xのうち、f(x)が最小の箇所である。
もしf(x)が最小値となるxが複数あるなら最小のxを取ればよい。
これはスライド最小値等でも処理できるし、KeyとValueを併せ持つRMQを処理できるSegTreeでもよい。

移動先が決まったら、0マス目から順に実際に移動するだけ。

int N,M;
string S;

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=1<<30;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return min(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,NV);
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<int,1<<20> st;

int dp[202020];
int from[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	
	dp[N]=0;
	st.update(N,0);
	for(i=N-1;i>=0;i--) if(S[i]=='0') {
		auto p=st.getval(i+1,min(i+M+1,N+1));
		from[i]=p.second;
		dp[i]=p.first+1;
		st.update(i,dp[i]);
	}
	
	if(dp[0]>=1<<30) {
		cout<<-1<<endl;
	}
	else {
		int cur=0;
		while(cur<N) {
			cout<<from[cur]-cur<<" ";
			cur=from[cur];
		}
		cout<<endl;
	}
}

まとめ

今回全完がかなり多いみたいだけど、むべなるかなという感じ。