TopCoder SRM 798 : Div1 Hard RaceCircuit

解法は自明だけどしんどい。
https://community.topcoder.com/stat?c=problem_statement&pm=16769&rd=18491

問題

R*Cのグリッドがある。
隣接マスを順にたどる経路のうち、全マスを1回ずつたどる単一の閉路で構成される例を考える。
各隣接マス間における移動コストと、各マスで経路を90度曲げる場合のコストが与えられる。
また、隣接マス間のうち移動不可の箇所もありうる。

コストの最小値を求めよ。

解法

yukicoderでグリッド上の閉路を扱う問題が何度か出ている。
No.234 めぐるはめぐる (4) - yukicoder
No.541 3 x N グリッド上のサイクルの個数 - yukicoder
No.579 3 x N グリッド上のサイクルのサイズ(hard) - yukicoder

ここらへんを応用しよう。
1段ごとに、次の段に経路が伸びている列と、あとどの列とどの列が経路上で連結しているかを状態に持ち、その際のコストの最小値を覚えておく。
次の段において、90度曲げる箇所を(2^C通り)総当たりしていこう。
列の連結関係が変わるので、そこは面倒だが頑張って処理する。
最終段以外で途中閉路が閉じてしまうケースや、最終段で複数閉路が生じるケースを丁寧に除外していこう。

以下のコードは最大ケースで2.6sと結構危ない。

unordered_map<ll,ll> from;
unordered_map<ll,ll> to;
ll LR[15][15],UD[15][15],CN[15][15];
int ov[256],con[256];
ll DM[1<<12],CM[1<<12];

class RaceCircuit {
	public:
	int construct(int R, int C, vector <int> costRight, vector <int> costDown, vector <int> costCorner) {
		int mask,i,j,y,x;
		FOR(y,R) FOR(x,C) {
			LR[y][x]=costRight[y*C+x];
			if(LR[y][x]==-1) LR[y][x]=1LL<<30;
			UD[y][x]=costDown[y*C+x];
			if(UD[y][x]==-1) UD[y][x]=1LL<<30;
			CN[y][x]=costCorner[y*C+x];
		}
		
		vector<int> cand;
		FOR(mask,1<<C) if(__builtin_popcount(mask)%2==0) cand.push_back(mask);
		
		from.clear();
		FOR(mask,1<<C) {
			ll state=0;
			ll sum=0;
			int right=0,p=0;
			FOR(x,C) {
				if(mask&(1<<x)) {
					sum+=UD[0][x]+CN[0][x];
					if(right==0) {
						p=x;
					}
					else {
						state|=(p+1LL)<<(4*x);
						state|=(x+1LL)<<(4*p);
					}
					right^=1;
				}
				else {
					if(right==0) sum=1LL<<30;
				}
				if(right) sum+=LR[0][x];
			}
			if(right||state==0||sum>=1LL<<30) continue;
			from[state]=sum;
		}
		for(y=1;y<R-1;y++) {
			FOR(mask,1<<C) {
				DM[mask]=CM[mask]=0;
				FOR(x,C) if(mask&(1<<x)) DM[mask]+=UD[y][x], CM[mask]+=CN[y][x];
			}
			to.clear();
			FORR(f,from) {
				ll sum=f.second;
				ll state=f.first;
				int up=0;
				int num=0;
				FOR(x,C) {
					int s=(state>>(4*x))&15;
					if(s) up|=1<<x, ov[x]=s-1,num++;
				}
				FORR(mask,cand) {
					int down=up^mask;
					if(down==0) continue;
					ll ret=sum+DM[down]+CM[mask];
					if(ret>=1LL<<30) continue;
					int wall=up&down;
					int right=0;
					int start=-100;
					FOR(x,C) {
						if(wall&(1<<x)) {
							if(right) {
								ret=1LL<<30;
								break;
							}
							con[x]=x+100;
							con[x+100]=x;
						}
						else if(right) {
							if(up&(1<<x)) {
								con[start]=x;
								con[x]=start;
								right=0;
							}
							else if(down&(1<<x)) {
								con[start]=100+x;
								con[100+x]=start;
								right=0;
							}
						}
						else {
							if(up&(1<<x)) {
								right=1;
								start=x;
							}
							else if(down&(1<<x)) {
								right=1;
								start=100+x;
							}
							else {
								ret+=1LL<<30;
								break;
							}
						}
						if(right) ret+=LR[y][x];
					}
					if(ret>=1LL<<30) continue;
					
					ll nstate=0;
					int cover=0;
					FOR(x,C) if(down&(1<<x)) {
						int tar=con[100+x];
						while(tar<100) tar=con[ov[tar]], cover+=2;
						tar-=100;
						down^=(1<<x)|(1<<tar);
						nstate|=(x+1LL)<<(4*tar);
						nstate|=(tar+1LL)<<(4*x);
					}
					if(nstate==0) continue;
					if(cover!=num) continue;
					if(to.count(nstate)==0) to[nstate]=1LL<<30;
					to[nstate]=min(to[nstate],ret);
				}
			}
			
			swap(from,to);
		}
		ll mi=1LL<<30;
		FORR(f,from) {
			ll state=f.first;
			ll sum=f.second;
			
			FOR(x,C) {
				int s=(state>>(4*x))&15;
				sum+=LR[R-1][x];
				if(x==0&&s==0) sum+=1LL<<30;
				if(s) {
					s--;
					if(x==0&&s!=C-1) sum+=1LL<<30;
					if(x>0&&x<s&&x+1!=s) sum+=1LL<<30;
					if(x==0) sum-=LR[R-1][C-1];
					else if(x<s) sum-=LR[R-1][x];
					sum+=CN[R-1][x];
				}
			}
			mi=min(mi,sum);
		}
		if(mi>=1LL<<30) mi=-1;
		return mi;
	}
}

まとめ

今回1段ずつ処理したけど、よくある1マスずつの処理に直すと高速化できる問題だったかな？
どっちにせよ短時間で詰め切るのはしんどい。