これはパズル的な問題。
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が妥当なのかとうか判断が付かないな…。