kmjp's blog

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

Codeforces #355 Div2 D. Vanya and Treasure

これ3s位でいい気がする。
http://codeforces.com/contest/677/problem/D

問題

N*Mのグリッドが与えられる。
各セルには1~Pの整数が書かれている。

左上から初めて隣接マスを辿り、1~Pが書かれたマスを最低1回ずつ順に辿りたい。
(途中関係ないマスを経由しても良いし、複数回通ってもよい)
最低何回移動が必要か。

解法

f(x)をxが書かれたマスの数とする。
f(x)*f(x+1)が十分小さいなら、xが書かれたマスからDPの容量で(x+1)が書かれたマスに移動した際の移動長の最小値を求めることができる。

ただ、わずかながらf(x)やf(x+1)が多いケースはf(x)*f(x+1)が大きいとTLEする。
そこで、それらのケースに限っては、xが書かれたマス群を始点とするダイクストラ法で(x+1)が書かれたマスに移動した際の移動長の最小値を求めよう。
f(x)*f(x+1)が多くなるxはそんなにないので、両方式を使い分ける閾値を適切に設定すれば通る。

int H,W,P;
int A[303][303];
vector<int> V[90909];
int dist[303][303];
int tdist[303][303];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>P;
	FOR(y,H) FOR(x,W) {
		cin>>A[y][x];
		V[A[y][x]].push_back(y*1000+x);
		dist[y][x]=1<<30;
		if(A[y][x]==1) dist[y][x] = y+x;
	}
	for(i=1;i<P;i++) {
		if(V[i].size()*V[i+1].size()<=250000) {
			FORR(r1,V[i]) FORR(r2,V[i+1])
				dist[r2/1000][r2%1000] = min(dist[r2/1000][r2%1000], dist[r1/1000][r1%1000] + abs(r1/1000-r2/1000) + abs(r1%1000-r2%1000));
		}
		else {
			FOR(y,H) FOR(x,W) tdist[y][x]=1<<30;
			priority_queue<pair<int,int>> Q;
			FORR(r,V[i]) {
				tdist[r/1000][r%1000]=dist[r/1000][r%1000];
				Q.push({-tdist[r/1000][r%1000],r});
			}
			while(Q.size()) {
				int cy=Q.top().second/1000;
				int cx=Q.top().second%1000;
				int co=-Q.top().first;
				Q.pop();
				if(co!=tdist[cy][cx]) continue;
				FOR(j,4) {
					int dd[4]={1,0,-1,0};
					int ty=cy+dd[j];
					int tx=cx+dd[j^1];
					if(tx>=0 && tx<W && ty>=0 && ty<H && tdist[ty][tx] > co+1) {
						tdist[ty][tx] = co+1;
						Q.push({-tdist[ty][tx],ty*1000+tx});
					}
				}
			}
			FORR(r,V[i+1]) dist[r/1000][r%1000]=tdist[r/1000][r%1000];
		}
	}
	int mi=1<<30;
	FORR(r,V[P]) mi=min(mi,dist[r/1000][r%1000]);
	cout<<mi<<endl;
	
}

まとめ

最初閾値を90000にしたらTLEした。
凡そ解法あってるんだしさぁ…。