AtCoder Beginner Contest 173 ABC173 E - Multiplication 4

問題へのリンク

解説

まずの場合は調整しようがないのでやります。負の数が奇数個あったら負にします。

以降はとします。

が奇数の場合、正の数が存在するならその最大値をまず使うことにします。 すると、以降に選ぶ数が偶数個になります。 正の数が存在しないなら、0以下の数から個選びます。が個以上あるなら、がないなら負の数で絶対値が小さい方から選びます。

ここからは選ぶ個数が偶数になっているので、正の数からつ、負の数からつ、絶対値の大きい方から選んでいくことで結果を正にできます。個ずつの積を見て、正と負で大きい方を選ぶ貪欲をしていくことで答えることができます。

追記

なぜ奇数のときに正の数の最大を入れたあと2個ずつ入れていいのかについて少し考えたのでメモしておきます。

まず、結果が正になるので、負の数は必ず偶数個です。このとき、が奇数なら正の数も奇数個であり、が偶数なら正の数の偶数個です。よって、が奇数のときは正の数を個以上入れることになり、その個は最大値となります。そのあとの個ずつは、正負どちらでもよいので、大きい方から見ていくために貪欲で選んでよいということです。

実装

最後の個ずつ進むパートにおいては、実装上煩雑になるのを防ぐためにあらかじめを多く後ろに置いておき、足りなくなったら結果がになるようにしたり、片方だけ足りなくなったらもう片方のみを選べるようにしたりしています。いわゆる番兵です。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
const ll MOD = 1e9 + 7;
struct mint {
    /*省略*/
};



int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> s(2e5,0), f(2e5,0);
    vector<ll> A;
    ll cntz = 0, cntpl = 0, cntmi = 0;
    rep(i,N){
        ll a;
        cin >> a;
        A.push_back(abs(a));
        if(a == 0)cntz++;
        if(a > 0){
            s.push_back(a);
            cntpl++;
        }
        if(a < 0){
            f.push_back(abs(a));
            cntmi++;
        }
    }
    sort(all(A));
    sort(all(s), greater<>());
    sort(all(f), greater<>());
    mint ans = 1;
    if(N == K){
        rep(i,K)ans *= A[i];
        if(cntmi & 1)ans = -ans;
        cout << ans << endl;
        return 0;
    }
    // K < N;
    ll idx[] = {0,0};
    if(K&1){
        if(cntpl > 0)ans *= s[idx[0]++];
        else{
            rep(i,K)ans *= A[i];
            ans = -ans;
            cout << ans << endl;
            return 0;
        }
    }
    // 残りの偶数個を決めていく
    ll len = K / 2;
    while(len--){
        ll tmp[2];
        tmp[0] = s[idx[0]] * s[idx[0]+1];
        tmp[1] = f[idx[1]] * f[idx[1]+1];
        if(tmp[0] < tmp[1]){
            ans *= tmp[1];
            idx[1] += 2;
        }
        else{
            ans *= tmp[0];
            idx[0] += 2;
        }
    }
    cout << ans << endl;
}