TopCoder SRM 849 : Div1 Easy Div2 Hard LongSimplePath

4か月ぶりに参加したSRM、なんかChallengeで当たっていい結果に。
https://community.topcoder.com/stat?c=problem_statement&pm=18100

問題

R*Cのグリッドがあり、うちN箇所通行不可なマスがある。
左上マスにあるロボットを、右下マスに移動させたい。

ロボットには以下の命令を出すことができる。

• 右に2^0～2^25のいずれか2の累乗マス分移動する
• 下に2^0～2^25のいずれか2の累乗マス分移動する

なお、途中で通行不可マスを通ってはならない。

経路が存在するなら一例を示せ。

解法

行と列を座標圧縮する。
圧縮対象は、行については先頭行・最後の行・通行不可マスのある行・通行不可マスのある行の1つ手前の行である。
列も同様に行う。

あとは単純なDPで処理できる。
圧縮後の隣接マスが、圧縮後2^26以上の距離があることもある点に注意。
その場合2^25マス移動する命令を連打しないといけない。

string dp[155][155];

class LongSimplePath {
	public:
	string traverse(int R, int C, vector <int> obsR, vector <int> obsC) {
		vector<int> Ys={0,R};
		vector<int> Xs={0,C};
		int i;
		FOR(i,obsR.size()) {
			if(obsR[i]) Ys.push_back(obsR[i]-1);
			Ys.push_back(obsR[i]);
		}
		FOR(i,obsC.size()) {
			if(obsC[i]) Xs.push_back(obsC[i]-1);
			Xs.push_back(obsC[i]);
		}
		sort(ALL(Ys));
		sort(ALL(Xs));
		Xs.erase(unique(ALL(Xs)),Xs.end());
		Ys.erase(unique(ALL(Ys)),Ys.end());
		int x,y;
		set<pair<int,int>> NG;
		FOR(i,obsR.size()) {
			x=lower_bound(ALL(Xs),obsC[i])-Xs.begin();
			y=lower_bound(ALL(Ys),obsR[i])-Ys.begin();
			NG.insert({y,x});
		}
		R=Ys.size();
		C=Xs.size();
		FOR(x,R) FOR(y,C) dp[y][x].clear();
		FOR(y,R) FOR(x,C) if(y+x==0||dp[y][x].size()) {
			if(y+1<R&&NG.count({y+1,x})==0) {
				dp[y+1][x]=dp[y][x];
				int dif=Ys[y+1]-Ys[y];
				while(dif>=1<<25) {
					dp[y+1][x]+='a'+25;
					dif-=1<<25;
				}
				FOR(i,26) if(dif&(1<<i)) dp[y+1][x]+='a'+i;
			}
			if(x+1<C&&NG.count({y,x+1})==0) {
				dp[y][x+1]=dp[y][x];
				int dif=Xs[x+1]-Xs[x];
				while(dif>=1<<25) {
					dp[y][x+1]+='A'+25;
					dif-=1<<25;
				}
				FOR(i,26) if(dif&(1<<i)) dp[y][x+1]+='A'+i;
			}
			
		}
		return dp[R-1][C-1];
	}
}

まとめ

250ptの割に面倒な問題。