SRM 646 Div1 600 TheGridDivOne

2015-01-16

13:52 |

無限に広い2次元グリッドの原点に人がいて1秒で東西南北に1進める。
行けない整数点が最大47個与えられる。k秒以内で行ける x 座標の最大値を求めよ。
1≦k≦10^9, 行けない点の座標範囲 in [-10^9, 10^9]

行けない点が少ないので座標圧縮＋BFS的なもので行けそう
初めて座標圧縮を書いてみる
なんかおかしい. そもそも圧縮済みのグラフで移動するコストを +1 にしてておかしい.
移動先と移動元のマンハッタン距離を足すようにして Dijkstra に変更
移動先は範囲を表すようにしたけどこれコストはどうするんだ
範囲のうち左を表すようにしてみる
ノードに行くコストが k 未満の場合は余った分を範囲内でさらに動かせるな
むむむむむ合わない
終了

(あとで)

そうだ行けない点と±1 をuniqueにすれば圧縮済みのグラフでもノードが1点に対応するのでコストがちゃんと求まるのだ
圧縮後の一番右のノードのときだけ k の剰余分を答えに足してみる
failed in practice room

圧縮後の一番右に限らず余剰分を足して、もしあれば右のノード座標-1まで行ける、とすれば良さそう
(右に行けるならそこからのやつが答えに反映されるので右-1までとしてよい)
本番とその後の自力トライではできなかったものの、いつもの500とか600にしては簡単？
↓passed in practice room

// Dijkstra省略
VI compress(VI v) {
	VI w;
	REP(i, v.size()) RANGE(r, -1, 2) w.PB(v[i]+r);
	sort(ALL(w));
	w.erase(unique(ALL(w)), w.end());
	return w;
}

VI toVI(vector<int> v) {
	VI w;
	REP(i, v.size()) w.PB(v[i]);
	return w;
}

class TheGridDivOne {
	public:
	int W, H;
	vector<string> m;
	int node(int x, int y) {
		return y*W + x;
	}
	int find(vector <int> X, vector <int> Y, int k) {
		VI vix = toVI(X);
		VI viy = toVI(Y);
		vix.PB(0);
		viy.PB(0);
		VI CX = compress(vix);
		VI CY = compress(viy);
		cout<<CX<<endl;
		cout<<CY<<endl;
		W = CX.size();
		H = CY.size();
		m = vector<string>(H, string(W, '.'));
		int sx, sy;
		REP(x, W) if(CX[x]==0) sx=x;
		REP(y, H) if(CY[y]==0) sy=y;
		REP(y, H) REP(x, W) REP(i, X.size()) {
			if(CX[x]==X[i] && CY[y]==Y[i]) m[y][x]='x';
		}
		m[sy][sx] = 's';
		cout<<m<<endl;
		
		Dijkstra d(W*H);
		int dx[]={0,0,1,-1};
		int dy[]={1,-1,0,0};
		REP(y, H) REP(x, W) REP(dir, 4) {
			int nx=x+dx[dir];
			int ny=y+dy[dir];
			if(0<=nx && nx<W && 0<=ny && ny<H) {
				if(m[ny][nx]=='.') {
					ll cost = abs(CX[nx]-CX[x]) + abs(CY[ny]-CY[y]);
					d.add_edge(node(x, y), node(nx, ny), cost);
				}
			}
		}
		d.run(node(sx, sy), -1);
		ll ans = 0;
		REP(y, H) REP(x, W) if(d.V[node(x, y)]<=k) {
			ll nv = CX[x] + max<ll>(0, k-d.V[node(x, y)]);
			if(x<W-1) nv = min<ll>(nv, CX[x+1]-1);
			ans = max<ll>(ans, nv);
		}
		return ans;
	}
};