yukicoder : No.340 雪の足跡

図があるので公式解説見た方がいいね。
http://yukicoder.me/problems/932

問題

大きさH*Wの２次元グリッドがある。
位置(x,y)のセルの番号をy*W+xとする。
左下セル(0,0)から右上セル(W-1,H-1)まで移動したい。

その際、以下の手順で構築されたルート上しか通れない。
N個のセル列が与えられる。
各セル列は(M[i]+1)個のセル番号で構成され、列中で隣接するセル番号は、グリッド上で同じ列か同じ行にあるセルであることが保証される。
セル列中の各セルを順に辿るように隣接セルを辿って移動すると、その際経由した隣接セル同士は相互に移動可能となる。

上記手順で構築されたルートを通って左下(0,0)の点から右上(W-1,H-1)まで移動する最短移動セル数を求めよ。

解法

ルートさえ構築できてしまえばあとは単なるBFSである。
問題はルートの構築。
セル列を構成するセルは最大10^6個程度で、それらの距離は最大1000離れているので愚直にセル列を辿ってルートを構築すると10^9回程度ループを回すことになりTLEする。

そこで、累積和の要領でルート構築を高速化しよう。
例えばセル列中での隣接セル番号をa,b(a＜b)とするなら、以下のように各セルから右・下に移動可能なセル数の最大値を覚えておこう。

• aがbの左側にあるなら「aから右に(b-a)セル移動可能」
• aがbの上側にあるなら「aから下に(b-a)/Wセル移動可能」

全セル列の処理を終えたら、全セルの移動可能距離をDPで求めよう。
「セルpから最大qセル右に移動可能」なら「セル(p+1)から最大(q-1)セル右に移動可能」なので、同様の手順で全セルについて「そこから最大何セル右/下に移動可能」かを求めよう。
DPの結果右ないし下に１つ以上移動なセルは、右・下の隣接セルと辺を張れる。
あとはBFSをやるだけ。

int H,W,N;
vector<int> L[1000000];
int R[1000001],B[1000001];
int dist[1000001],vis[1000001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H>>N;
	FOR(i,N) {
		cin>>x;
		int pre=-1;
		FOR(j,x+1) {
			cin>>y;
			if(pre!=-1) {
				if(abs(y-pre)<W) R[min(y,pre)]=max(R[min(y,pre)],abs(y-pre));
				else B[min(y,pre)]=max(B[min(y,pre)],abs(y-pre)/W);
			}
			pre=y;
		}
	}
	
	FOR(y,H) FOR(x,W) {
		int id=y*W+x;
		dist[id]=1<<30;
		if(x) R[id]=max(R[id],R[id-1]-1);
		if(y) B[id]=max(B[id],B[id-W]-1);
		if(R[id] && x<W-1) L[id].push_back(id+1),L[id+1].push_back(id);
		if(B[id] && y<H-1) L[id].push_back(id+W),L[id+W].push_back(id);
	}
	
	dist[0]=0;
	queue<int> Q;
	Q.push(0);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		FORR(r,L[cur]) if(dist[r]>dist[cur]+1) {
			dist[r]=dist[cur]+1;
			Q.push(r);
		}
	}
	if(dist[W*H-1]<1<<20) _P("%d\n",dist[W*H-1]);
	else _P("Odekakedekinai..\n");
}

まとめ

本番何も考えず愚直に隣接マスを辿ってルート構築してTLEした。
流石にそこまで甘くはないよね…。