Google Code Jam 2022 Round 2 : A. Spiraling Into Control

どうにかRound3進出。
https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec/0000000000b15a74

問題

奇数Nと、正整数Kが与えられる。
N*Nのグリッドを考える。
左上マスに1が書かれ、以後時計回りに渦巻き状に2,3,4...と数値が埋められ、真ん中のマスにN^2が書かれている。

左上マスから、書かれた数値が増える方向で、隣接マスをたどり真ん中のマスに移動することを考える。
ちょうどK回の移動で真ん中に到達可能か。
1よりも大きな数値の増加を伴う移動をショートカットと呼ぶことにする。
所定の移動が可能なら、ショートカット箇所を列挙せよ。

解法

通常隣接マスをたどると数値は１増える。
今回K回の移動で追えるためには、ショートカットで(元々の1増加に加えて)計(N^2-K)分だけ数値を増加させることを考える。

数値が同じ分増加するなら、早めにショートカットするのが良い。
また、それは数値の増分に渦巻き状にマス目をたどっていくと、90度進行方向を変えた直後に行うのが良い。
よってそのようなショートカット箇所を列挙し、計(N^2-K)分の増加が可能なように貪欲にショートカット位置を求めて行こう。

int N,K;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	vector<pair<int,int>> cand;
	ll s=1;
	for(i=N;i>1;i-=2) {
		ll nex=s+(i-1)*4;
		FOR(j,4) {
			int a=nex+j*(i-3);
			int b=s+1+j*(i-1);
			if(a-b>2) cand.push_back({a-b-1,b});
		}
		s=nex;
	}
	
	int skip=N*N-1-K;
	int cur=1;
	vector<pair<int,int>> res;
	FORR2(a,b,cand) {
		if(cur>b) continue;
		if(skip>=a) {
			res.push_back({b,a+b+1});
			skip-=a;
			cur=a+b+1;
		}
	}
	
	
	if(skip) {
		cout<<"Case #"<<_loop<<": IMPOSSIBLE"<<endl;
	}
	else {
		cout<<"Case #"<<_loop<<": "<<res.size()<<endl;
		FORR2(a,b,res) cout<<a<<" "<<b<<endl;
	}
	
}

まとめ

コード量はそこまで大きくないけど、細かいミスを避けようとすると割と慎重に書く必要がある。