Codeforces #182 Div1. B. Yaroslav and Time

本番解けてはいるけど、通すまでにかなり苦労した問題。
確かにこの問題、Bの割に正答率低いのよね。
http://codeforces.com/contest/301/problem/B

問題

(若干単語を意訳)
N個の都市が２次元座標上に存在する。
数Dが与えられ、都市間の移動にはD*(マンハッタン距離)のエネルギーを消費する。
また、各都市iに到達すると、A[i]分エネルギーが回復する。
途中でエネルギーが0になってはならない。

このとき、都市0から都市(N-1)に到達するときに必要な初期のエネルギー値を答えよ。

解法

初期エネルギー値を二分探索で指定しながらDFSをすればよい。
N<=100なので、２分探索を数十回行っても足りる。

int N,D;
ll X[101],Y[101];
ll A[102];
ll Di[101][101];

int test(ll v){
	int i,y;
	ll EN[101];
	
	FOR(i,N) EN[i]=-1;
	EN[0]=v;
	
	int vis[102];
	ZERO(vis);
	queue<int> q;
	
	q.push(0);
	
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		vis[x]=0;
		
		for(y=1;y<N;y++) if(x!=y && EN[x]-D*Di[x][y]>=0) {
			if(EN[y]<EN[x]-D*Di[x][y]+A[y]) {
				EN[y]=EN[x]-D*Di[x][y]+A[y];
				if(vis[y]==0) {
					vis[y]=1;
					q.push(y);
				}
			}
		}
		if(EN[N-1]>=0) return 1;
	}
	return 0;
	
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	D=GETi();
	int c=0,ma=0;
	FOR(i,N-2) A[i+1]=GETi();
	FOR(i,N) {
		X[i]=GETi();
		Y[i]=GETi();
	}
	
	FOR(x,N) FOR(y,N) Di[x][y]=abs(X[x]-X[y])+abs(Y[x]-Y[y]);
	
	ll L=0,R=1LL<<30;
	FOR(i,32) {
		int P=(L+R)/2;
		if(test(P)) R=P;
		else L=P;
	}
	
	L=max(0LL,L-2);
	while(1) {
		if(test(L)) {
			_P("%lld\n",L);
			return;
		}
		L++;
	}
	return;
}

まとめ

二分探索問題、どうしても１答えがずれるのが怖くて周辺を探してしまうな。