Google Code Jam 2017 Qualification Round : D. Fashion Show

これは良い問題。
https://code.google.com/codejam/contest/3264486/dashboard#s=p3

問題

N*Nのグリッドに、3種類の駒"+xo"を置く。
各駒の置き方は以下の条件がある。

• 同じ列または行にある2つの駒のうち少なくとも片方は"+"でなければならない。
• 斜め45度の位置にある2つの駒のうち少なくとも片方は"x"でなければならない。

駒の初期状態が与えられる。
"+xo"の各駒は、それぞれ1,1,2ポイントを持つ。
条件に違反しない範囲で以下の駒配置を行い、ポイントを最大化せよ。

• 空きマスに任意の駒を置く。
• "+x"を"o"に昇格する。

解法

両者の条件を言い換えると以下のようになる。

• 同じ列または行にはxやoは2つ以上置けない。
• 同じ斜め45度のラインには+やoは2つ以上置けない。

"o" = "+" + "x"と考えると、前者の条件と後者の条件を独立に考えることができる。
あとは両者それぞれの範囲で置ける駒数を最大化しよう。
後者は前者を45度回転させた問題と考えると、同じような考え方で解ける。

前者について考えると、列と行をそれぞれ頂点とおいた二部グラフの最大マッチング問題にできる。
また、貪欲法でも解くことができる。
「ここに"x"または"o"を配置することで、新たに"x""o"を配置できるマスの減少量が少ないマス」を貪欲に選び、"x"を置くまたは"+"を"o"にしていけばよい。

int N,M;
string S[101],T[101];
int mask[101][101];

void solve(int _loop) {
	int f,i,j,k,l,x,y; char c;
	
	cin>>N>>M;
	FOR(y,N) S[y]=string(N,'.');
	FOR(y,N) FOR(x,N) mask[y][x]=3;
	FOR(i,M) {
		cin>>c>>y>>x;
		y--,x--;
		S[y][x]=c;
		
		if(c=='x' || c=='o') {
			FOR(j,N) mask[y][j] &= 1;
			FOR(j,N) mask[j][x] &= 1;
		}
		if(c=='+' || c=='o') {
			for(j=-N;j<=N;j++) {
				if((y+j)>=0 && (y+j)<N && (x+j)>=0 && (x+j)<N) mask[y+j][x+j] &= 2;
				if((y+j)>=0 && (y+j)<N && (x-j)>=0 && (x-j)<N) mask[y+j][x-j] &= 2;
			}
		}
	}
	FOR(y,N) T[y]=S[y];
	
	retry:
	int mi=10100,cy,cx;
	FOR(y,N) FOR(x,N) if(mask[y][x]&1) {
		int sc=0;
		for(j=-N;j<=N;j++) if(j) {
			if((y+j)>=0 && (y+j)<N && (x+j)>=0 && (x+j)<N && (mask[y+j][x+j]&1)) sc++;
			if((y+j)>=0 && (y+j)<N && (x-j)>=0 && (x-j)<N && (mask[y+j][x-j]&1)) sc++;
		}
		if(sc<mi) mi=sc,cy=y,cx=x;
	}
	if(mi<10100) {
		y=cy, x=cx;
		if(S[y][x]=='.') S[y][x]='+';
		else S[y][x]='o';
		for(j=-N;j<=N;j++) {
			if((y+j)>=0 && (y+j)<N && (x+j)>=0 && (x+j)<N) mask[y+j][x+j] &= 2;
			if((y+j)>=0 && (y+j)<N && (x-j)>=0 && (x-j)<N) mask[y+j][x-j] &= 2;
		}
		goto retry;
	}
	
	retry2:
	mi=10100,cy,cx;
	FOR(y,N) FOR(x,N) if(mask[y][x]&2) {
		int sc=0;
		FOR(j,N) if(j!=x && (mask[y][j]&2)) sc++;
		FOR(j,N) if(j!=y && (mask[j][x]&2)) sc++;
		if(sc<mi) mi=sc,cy=y,cx=x;
	}
	if(mi<10100) {
		y=cy, x=cx;
		if(S[y][x]=='.') S[y][x]='x';
		else S[y][x]='o';
		for(j=-N;j<=N;j++) {
			FOR(j,N) mask[y][j] &= 1;
			FOR(j,N) mask[j][x] &= 1;
		}
		goto retry2;
	}
	
	int pt=0,num=0;
	FOR(y,N) FOR(x,N) {
		if(S[y][x]!=T[y][x]) num++;
		if(S[y][x]=='o') pt+=2;
		if(S[y][x]=='+') pt+=1;
		if(S[y][x]=='x') pt+=1;
	}
	
	_P("Case #%d: %d %d\n",_loop,pt,num);
	FOR(y,N) FOR(x,N) if(S[y][x]!=T[y][x]) _P("%c %d %d\n",S[y][x],y+1,x+1);
}

まとめ

ちょっと変な貪欲をしたので本番通らず。