yukicoder : No.1087 転倒数の転倒数

なるほど…。
https://yukicoder.me/problems/no/1087

問題

数列Xに対し、f(X)はXの転倒数を示すとする。
以下を満たすN*Nの行列Sを構築せよ。

• 数列Aを、A[i]=f(Sのi行目)とし、- 数列Bを、B[i]=f(Sのi列目)とする。このときf(A)+f(B)=Kである。

解法

まず転倒数が与えられたとき、それが要素数Nに対しN*(N-1)/2以下ならそれを満たす数列は作れることを前提とする。

K≦N*(N-1)/2の場合

f(A)=K、f(B)=0とすることを考える。
まずf(A)=Kを満たすAを作ろう。全要素N-1以下で作ることができる。
次に、A[i]=f(Sのi行目)となるようSの各行を作ろう。やはり全要素N-1以下である。

あとはf(B)=0を確実に満たすようにすればよいので、r行目にN*rを加えておく。

N*(N-1)/2＜K≦N*(N-1)の場合

以下Editorialのまま。
N行目以外にS[i][i]=1を入れてみる。その他は0とする。
こうなるとAもBもN-1,N-2,N-3,...,0となるので、f(A)+f(B)=N*(N-1)となる。
ここで、SのN行・N列目以外の部分で、後ろから順に0を1つ1にしてみる。
そうすると、対角成分の上か下かによって、A,Bのいずれか片方だけ要素が1増え、f(A)+f(B)が1減る。
なのでf(A)+f(B)=Kになるまで要素を1にしていけばよい。

int N,K;
int A[1010][1010];

int FA[1010],FB[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	
	
	if(K<=N*(N-1)/2) {
		for(y=N-1;y>0;y--) {
			x=min(K,y);
			K-=x;
			FA[N-1-x]=y;
		}
		for(y=N-1;y>=0;y--) {
			A[y][N-1-FA[y]]=1;
			FOR(x,N) A[y][x]+=y*N;
		}
	}
	else if(K<=N*(N-1)) {
		K-=N*(N-1);
		FOR(i,N-1) A[i][i]=1;
		for(x=N-2;x>=0;x--) {
			for(y=x-1;y>=0;y--) {
				if(K<0) A[y][x]=1,K++;
				if(K<0) A[x][y]=1,K++;
			}
		}
		
		
	}
	else {
		cout<<"No"<<endl;
		return;
	}
	
	
	cout<<"Yes"<<endl;
	FOR(y,N) {
		FOR(x,N) cout<<A[y][x]<<" ";
		cout<<endl;
	}
}

まとめ

結構シンプルな回答になるね。