Codeforces #592 Div2 G. Running in Pairs

Div2の最終問題にしては簡単。
https://codeforces.com/contest/1244/problem/G

問題

整数N,Kが与えられる。
1～NのPermutationを2つP,Qと構築し、S=sum(max(P[i],Q[i]))を考える。
S=KとなるP,Qを構築せよ。
SがKより小さくしかならない場合、Sが最大となる構成を答えよ。
逆にSがどうしてもKより大きくなる場合、構築不可と答えよ。

解法

Sの最大値と最小値は自明。
最小値はP=Qにすることだし、最大値はPを1～Nの昇順、Qは降順に並べればよい。
その間の値は任意にとれる。

TをKから上記最小値を引いたものとする。すなわちTは最小値から増分である。
まず、Pは1～Nの昇順(P[i]=i)とし、QをNから順にindexを割り当てることにする。
これは単純でT=Q[j]-jとなるような未割当のjを当てよう。
未割り当てて最小のjを当ててもTより小さい場合、T-=Q[j]-jとして取りあえず割り当て、次の数を考える。
T=0になった場合、大きなindexから順に未使用の位置に割り当てればよい。
このケースでは必ずQ[i]≦P[i]となるので、Qの配置はSに影響を与えない。

int N;
ll K;
int P[1010101];
int Q[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll mi=1LL*N*(N+1)/2;
	ll ma=0;
	set<int> S;
	for(i=1;i<=N;i++) {
		ma+=max(i,N+1-i);
		P[i]=Q[i]=i;
	}
	if(K<mi) return _P("-1\n");
	K=min(K,ma);
	cout<<K<<endl;
	K-=mi;
	for(x=1,y=N;K>=y-x&&x<y;x++,y--) {
		K-=y-x;
		swap(P[x],P[y]);
	}
	swap(P[x],P[x+K]);
	
	FOR(i,N) cout<<P[i+1]<<" ";
	cout<<endl;
	FOR(i,N) cout<<Q[i+1]<<" ";
	cout<<endl;
}

まとめ

上位陣はGを10分ぐらいで解いてるけど、まぁそうだよね…。