Codeforces #751 Div1 : B. Frog Traveler

不参加だった回。
https://codeforces.com/contest/1601/problem/B

問題

深さNメートルの穴に落ちたので、壁を登りたい。
2つの配列A,Bが与えられる。
現在高さxメートルの位置にいる場合、1回で0メートル以上A[x]メートル以下だけ上にジャンプできる。
ジャンプ後の位置をyメートルとすると、その後B[y]メートルだけ落下する。

Nメートルの穴を登り切るのに、最小何回のジャンプをすればよいか。
ジャンプの手順を示せ。

解法

各位置に到達する最小ジャンプ回数は、深さに対し単調減少(穴底から登る方向に見ると単調増加)になると考えてよい。
そこで、以下の2N+1頂点の有向グラフを考える。

• ジャンプ可能な状態に対応する(N+1)頂点
• 落下中に対応するN頂点

これを踏まえて以下のように辺を張る。

• 前者の深さxに対応する点からは、後者の深さ(x-A[x])に対応する点にコスト1の辺を張る。これは最大ジャンプするケースに相当する。
• 後者の深さyに対応する点からは、前者の深さ(y+B[y])に対応する点にコスト0の辺を張る。これはB[y]だけ落下した後は、再びジャンプできることを意味する。
• 後者の深さyに対応する点からは、後者の深さ(y+1)に対応する点にコスト0の辺を張る。これは1だけジャンプ先の位置を下げることを意味する。

あとはこの有向グラフについて、ダイクストラ法なり01-BFSで最小コストを求めれば。

int N;
int A[303030],B[303030];

vector<pair<int,int>> E[606060];
int D[606060];
int from[606060];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i+1];
	FOR(i,N) cin>>B[i+1];
	
	FOR(i,N) {
	}
	for(i=1;i<=N;i++) {
		E[i-1].push_back({i,0});
		E[i].push_back({i+(N+1)+B[i],0});
		E[i+(N+1)].push_back({i-A[i],1});
	}
	FOR(i,2*N+2) D[i]=1<<20;
	deque<int> Q;
	D[(N+1)+N]=0;
	Q.push_back(2*N+1);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop_front();
		FORR2(e,c,E[cur]) {
			if(D[e]>D[cur]+c) {
				D[e]=D[cur]+c;
				if(c==0) {
					Q.push_front(e);
				}
				else {
					Q.push_back(e);
				}
				from[e]=cur;
			}
		}
	}
	
	if(D[0]==1<<20) cout<<-1<<endl;
	else {
		vector<int> cur={0},ret={0};
		while(cur.back()!=N*2+1) {
			cur.push_back(from[cur.back()]);
			if(cur.size()>=2&&cur.back()<=N&&cur[cur.size()-2]>N) ret.push_back(cur.back());
		}
		reverse(ALL(ret));
		cout<<ret.size()<<endl;
		FORR(e,ret) cout<<e<<" ";
		cout<<endl;
	}
}

まとめ

復元要素面倒だな…。