Codeforces #492 Div1 A. Tesla

色々微妙なところはあるけど一応赤復帰。
http://codeforces.com/contest/995/problem/A

問題

縦4×横Nのグリッド状の土地がある。
中２段のマスにK台の車がある。
最上段と最下段は駐車場で、それぞれ停車位置は決まっている。

各車は同時に１台ずつ隣接マスに移動できる。
ただし最上段・最下段は自身の駐車位置以外移動できない。
最適に移動したとき、全車駐車位置に移動できるか、一例を示せ。

解法

まず初期状態で停車位置に隣接している車はそこに移動してしまおう。
その後、中２段に１マスでも空きがあれば、その中を他の車をぐるぐる回すことでいずれ自身の停車位置の隣接マスに到達するので停車位置に移動できる。
そうでない場合、だれも身動き取れないので解なし。

int N,K;
int A[55][55];
int C[55][55];
vector<vector<int>> V;

void add(int i,int r,int c) {
	int y,x;
	if(i==0) return;
	V.push_back({i,r+1,c+1});
	FOR(y,4) FOR(x,N) if(C[y][x]==i) {
		assert(abs(r-y)+abs(x-c)==1);
		assert(C[r][c]==0);
		swap(C[y][x],C[r][c]);
		return;
	}
	assert(0);
}

void out(){
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl;
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(y,4) FOR(x,N) {
		cin>>A[y][x];
		if(y==1||y==2) C[y][x]=A[y][x];
	}
	
	if(N==1) {
		if(K==2 && A[0][0]!=A[1][0]) return _P("-1\n");
		if(A[0][0]&&A[0][0]==C[2][0]) add(C[2][0],1,0);
		if(A[0][0]&&A[0][0]==C[1][0]) add(C[1][0],0,0);
		if(A[3][0]&&A[3][0]==C[1][0]) add(C[1][0],2,0);
		if(A[3][0]&&A[3][0]==C[2][0]) add(C[2][0],3,0);
		FOR(x,N) assert(A[0][x]==C[0][x]);
		FOR(x,N) assert(A[3][x]==C[3][x]);
		out();
	}
	
	FOR(i,2*N) {
		FOR(x,N) {
			if(A[0][x] && A[0][x]==C[1][x]) add(C[1][x],0,x);
			if(A[3][x] && A[3][x]==C[2][x]) add(C[2][x],3,x);
		}
		FOR(x,2*N) {
			int cy=x/N,cx;
			if(cy==0) cx=x;
			else cx=2*N-1-x;
			if(C[cy+1][cx]==0) break;
		}
		if(x==2*N) return _P("-1\n");
		FOR(j,2*N-1) {
			int cur=(j+x+2*N)%(2*N);
			int nex=(j+x+2*N+1)%(2*N);
			int cy=cur/N,cx;
			if(cy==0) cx=cur;
			else cx=2*N-1-cur;
			int ny=nex/N,nx;
			if(ny==0) nx=nex;
			else nx=2*N-1-nex;
			cy++;
			ny++;
			
			if(C[ny][nx]) add(C[ny][nx],cy,cx);
		}
	}
	FOR(x,N) assert(A[0][x]==C[0][x]);
	FOR(x,N) assert(A[3][x]==C[3][x]);
	out();
}

まとめ

これはBから行きたくなるよね。