https://atcoder.jp/contests/abc173/tasks/abc173_e

解説

https://atcoder.jp/contests/abc173/submissions/15024432

貪欲法。コーナーケースが多く、実装も大変。

まず簡単な問題で考えてみる。
全て正の数であれば、数が大きいものから貪欲にK個とっていけばいい。
今回は負の数があるのが、問題。
負の数であっても、絶対値が大きいものから貪欲にK個とって、総積が正であれば、最善であるのは明らかである。
総積が負の場合、次のどちらかの操作を行って大きいものが最適な選び方となる。

既に選択済みの負の数(m1)を取り除いて、選択されていない最大の正の数か0(p1)を入れる
既に選択済みの正の数(p2)を取り除いて、選択されていない最小の負の数か0(m2)を入れる

このとき、どちらの方が結果が良くなるかは、abs(p1/m1)とabs(m2/p2)を比較すればいい。
絶対値が大きいほうが最適なので、方針1の方がいい条件は、
abs(p1/m1) > abs(m2/p2)
absは使えないので展開するのだが、どちらも正と負の割り算なので、全体は負となる。よって、absを展開すると、不等号は逆転して、
p1/m1 < m2/p2
整数で割ると誤差が出るので、×m1p2で分数を消す。これは負の数なので、不等号は逆転して、
p1p2 > m1m2
これを判断材料とする。

どちらの方針がやれるかどうかも判定して場合分けする。

ok1 := 方針1ができる
ok2 := 方針2ができる

なお、どちらの方針もできない場合は、配列Aが全て負の数の場合である（コーナーケース）。
その場合は、絶対値が大きいものからK個選ぶと、負の数として小さくなってしまうので、絶対値が小さいものからK個選ぶことにする。

int N, K, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N, [&](int a, int b) { return abs(a) > abs(b); });

    int cnt = 0;
    mint ans = 1;

    rep(i, 0, K) {
        if (A[i] < 0) cnt++;
        ans *= mint(A[i]);
    }

    if (cnt % 2 == 1) {
        // 負→正
        int m1 = inf, p1 = inf;
        rep(i, 0, K) if (A[i] < 0) m1 = A[i];
        rep(i, K, N) if (0 <= A[i]) {
            p1 = A[i];
            break;
        }
        bool ok1 = (m1 != inf) && (p1 != inf);

        // 正→負
        int p2 = inf, m2 = inf;
        rep(i, 0, K) if (0 < A[i]) p2 = A[i];
        rep(i, K, N) if (A[i] <= 0) {
            m2 = A[i];
            break;
        }
        bool ok2 = (m2 != inf) && (p2 != inf);

        if (ok1 && ok2) {
            if (1LL * p1 * p2 > 1LL * m1 * m2) ans = ans * p1 / m1; // 負→正がいい
            else ans = ans * m2 / p2; // 正→負がいい
        }
        else if(ok1) ans = ans * p1 / m1;
        else if(ok2) ans = ans * m2 / p2;
        else {
            sort(A, A + N, greater<int>());
            ans = 1;
            rep(i, 0, K) ans *= A[i];
        }
    }

    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

Multiplication 4 [AtCoder Beginner Contest 173 E]

解説