kmjp's blog

競技プログラミング参加記です

Codeforces #231 Div2. C. Dominoes

CF231はDiv2回に参加。
Eは普通に回答しきれず、Cは凡ミスと微妙な出来でした。
http://codeforces.com/contest/394/problem/C

問題

正方形が2つくっついてできたドミノが与えられ、長方形となるように並べていく。
全てのドミノは縦1マス横2マスとなる向きで並べなければならないが、180度回転させることは認められている。

ドミノの各マスには0か1の番号が振られている。
最終的にできる長方形において、各列に登場する1の数の最大値が最小となるようなドミノの並べ方を答えよ

解法

"10"のドミノは"01"と縦に重ねると、2列とも1の数が1増加するだけで済む。
よって、"10"と"01"はセットにして左上から順に敷き詰めていこう。
"11"は逆に右下から順に敷き詰めていけばよい。

int H,W;
int type[3];
string S;
string RS[1000][1000];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) {
		cin>>S;
		if(S=="11") type[2]++;
		else if(S=="00") type[0]++;
		else type[1]++;
		RS[y][x]="00";
	}
	
	for(y=0;y<H;y+=2) {
		FOR(x,W) {
			if(type[1] && y<H) RS[y][x]="10",type[1]--;
			if(type[1] && y+1<H) RS[y+1][x]="01",type[1]--;
		}
	}
	for(y=H-1;y>=0;y--) for(x=W-1;x>=0;x--) {
		if(type[2] && RS[y][x]=="00") RS[y][x]="11",type[2]--;
	}
	
	
	FOR(y,H) {
		FOR(x,W) _P("%s ",RS[y][x].c_str());
		_P("\n");
	}
	
}

まとめ

本番は敷き詰めの順番を微妙に間違えてミス。