うーん。
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; } }
まとめ
本番斜めのケースを網羅できなかった。