Colopl programming contest 2018 : E - すぬけそだて――わっか――

ずいぶん手間取った…。
https://colopl2018-qual.contest.atcoder.jp/tasks/colopl2018_qual_e

問題

２次元グリッド上で格子点同士を軸に平方な辺で結んだ多角形を考える。
この多角形において、辺が90度曲がる部分のみを頂点と考える。
辺同士は交差してもよいが、同じ向きの辺が重なったり、ある頂点を縦横両方の辺が通過してはならない。

整数Kが与えられるので、平面をK個に分割するような多角形を構成せよ。

解法

Editorialの方がわかりやすいが、一応自分の解法を紹介。

偶数×偶数であるH*W領域を市松模様状に塗るようにしよう。
例えば以下は4*2の図形である。こうすると(H*W-H-W+2)個領域を追加できる。

┏┓
┗╋┓
┏╋┛
┗╋┓
　┗┛

K個を超えない範囲で大きなH,Wを選べば、それだけ多くの領域を追加できる。
さらに領域を追加したい場合、右下角の点から右下に向けて同様の図形を追加すればよい。

int K;

pair<vector<pair<int,int>>,vector<pair<int,int>>> hoge(int H,int W) {
	vector<pair<int,int>> A,B;
	K-=H*W-H-W+2;
	int x,y;
	for(x=W;x>0;x-=2) {
		A.push_back({x,H});
		A.push_back({x-1,H});
		A.push_back({x-1,0});
		A.push_back({x-2,0});
	}
	for(y=0;y<H;y+=2) {
		if(y) B.push_back({0,y});
		B.push_back({0,y+1});
		B.push_back({W,y+1});
		B.push_back({W,y+2});
	}
	return {A,B};
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>K;
	K--;
	vector<pair<int,int>> V;
	int H=0,W=0;
	V.push_back({0,0});
	
	for(x=1500;x>=2;x-=2) {
		H=W=0;
		if(x*x-x-x+2<=K && x*x-x-x+2>0) {
			H=W=x;
		}
		else if(x*(x-2)-x-(x-2)+2<=K && x*(x-2)-x-(x-2)+2>0) {
			H=x,W=x-2;
		}
		if(H&&W) {
			auto P=hoge(H,W);
			vector<pair<int,int>> V2;
			int a=V[0].first,b=V[0].second;
			
			P.first.pop_back();
			FORR(e,P.first) V2.push_back({e.first+a,e.second+b});
			if(V.size()!=1) {
				V.erase(V.begin());
				V.pop_back();
			}
			FORR(v,V) V2.push_back(v);
			FORR(e,P.second) V2.push_back({e.first+a,e.second+b});
			
			swap(V,V2);
			
		}
	}
	
	
	while(K--) {
		x=V[0].first;
		y=V[0].second;
		
		vector<pair<int,int>> V2;
		V2.push_back({x+1,y+1});
		V2.push_back({x+1,y});
		if(V.size()!=1) {
			V.pop_back();
			V.erase(V.begin());
		}
		FORR(v,V) V2.push_back(v);
		V2.push_back({x,y+1});
		V2.push_back({x+1,y+1});
		swap(V,V2);
		reverse(ALL(V));
	}
	
	vector<pair<int,int>> R;
	R=V;
	R.pop_back();
	cout<<R.size()<<endl;
	FORR(v,R) cout<<v.first<<" "<<v.second<<endl;
}

まとめ

Editorialの解法簡潔でいいな。