Codeforces #785 : Div2 F. Anti-Theft Road Planning

Div2のInteractiveボス問の割にシンプル。
https://codeforces.com/contest/1673/problem/F

問題

N*Nのグリッドが与えられる。
まず、隣接セル間の距離を任意の非負整数値に設定できるものとする。

一連のセルをたどるコストは、隣接セル間の距離のxorとする。
左上のセルから、あるセルまで至るコストが1つ示されるので、移動先セルの位置を答えよ。

解法

コストが列番号+((行番号)*1024)となるように、距離を設定すればよい。

int N,K;

int R[33],RS[33];
int C[33],CS[33];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=32;i++) {
		x=i;
		R[i]=1;
		while(x%2==0) x/=2,R[i]*=4;
		RS[i]=RS[i-1]^R[i];
		C[i]=R[i]*2;
		CS[i]=RS[i]*2;
	}
	
		
	
	
	cin>>N>>K;

	FOR(y,N) {
		FOR(x,N-1) cout<<R[x+1]<<" ";
		cout<<endl;
	}
	FOR(y,N-1) {
		FOR(x,N) cout<<C[y+1]<<" ";
		cout<<endl;
	}
	
	int pre=0;
	while(K--) {
		cin>>k;
		FOR(y,N) FOR(x,N) {
			if((RS[x]|CS[y])==(pre^k)) cout<<y+1<<" "<<x+1<<endl;
		}
		pre^=k;
	}
	
}

まとめ

気付いてしまえば簡単。