TopCoderOpen 2017 Warsar Hard EllysRollerCoasters

ARC解くのが間に合わなかったので不参加。
出てたらHardが遅くてレート微減だったかな。
https://community.topcoder.com/stat?c=problem_statement&pm=14683

問題

H*Wの2次元グリッド上にレールを敷くことを考える。
この時、各セルには以下の条件のいずれかが指定される。

• セルにレールを敷かない。
• セルに直線レールを敷く。すなわち上下か左右の端の中央を結ぶようにする。
• 90度に曲がるレールを敷く。うち片方の端点の上下左右の向きが指定される。

各レールが閉路を構成するようなレールのつなぎ方を求めよ。
つなぎ方が複数ある場合、最長の閉路が最長のものを答えよ。

解法

閉路を構成するつなぎ方が存在するとき、一意に定まる。
よってその唯一の構成を考えよう。

この問題は2-SATに置き換えることができる。
各セル上下左右方向のレールの有無を2-SATの変数とみなし、計4*H*W変数の2-SATを考えよう。

• 直線レールについては、上下および左右の値が一致し、上と左右が異なる。
• 90度レールについては、指定された向きは必ず真で、逆は偽で、90度回転した向きは２つのうち1つが真
• 隣接するセルをまたぐレールについては、両者の真偽が等しい。

class SCC {
public:
	static const int MV = 25000;
	vector<vector<int> > SC; int NV,GR[MV],rev[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu); rev[cu]=ind;
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

class TwoSat {
	int NV;
	SCC sc;
public:
	vector<int> val;
	void init(int NV) { this->NV=NV*2; sc.init(NV*2); val.resize(NV);}
	void add_edge(int x,int y) { // x or y  k+0:normal k+NV:inverse
		sc.add_edge((x+NV/2)%NV,y); // not x->y
		sc.add_edge((y+NV/2)%NV,x); // not y->x
	}
	
	bool sat() { // empty:false 
		sc.scc();
		for(int i=0;i<NV/2;i++) if(sc.GR[i]==sc.GR[i+NV/2]) return false;
		for(int i=0;i<NV/2;i++) val[i]=sc.GR[i]>sc.GR[i+NV/2];
		return true;
	}
};

TwoSat ts;
class EllysRollerCoasters {
	public:
	vector <string> getPlan(vector <string> F) {
		int H=F.size(),W=F[0].size();
		int NV=4*H*W;
		int y,x;
		vector<string> ret;
		
		ts.init(NV);
		FOR(y,H) FOR(x,W) {
			char c=F[y][x];
			int ID=(y*W+x)*4;
			if(c=='.') {
				ts.add_edge(ID+NV,ID+NV);
				ts.add_edge(ID+1+NV,ID+1+NV);
				ts.add_edge(ID+2+NV,ID+2+NV);
				ts.add_edge(ID+3+NV,ID+3+NV);
			}
			//LRUD
			if(c=='L') {
				ts.add_edge(ID,ID);
				ts.add_edge(ID+1+NV,ID+1+NV);
				ts.add_edge(ID+2,ID+3);
				ts.add_edge(ID+2+NV,ID+3+NV);
			}
			if(c=='R') {
				ts.add_edge(ID+1,ID+1);
				ts.add_edge(ID+NV,ID+NV);
				ts.add_edge(ID+2,ID+3);
				ts.add_edge(ID+2+NV,ID+3+NV);
			}
			if(c=='U') {
				ts.add_edge(ID+2,ID+2);
				ts.add_edge(ID+3+NV,ID+3+NV);
				ts.add_edge(ID+0,ID+1);
				ts.add_edge(ID+0+NV,ID+1+NV);
			}
			if(c=='D') {
				ts.add_edge(ID+3,ID+3);
				ts.add_edge(ID+2+NV,ID+2+NV);
				ts.add_edge(ID+0,ID+1);
				ts.add_edge(ID+0+NV,ID+1+NV);
			}
			if(c=='S') {
				ts.add_edge(ID+0,ID+1+NV);
				ts.add_edge(ID+1,ID+0+NV);
				ts.add_edge(ID+2,ID+3+NV);
				ts.add_edge(ID+3,ID+2+NV);
				ts.add_edge(ID,ID+2);
				ts.add_edge(ID+NV,ID+2+NV);
			}
			
			if(x<W-1) {
				ts.add_edge(ID+1,ID+4+NV);
				ts.add_edge(ID+4,ID+1+NV);
			}
			if(y<H-1) {
				ts.add_edge(ID+3,ID+4*W+2+NV);
				ts.add_edge(ID+4*W+2,ID+3+NV);
			}
			if(x==0) ts.add_edge(ID+NV,ID+NV);
			if(x==W-1) ts.add_edge(ID+1+NV,ID+1+NV);
			if(y==0) ts.add_edge(ID+2+NV,ID+2+NV);
			if(y==H-1) ts.add_edge(ID+3+NV,ID+3+NV);
		}
		if(!ts.sat()) return ret;
		
		char hoge[17]=".**-*/\\**\\/*|***";
		FOR(y,H) {
			string s;
			FOR(x,W) {
				int ID=(y*W+x)*4;
				s+=hoge[ts.val[ID]+ts.val[ID+1]*2+ts.val[ID+2]*4+ts.val[ID+3]*8];
			}
			ret.push_back(s);
		}
		return ret;
	}
}

まとめ

条件を作るのにだいぶ手間取った。