TopCoderOpen 2020 Round4 : Easy CovidCinema

うーん。
https://community.topcoder.com/stat?c=problem_statement&pm=16405&rd=18191

問題

R*Cのグリッドに、'A'をA個、'B'をB個配置したい。
'A'と'B'が隣接しないような置き方が可能か、可能ならそれを構築せよ。

解法

'A'を置くところと'B'を置くところの境界の作り方を考える。

• 縦に境界となる空マスを置こうとするとR個空マスが必要で、AとBの個数は計(R-1)*C以内なら任意の個数が可能。
• 横に境界となる空マスを置こうとするとC個空マスが必要で、AとBの個数は計(C-1)*R以内なら任意の個数が可能。
• 空マスが斜め、例えば上と左を結ぶように配置すると、X個空マスを使うと左上領域に最大X*(X-1)/2個までAかBを置ける。

上記をそれぞれ試せばよい。

class CovidCinema {
	public:
	int hoge(int R,int C,int N[2],vector<string>& V,int i) {
		int x,y;
		FOR(y,R) FOR(x,C) if(N[i^1]) {
			int ok=1;
			if(V[y][x]!='.') ok=0;
			if(y&&V[y-1][x]=='A'+i) ok=0;
			if(x&&V[y][x-1]=='A'+i) ok=0;
			if(y+1<R&&V[y+1][x]=='A'+i) ok=0;
			if(x+1<C&&V[y][x+1]=='A'+i) ok=0;
			if(ok) {
				V[y][x]='A'+(i^1);
				N[i^1]--;
			}
		}
		return N[0]==0&&N[1]==0;
	}
	vector <string> seat(int R, int C, int A, int B) {
		string S(C,'.');
		vector<string> tmp,NG;
		int y,x,i;
		FOR(y,R) tmp.push_back(S);
		
		int w,h;
		FOR(i,2) { //A,B
			
			for(w=1;w<=C;w++) {
				auto V=tmp;
				int N[2]={A,B};
				FOR(y,R) FOR(x,w) if(N[i]) V[y][x]='A'+i, N[i]--;
				if(hoge(R,C,N,V,i)) return V;
				
			}
			for(h=1;h<=R;h++) {
				auto V=tmp;
				int N[2]={A,B};
				FOR(x,C) FOR(y,h) if(N[i]) V[y][x]='A'+i, N[i]--;
				if(hoge(R,C,N,V,i)) return V;
			}
			for(h=1;h<=min(R,C);h++) {
				auto V=tmp;
				int N[2]={A,B};
				FOR(y,h) FOR(x,h-1-y) if(N[i]) V[y][x]='A'+i, N[i]--;
				if(hoge(R,C,N,V,i)) return V;
			}
		}
		return NG;
	}
}

まとめ

本番斜めのケースを網羅できなかった。