TopCoder SRM 792 : Div1 Hard EllysFlags

本番バグが取り切れずだった…もったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=15914&rd=18340

問題

H*Wのグリッドの各マスが白・緑・赤のいずれかで塗られている。
ここで、白マスを任意に緑または赤に塗り替えられるものとする（白のまま残してもよい）。
3つの右または下方向につながるマスが順に白・緑・赤の順に塗られているとき、1ポイントを得られるとする。
最適に色を塗ったとき、最大ポイントを求めよ。

解法

1行分のマス目の状態を持ちずつ1マスずる処理していく。
dp(r,c,state) := row-major orderで1マスずつ処理し、r行c列まで処理したとき、各列処理済みの最下段の状態がstateであるときの最多ポイント

stateの状態だが、各マス以下が考えられる。

• 白マス
• 緑マスで、その左と上に合わせて0,1,2個の白マスがつながっている
• 赤マス

こうするとstateは5^W通り取れるが、そうすると全体の処理がO(HW5^W)でTLEする。
次にどのマスが来てもポイントが増えない、という意味で白マスと隣接しない緑マスと赤マスは同じなので、それらを同一視しよう。
そうするとstateが4^W通りになり間に合う。

int from[1<<20];
int to[1<<20];

// G0,G1,G2,W

class EllysFlags {
	public:
	int getMax(vector <string> paper) {
		int H=paper.size();
		int W=paper[0].size();
		
		int i,mask;
		FOR(i,1<<20) from[i]=-101010;
		from[0]=0;
		int y,x;
		FOR(y,H) FOR(x,W) {
			FOR(i,1<<20) to[i]=-101010;
			FOR(mask,1<<(2*W)) {
				int cm=(mask>>(2*x))&3;
				int pm=(x?((mask>>(2*(x-1)))&3):4);
				int nmask=mask^(cm<<(2*x));
				int v=from[mask];
				if(paper[y][x]=='W') {
					to[nmask|(3<<(2*x))]=max(to[nmask|(3<<(2*x))],v);
				}
				if(paper[y][x]=='W'||paper[y][x]=='G') {
					int nv=0;
					if(cm==3) nv++;
					if(pm==3) nv++;
					to[nmask|(nv<<(x*2))]=max(to[nmask|(nv<<(x*2))],v);
				}
				if(paper[y][x]=='W'||paper[y][x]=='R') {
					int ok=0;
					if(cm<3) ok+=cm;
					if(pm<3) ok+=pm;
					to[nmask]=max(to[nmask],v+ok);
				}
				
			}
			swap(to,from);
		}
		
		int ma=0;
		FOR(mask,1<<(2*W)) ma=max(ma,from[mask]);
		return ma;
	}
}

まとめ

こっちの方が簡単じゃないか…。