Google Code Jam 2019 Round 1A : A. Pylons

色々変にはまって全完できず。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e03

問題

H*Wの二次元グリッドがある。
このセル群を、各セルを１回ずつ経由し、全セルを通るようにしたい。
その際、最初のセルと最後のセルは任意に選択できる。

ただし、移動の際に移動前と移動後のセルが、上下左右またはちょうど斜め方向に位置することは許容されない。
H,Wが与えられた際その例を示せ。

解法

H≦Wとする。
以下(r,c)をr行c列目のセルの位置とする。

H=2の場合

• W＜5の場合解なし。
• W≧5の場合、(1,1)(2,4)(1,2)(2,5)...(1,x)(2,x+3)(1,x+1)(2,x+4)....と通っていき、(1,W-2)に到達したら(2,1)(1,W-1)(2,2)(1,W)(2,3)と移動すればよい。

H=3の場合

• W＜4の場合解なし。
• W≧4の場合、(1,1)(2,3)(3,1)(1,2)(2,4)(3,2)...(1,x)(2,x+2)(3,x)(1,x+1)(2,x+3)(3,x+1)...と移動すればよい。ただしx+2がWを超える場合は(2,1)ないし(2,2)とする。

H≧4の場合

• (1,x)(2,x+2)(3,x+4)....とし、(H,x+2*(H-1))に到達したら(1,x+2*(H-1)+1)に遷移するようにした。
• 4*4の場合はこれではうまくいかないのでそこは手入力。

int H,W;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	
	cin>>H>>W;
	int rev=0;
	vector<pair<int,int>> R;
	if(H>W) {
		swap(H,W);
		rev=1;
	}
	
	if(H==2) {
		if(W<5) {
			_P("Case #%d: IMPOSSIBLE\n",_loop);
			return;
		}
		x=1;
		R.push_back({1,x});
		while(x+3<=W) {
			R.push_back({2,x+3});
			x++;
			R.push_back({1,x});
		}
		R.push_back({2,1});
		R.push_back({1,W-1});
		R.push_back({2,2});
		R.push_back({1,W});
		R.push_back({2,3});
		
	}
	else if(H==3) {
		vector<int> C;
		if(W<4) {
			_P("Case #%d: IMPOSSIBLE\n",_loop);
			return;
		}
		FOR(x,W) {
			R.push_back({1,x+1});
			R.push_back({2,(x+2)%W+1});
			R.push_back({3,x+1});
		}
	}
	else if(H==4&&W==4) {
		R.push_back({1,1});		R.push_back({2,3});		R.push_back({3,1});		R.push_back({4,3});
		R.push_back({1,2});		R.push_back({2,4});		R.push_back({3,2});		R.push_back({4,4});
		R.push_back({1,3});		R.push_back({2,1});		R.push_back({3,3});		R.push_back({4,1});
		R.push_back({3,4});		R.push_back({2,2});		R.push_back({1,4});		R.push_back({4,2});
	}
	else {
		int vis[20]={};
		y=0;
		FOR(i,H) {
			while(vis[y]) y=(y+1)%H;
			vis[y]=1;
			FOR(x,W) {
				R.push_back({y+1,x+1});
				y=(y+2)%H;
			}
		}
	}
	if(rev) {
		swap(H,W);
		FORR(r,R) swap(r.first,r.second);
	}
	
	_P("Case #%d: POSSIBLE\n",_loop);
	FORR(r,R) _P("%d %d\n",r.first,r.second);
}

まとめ

Bも変なところで苦戦して時間が足りなかった…。