AtCoder ABC #173 : E - Multiplication 4

FよりEに手間取った。
https://atcoder.jp/contests/abc173/tasks/abc173_e

問題

N個の整数が与えられる。
K個の積のうち最大値となるものについて、mod 10^9+7の値を求めよ。

解法

正の数が1個もない場合、Kが偶数なら絶対値が大きい順、奇数なら小さい順に掛けていこう。

そうでない場合、とりあえず絶対値が大きいK個を掛ける。
この時負の数が奇数個入っているなら、それを何とかすることを考える。

以下のいずれか、可能なもののうち積が大きくなる方を取ろう。

• K個中にある負の数のうち絶対値が最小のものを外し、K個外にある正の数のうち絶対値が最大のものを入れる
• K個中にある正の数のうち絶対値が最小のものを外し、K個外にある負の数のうち絶対値が最大のものを入れる

int N,K;
pair<int,int> A[202020];
const ll mo=1000000007;

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;
	
	cin>>N>>K;
	int p=0;
	FOR(i,N) {
		cin>>x;
		A[i]={abs(x),x};
		if(x>0) p=1;
	}
	sort(A,A+N);
	
	ll ret=1;
	if(p==0 || K==N) {
		if(K%2==0) {
			FOR(i,K) (ret*=(mo+A[N-1-i].second))%=mo;
		}
		else {
			FOR(i,K) (ret*=(mo+A[i].second))%=mo;
		}
	}
	else {
		int pm=mo,mm=0;
		int s=0;
		FOR(i,K) {
			(ret*=(mo+A[N-1-i].second))%=mo;
			if(A[N-1-i].second>0) pm=A[N-1-i].second;
			if(A[N-1-i].second<0) mm=A[N-1-i].second, s^=1;
		}
		
		if(ret && s==1) {
			int p2=-1,m2=1,z=0;
			for(i=N-1-K;i>=0;i--) {
				if(A[i].second>0&&p2==-1) p2=A[i].second;
				if(A[i].second<0&&m2==1) m2=A[i].second;
				if(A[i].second==0) z++;
			}
			
			if((mm==0 || p2==-1) && (pm==mo||m2==1)) {
				if(z) ret=0;
			}
			else if(mm==0 || p2==-1) {
				(ret*=(m2+mo))%=mo;
				(ret*=modpow(pm))%=mo;
			}
			else if(pm==mo||m2==1) {
				(ret*=(p2))%=mo;
				(ret*=modpow(mm+mo))%=mo;
			}
			else if(1LL*p2*pm>=1LL*m2*mm) {
				(ret*=(p2))%=mo;
				(ret*=modpow(mm+mo))%=mo;
			}
			else {
				(ret*=(m2+mo))%=mo;
				(ret*=modpow(pm))%=mo;
			}
		}
	}
	cout<<ret<<endl;
	
}

まとめ

やりたいことはわかってもコードを書くのが面倒な問題。