TopCoderOpen 2020 Round2B : Medium RoomPairs

これ本番で解きたくないな…。
https://community.topcoder.com/stat?c=problem_statement&pm=16282&rd=18074

問題

整数R,C,Nが与えられる。
R*Cのグリッドにおいて、隣接セルの間に仕切りを任意に入れる。
連結したセルを部屋とみなすとき、互いに仕切りを挟んで隣接する部屋の対がN個となるような仕切りの入れ方を構成せよ。

解法

R=C=N=2の時は解なし。

それ以外の場合、以下の通り貪欲法が取れる。
左上のセルから順に、各セルの四方を仕切りで囲うか考えよう。
この時、隣接部屋対は1か2増える。そこでNがそれ以上なら囲ってしまおう。
ただし、途中N=1になったら、一番右下を同様に囲ってそこで終えてしまおう。

vector<string> S;
int sp[31][31];

class RoomPairs {
	public:
	vector <string> construct(int R, int C, int N) {
		S.clear();
		int x,y;
		
		ZERO(sp);
		
		if(N==2) {
			if(R==2&&C==2) return {};
			sp[0][0]=sp[R-1][C-1]=1;
		}
		else if(C>R) {
			FOR(y,R) {
				FOR(x,C) {
					int add=2;
					
					if(N==1 && y<R-1&&x<C-1) {
						sp[R-1][C-1]=1;
						N-=1;
					}
					
					if(x==0 || y==R-1) add--;
					if(N>=add) sp[y][x]=1,N-=add;
				}
			}
		}
		else {
			FOR(x,C) {
				FOR(y,R) {
					int add=2;
					if(N==1 && y<R-1&&x<C-1) {
						sp[R-1][C-1]=1;
						N-=1;
					}
					
					if(y==0 || x==C-1) add--;
					if(N>=add) sp[y][x]=1,N-=add;
				}
			}
		}
		
		
		FOR(y,2*R+1) {
			S.push_back(string(2*C+1,' '));
			if(y%2==0) {
				for(x=0;x<=2*C;x+=2) S[y][x]='+';
			}
			if(y==0 || y==2*R) for(x=1;x<=2*C;x+=2) S[y][x]='-';
			if(y%2) S[y][0]=S[y][2*C]='|';
		}
		
		FOR(y,R) FOR(x,C) {
			if(y+1<R && (sp[y][x]||sp[y+1][x])) S[2*(y+1)][x*2+1]='-';
			if(x+1<C && (sp[y][x]||sp[y][x+1])) S[y*2+1][2*(x+1)]='|';
		}
		
		FORR(s,S) cout<<s<<endl;
		return S;
	}
}

まとめ

R=C=N=2、本番で気づける気がしない。