読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

TopCoder SRM 587 Div2 Hard ThreeColorabilityEasy

SRM

さてDiv2 Hard。
今回妙に簡単だな…。いや、2回凡ミスしたんだけど。
http://community.topcoder.com/stat?c=problem_statement&pm=12699

問題

(0,0)-(H,W)上の格子点を考える。
隣り合う格子点同士を辺でつなぎ、グリッド状にする。
このときできる個々の1x1の正方形について、左下から右上または右下から左上のいずれか対角線を引くように辺でつなぐ。

辺同士でつながった点同士が同じ色にならないように、点を塗り分ける。
点を3色で塗り分けられるか答えよ。

解法

グリッドを構成する各正方形を考える。2点の色が決まると4点の色が確定する。
よって、一番左上の正方形だけ各点の色を決めてしまい、後は接する正方形の色をどんどん確定させていく。
隣同士の正方形は2点を共有するので、ある正方形の4点の色が確定すれば、隣も確定できる。

あとは辺でつながった点が同じ色にならないか適宜チェックしていけばよい。

class ThreeColorabilityEasy {
	public:
	int col[52][52];
	string isColorable(vector <string> cells) {
		int H=cells.size();
		int W=cells[0].size();
		int x,y;
		ZERO(col);
		
		col[0][0]=1;
		if(cells[0][0]=='N') {
			col[1][0]=2;
			col[0][1]=2;
			col[1][1]=3;
		}
		else {
			col[1][0]=2;
			col[0][1]=3;
			col[1][1]=1;
		}
		
		
		FOR(y,H) FOR(x,W) {
			if(x==0 && y==0) continue;
			if(col[x][y]==col[x][y+1]) return "No";
			if(col[x][y]==col[x+1][y]) return "No";
			if(cells[y][x]=='N') {
				if(col[x+1][y]==0) col[x+1][y]=col[x][y+1];
				else if(col[x][y+1]==0) col[x][y+1]=col[x+1][y];
				col[x+1][y+1]=6-col[x][y]-col[x][y+1];
			}
			else {
				if(col[x+1][y]==col[x][y+1]) return "No";
				if(col[x+1][y]==0) col[x+1][y]=6-col[x][y]-col[x][y+1];
				if(col[x][y+1]==0) col[x][y+1]=6-col[x][y]-col[x+1][y];
				col[x+1][y+1]=col[x][y];
			}
		}
		FOR(y,H) if(col[W][y]==col[W][y+1]) return "No";
		FOR(x,W) if(col[x][H]==col[x+1][H]) return "No";
		return "Yes";
	}
};

まとめ

今回はどれもあっさり解けてうれしい。なぜ参加できなかった…。

広告を非表示にする