第二回全国統一プログラミング王決定戦予選 : E - Non-triangular Triplets

パズル色の強い感じの問題。
https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_e

問題

整数N,Kが与えられる。
K～(K+3N-1)の3N個の整数を1個ずつ使い、N要素の整数列A,B,Cを3つ作りたい。
A[i]+B[i]≦C[i]となるようにできるか。

解法

3N個のうち大きいものN個をCに持ってくるのが良いのは自明である。
Nが決まっているとき、sum(A)+sum(B)≦sum(C)を満たすKの上限を考える。
この上限値をK'としよう。
この時、入力値をN,K'とするときのA,B,Cは必ず構成できる。なのでこれを構成した後、全体を(K'-K)だけ引いて調整しよう。

• Nが偶数のとき、K'はN/2。よってK'～7K'-1までの3N個を分けることにする。
  • K' + 3K' ≦ 5K' で1通り
  • (K'+i) + (4K' + i -1) = 5K' + 2i - 1 でN/2通り
  • (2K'+i) + (3K' + i -1) = 5K' + 2i で(N/2-1)通り
• Nが奇数の時、K'は(N+1)/2。
  • (K' + i - 1) + (4K' + i - 1) = (5K' + 2i - 2) で(N+1)/2通り
  • (2K' + i) + (3K' + i) = (5K' + 2i) で(N-1)/2通り

int N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll A=0,B=0;
	FOR(i,2*N) A+=K+i;
	FOR(i,N) B+=K+2*N+i;
	if(B<A) return _P("-1\n");
	vector<vector<int>> R;
	set<int> V;
	if(N%2==0) {
		if(K>N/2) return _P("0\n");
		int TK=N/2;
		R.push_back({TK,3*TK,5*TK});
		for(i=1;i<=N/2;i++) R.push_back({TK+i,2*N+i-1,TK+i+2*N+i-1});
		for(i=1;i<=N/2-1;i++) R.push_back({N+i,3*N/2+i,5*N/2+2*i});
		FORR(r,R) {
			FORR(a,r) {
				a-=TK-K;
				V.insert(a);
			}
			assert(r[0]+r[1]<=r[2]);
		}
	}
	else {
		if(K>N/2+1) return _P("0\n");
		int TK=N/2+1;
		for(i=1;i<=N/2+1;i++) R.push_back({TK+i-1,2*N+i-1,TK+i+2*N+i-2});
		for(i=1;i<=N/2;i++) R.push_back({N+i,3*N/2+i,5*N/2+2*i});
		FORR(r,R) {
			FORR(a,r) {
				a-=TK-K;
				V.insert(a);
			}
			assert(r[0]+r[1]<=r[2]);
		}
	}
	assert(V.size()==3*N);
	assert(*V.begin()==K);
	assert(*V.rbegin()==K+3*N-1);
	
	
	FORR(v,R) {
		cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl;
	}
	
}

まとめ

sum(A)+sum(B)≦sum(C)となるK'を探すのはいいとして、その後実際にその例を構築するのがパズルっぽい。