Kodamanと愉快な仲間たち : X - Trypophobia

これはパズル的な問題。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/trypophobia

問題

正整数Nが与えられる。
N*(N+1)格子状に点が並んでいる。
この点を2つずつペアを組んだ時、マンハッタン距離がiになるものが(N+1-i)個になるものを構成せよ。

解法

以下はEditorialそのまんまである。
N%4=2の時は解なし。この時ペアのマンハッタン距離の総和は奇数になるが、問題の趣旨は総和が偶数になることを要求しており矛盾する。
あとは残りのケースを示す。
以下、x行目y列の格子点を(x,y)と示す。(0-originとする)

• N%4=1or3の時
  • (N+1)列を2列ずつ分け、隣同士で高さをずらすようにする。
  • (2x,y)-(2x+1,(y+x)%N)をつなぐようにすると、一番左2列は距離1がN個、次の2列は距離2が(N-1)個、距離Nが1個…というようになる。
• N%4=0の時
  • (N+1)列を2列ずつ分け、隣同士で高さをずらすようにする基本戦略は同じ。ただNが偶数なので1列余る。
  • その1列では、縦に2ずつ離れた点をつなぎ距離2の組をN/2個作っておく。
  • 次の2列では、距離Nを1個、N/2+1をN/2個、距離2をN-(N/2+1)個作っておく。
  • あとは距離3～(N-2)を作ればいいので、(2x,y)-(2x+1,(y+i)%N)をi=3～N/2まで2列ごとにずらして作っていく。

int N;
int C[10101];
set<pair<int,int>> S;
void out(int x1,int y1,int x2,int y2) {
	C[abs(x1-x2)+abs(y2-y1)]++;
	assert(S.count({x1,y1})==0);
	assert(S.count({x2,y2})==0);
	assert(x1>=1 && x1<=N+1);
	assert(x2>=1 && x2<=N+1);
	assert(y1>=1 && y1<=N);
	assert(y2>=1 && y2<=N);
	S.insert({x1,y1});
	S.insert({x2,y2});
	cout<<y1<<" "<<x1<<" "<<y2<<" "<<x2<<endl;
}


void solve() {
	
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N%4==2) {
		cout<<"No"<<endl;
	}
	else if(N%2) {
		cout<<"Yes"<<endl;
		for(x=1;x<=N+1;x+=2) FOR(y,N) out(x,y+1,x+1,(y+(x/2))%N+1);
	}
	else {
		cout<<"Yes"<<endl;
		FOR(y,N) out(1,y+1,2,y+1);
		FOR(y,N/4) {
			out(3,y*4+1,3,y*4+3);
			out(3,y*4+2,3,y*4+4);
		}
		out(4,N,5,1);
		if(N==4) {
			out(4,1,5,3);
			out(4,2,5,4);
			out(4,3,5,2);
		}
		else {
			for(y=1;y<=N-1;y++) {
				if(y<=N/4) out(4,y,4,y+N/2+1);
				else if(y>N/2 && y-(N/2+1)<=N/4 && y-(N/2+1)>=1) continue;
				else out(4,y,5,y+1);
			}
			for(y=2;y<2+N/4;y++) out(5,y,5,y+N/2+1);
		}
		
		for(x=6;x<=N+1;x+=2) {
			FOR(y,N) out(x,y+1,x+1,(y+(x/2-1))%N+1);
		}
		
	}
	for(i=1;i<=N;i++) assert(C[i]==N+1-i);
}

まとめ

こういうのは1000ptが妥当なのかとうか判断が付かないな…。