AtCoder水色になりました2回目

前回 hotarunx.hatenablog.com

f:id:hotarunx:20200706004439j:plain f:id:hotarunx:20200706004456j:plain f:id:hotarunx:20200706004511j:plain

AtCoder水色になりました。約4か月死闘しました。

書くことがないのでここからABC173の感想とE問題の考察を書きます。

ABC173 - AtCoder Beginner Contest 173

Eをブザービートしてなんとか水パフォを取りました。きつかった🥺。 Dはわかりませんでした。

E - Multiplication 4

問題へのリンク

Difficulty: 1637

考察編

やるだけなんだけど難しい。

絶対値が大きい要素を選んで、選んだ要素の積が負だったら、選び方を少し変えて正にしたらよさそう。

前処理として $A$ を絶対値が大きい順にソート。

$A_1,\cdots,A_K$ を選んで、選んだ要素の積が正ならば答え。選んだ要素の積が負なら、選び方を少しだけ変更して値が小さくなる代わりに符号を反転させる。具体的にはこの操作をする。

$A_1,\cdots,A_K$ の最小の正の要素を選ばないようにして、 $A_{K+1},\cdots,A_N$ の最小の負の要素を選ぶ。
$A_1,\cdots,A_K$ の最大の負の要素を選ばないようにして、 $A_{K+1},\cdots,A_N$ の最大の正の要素を選ぶ。

もしこの操作をしても選んだ要素の積を正にできないならば、選んだ要素の積は負。 $A_{N-K},\cdots,A_N$ を選ぶ。

実装編

これがコードです。初WAとACのDiffにしています。

こんなバグを埋め込んでしまったので修正しました。

最小の正の要素などを探す処理で、最大/最小のインデックスを正しく探すように修正。
二通りのどちらの選び方が大きいか比較する処理で、式変形して割り算しないように修正。
二通りのどちらの選び方が大きいか比較する処理で、変数名を正しく修正。

// う　し　た　ぷ　に　き　あ　く　ん　笑
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
constexpr int MOD = 1000000000 + 7;

struct mint {
    using ll = long long;
    ll mod = MOD;
    ll x;  // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.rbegin(), a.rend(), [](int a, int b) {
        if (abs(a) == abs(b))
            return a < b;
        else
            return abs(a) < abs(b);
    });

    int minuscount = 0;
    for (int i = 0; i < k; i++) {
        if (a[i] < 0) minuscount++;
    }

    if (minuscount % 2 == 0) {
        mint ans = 1;
        for (int i = 0; i < k; i++) {
            ans *= a[i];
        }
        cout << ans << endl;
        return 0;
    }

    // leftplus rightminus
    bool leftplus = false, rightminus = false;
-   int leftplus_i = 0, rightminus_i = 0;
+   int leftplus_i = -1, rightminus_i = -1;
    for (int i = 0; i < k; i++) {
        if (a[i] > 0) {
            leftplus = true;
-           leftplus_i = i;
-           break;
+           if (leftplus_i == -1 || a[i] < a[leftplus_i]) leftplus_i = i;
        }
    }
    for (int i = k; i < n; i++) {
        if (a[i] < 0) {
            rightminus = true;
-           rightminus_i = i;
-           break;
+           if (rightminus_i == -1 || a[i] < a[rightminus_i]) rightminus_i = i;
        }
    }

    mint lprm = 0;
    if (leftplus && rightminus) {
        lprm = 1;
        for (int i = 0; i < k; i++) {
            if (i != leftplus_i) lprm *= a[i];
        }
        lprm *= a[rightminus_i];
    }

    // leftminus rightplus
    bool leftminus = false, rightplus = false;
-   int leftminus_i = 0, rightplus_i = 0;
+   int leftminus_i = -1, rightplus_i = -1;
    for (int i = 0; i < k; i++) {
        if (a[i] < 0) {
            leftminus = true;
-           leftminus_i = i;
-           break;
+           if (leftminus_i == -1 || a[i] > a[leftminus_i]) leftminus_i = i;
        }
    }
    for (int i = k; i < n; i++) {
        if (a[i] > 0) {
            rightplus = true;
-           rightplus_i = i;
-           break;
+           if (rightplus_i == -1 || a[i] > a[rightplus_i]) rightplus_i = i;
        }
    }

    mint lmrp = 0;
    if (leftminus && rightplus) {
        lmrp = 1;
        for (int i = 0; i < k; i++) {
            if (i != leftminus_i) lmrp *= a[i];
        }
        lmrp *= a[rightplus_i];
    }

-   if ((leftplus && rightminus) || (leftminus && rightplus)) {
-       bool lprm_is_large = abs(a[rightminus_i] / a[leftplus_i]) >
-                            abs(a[rightminus_i] / a[leftminus_i]);

-       if (lprm_is_large || !(leftminus && rightplus)) {
+   if ((leftplus && rightminus) && !(leftminus && rightplus)) {
+       cout << lprm << endl;
+       return 0;
+   } else if (!(leftplus && rightminus) && (leftminus && rightplus)) {
+       cout << lmrp << endl;
+       return 0;
+   } else if ((leftplus && rightminus) && (leftminus && rightplus)) {
+       bool lprm_is_large = abs(a[rightminus_i] * a[leftminus_i]) >
+                            abs(a[rightplus_i] * a[leftplus_i]);

+       if (lprm_is_large) {
            cout << lprm << endl;
        } else {
            cout << lmrp << endl;
        }
        return 0;
    }

    mint ans = 1;
    for (int i = n - 1; i >= n - k; i--) {
        ans *= a[i];
    }
    cout << ans << endl;
    return 0;
}