AtCoder ARC #148 : E - ≥ K

こういうのどこから手を付けてよいかわからんな…。
https://atcoder.jp/contests/arc148/tasks/arc148_e

問題

整数列Aと整数Kが与えられる。
Aを並べ替えたとき、隣接要素の和が必ずK以上であるようなものは何通りか。

解法

Aの要素を抜き出してBを作ることにする。
Aの最小値をL、最大値をRとすると、

• L+R＜KならL
• L+R≧KならR

をAから抜き出しBに挿入していこう。
その際、「Bのうちこの位置ならLまたはRを挿入してよい場所」はL,R挿入のために1増減するので、その場所を更新しながらそれらの積を取る。

int N,K;
const ll mo=998244353;
vector<ll> L,R;

const int NUM_=1400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>K;
	map<int,int> M;
	FOR(i,N) {
		ll x;
		cin>>x;
		M[x]++;
		x=2*x-K;
		if(x>=0) R.push_back(x);
		else L.push_back(x);
	}
	sort(ALL(L));
	sort(ALL(R));
	
	int space=1;
	ll ret=1;
	FORR(a,L) {
		while(R.size()&&R.back()>=-a) {
			(ret*=space++)%=mo;
			R.pop_back();
		}
		(ret*=space--)%=mo;
	}
	FOR(i,R.size()) (ret*=space++)%=mo;
	
	FORR2(a,b,M) (ret*=factr[b])%=mo;
	
	cout<<ret%mo<<endl;
	
	
}

まとめ

最終的なコードは短いんだけどね。