kmjp's blog

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

TopCoder SRM 741 Div1 Medium BoardCoveringDiv1

SRM

これ解けなかったので本番出てたらレート落ちてたな。
http://community.topcoder.com/stat?c=problem_statement&pm=15144

問題

N*Nのサイズのグリッドのうち、指定された１マスを除いたグリッドを考える。
このグリッドをトリオミノで覆い、かつ10色以内で塗り分ける例を示せ。

解法

トリオミノでの覆い方を決めれば、あとはDiv2 Hardと同じ。
TopCoder SRM 741 Div2 Hard BoardCoveringDiv2 - kmjp's blog

N=1の場合は自明。また、Nが3の倍数のときはマスの数が３の倍数ではないので解なしなのも自明。
以下はNが2以上かつNが3の倍数でない場合を考える。

トリオミノでうまく埋められなかったので自分はEditorialを参照した。
大きな形状を考えるのは面倒なので、まず問題サイズを小さくしよう。
以下の要領でサイズを小さくする。

  • 列数が5以上で、左３列または右３列に除かれるマスが無いなら、その３列はトリオミノで自明に埋め列数を３減らす
  • 行についても同様

こうすると残る形状は2*2、2*5、4*4、5*5のいずれかである。
取り除くマスの位置のバリエーションも少ないので、個別に決め打ちしてしまおう。

2*2、2*5、4*4は一筆書きパターンがあるので、指定されたマスを除いたのち残りを一筆書き順に３マスずつ区切ればよい。
yukicoder : No.85 TVザッピング(1) - kmjp's blog

5*5のときは除くマスは中央一択なので、その１パターンだけ頑張って構築しよう。

class BoardCoveringDiv1 {
	public:
	vector <string> make(int N, int R, int C) {
		if(N%3==0) return {};
		vector<string> V;
		int i,j,k,y,x;
		FOR(i,N) V.push_back(string(N,'.'));
		V[R][C]='#';
		
		if(N==1) return V;
		
		vector<pair<int,int>> cand;
		int SL=0,SR=N-1;
		int SU=0,SD=N-1;
		while(SR-SL>=4 && SL+3<=C) {
			for(y=SU;y<=SD;y++) cand.push_back({SL,y}), cand.push_back({SL+1,y}), cand.push_back({SL+2,y});
			SL+=3;
		}
		while(SR-SL>=4 && C<=SR-3) {
			for(y=SU;y<=SD;y++) cand.push_back({SR,y}), cand.push_back({SR-1,y}), cand.push_back({SR-2,y});
			SR-=3;
		}
		while(SD-SU>=4 && SU+3<=R) {
			for(x=SL;x<=SR;x++) cand.push_back({x,SU}), cand.push_back({x,SU+1}), cand.push_back({x,SU+2});
			SU+=3;
		}
		while(SD-SU>=4 && R<=SD-3) {
			for(x=SL;x<=SR;x++) cand.push_back({x,SD}), cand.push_back({x,SD-1}), cand.push_back({x,SD-2});
			SD-=3;
		}
		
		if((SR-SL+1)*(SD-SU+1)%2==0) {
			vector<pair<int,int>> C2;
			if((SD-SU+1)%2==0) {
				for(y=SU;y<=SD;y++) {
					if((y-SU)%2==0) {
						for(x=SR-1;x>=SL;x--) C2.push_back({x,y});
					}
					else {
						for(x=SL;x<=SR-1;x++) C2.push_back({x,y});
					}
				}
				for(y=SD;y>=SU;y--) C2.push_back({SR,y});
			}
			else {
				for(x=SL;x<=SR;x++) {
					if((x-SL)%2==0) {
						for(y=SD-1;y>=SU;y--) C2.push_back({x,y});
					}
					else {
						for(y=SU;y<=SD-1;y++) C2.push_back({x,y});
					}
				}
				for(x=SR;x>=SL;x--) C2.push_back({x,SD});
			}
			auto it=find(ALL(C2),make_pair(C,R));
			rotate(C2.begin(),it,C2.end());
			C2.erase(C2.begin());
			FORR(c,C2) cand.push_back(c);
		}
		else if(SR-SL==4 && SD-SU==4) {
			for(x=SL;x<=SR;x++) cand.push_back({x,SU});
			for(x=SR;x>=SL;x--) cand.push_back({x,SU+1});
			cand.push_back({SL,SU+2});
			cand.push_back({SL+1,SU+2});
			cand.push_back({SL+1,SU+3});
			cand.push_back({SL,SU+3});
			cand.push_back({SL,SU+4});
			cand.push_back({SL+1,SU+4});
			cand.push_back({SL+2,SU+4});
			cand.push_back({SL+2,SU+3});
			cand.push_back({SL+3,SU+3});
			cand.push_back({SL+3,SU+4});
			cand.push_back({SL+4,SU+4});
			cand.push_back({SL+4,SU+3});
			cand.push_back({SL+4,SU+2});
			cand.push_back({SL+3,SU+2});
		}
		
		for(i=0;i<cand.size();i+=3) {
			set<char> S;
			for(j=i;j<i+3;j++) {
				int dd[4]={0,1,0,-1};
				FOR(k,4) {
					int ty=cand[j].second+dd[k];
					int tx=cand[j].first+dd[k^1];
					if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
					S.insert(V[ty][tx]);
				}
			}
			char ret='0';
			while(S.count(ret)) ret++;
			for(j=i;j<i+3;j++) V[cand[j].second][cand[j].first]=ret;
		}
		return V;
	}
}

まとめ

色んな一筆書きパターンを考えちゃったよ…。