Codeforces ECR #117 : G. Max Sum Array

ECR最終問でこの短さは珍しい。
https://codeforces.com/contest/1612/problem/G

問題

整数列Aには、1～Mの値がそれぞれ指定した数格納されている。
f(A)は、同じ値を持つ2要素について、indexの差の総和を取ったものとして定義される。

f(A)の最大値と、その値をとるAのパターンは何通りかをそれぞれ求めよ。

解法

残り最多の個数のものを両端に置くのが良い。
という点に気付くと、後は個数最多のものが同着k個あれば、両端にそれらを1個ずつ置く置き方(k!)^2通りがあり得る。
また、その結果最多の個数のものは2個ずつ数が減るので、あとは同様に残りの中で最多の個数のものを順次処理して行けばよい。

int M;
ll num[1505050];
const ll mo=1000000007;
ll dp[1010101];
ll fact[1010101];
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	fact[0]=1;
	FOR(i,1010000) fact[i+1]=fact[i]*(i+1)%mo;
	
	cin>>M;
	ll tlen=0;
	FOR(i,M) {
		cin>>x;
		tlen+=x;
		num[x]++;
	}
	ll dif=0;
	ll pat=1;
	for(i=1000000;i>=1;i--) {
		num[i]+=num[i+2];
		(pat*=fact[num[i]])%=mo;
		if(i>1) {
			(pat*=fact[num[i]])%=mo;
			tlen-=2*num[i];
			(dif+=(num[i]+tlen)%mo*(i-1)%mo*num[i])%=mo;
			
		}
		
	}
	
	cout<<dif<<" "<<pat<<endl;
}

まとめ

最初の気付きが付けば、後はだいぶ楽。
とはいえ、そこが難しいよねぇ。