AtCoder Regular Contest 092 E - Both Sides Merger - アルゴリズマーの備忘録

「3月中に毎日1問解いて黄色になろう！」キャンペーン7問目。3日に1問ペースすら崩れてると思いきや、残念ながら2問連続投稿でペース通りです。

問題概要

以下の操作を与えられた配列に残り要素が1つになるまで行う。最大値とそれを得る方法を求めよ。

配列の要素を1つ選ぶ
選んだ要素が配列の端なら削除
そうでなければその両隣の要素の和にその要素を書き換え、両隣を削除

解説

実験していると、割とすぐに「偶奇で分けて、その中では任意に選ぶことが出来る」ということが分かります。具体的には、

A=[1,3,5,2,4]

としたときに、1と4を組み合わせるなら3番目で[1,5,4]にする→[5(1+4)]にするという感じで、奇数個離れていれば自由に組み合わせられます。逆に、偶数個離れているときはどう頑張っても無理です。というのも、3の操作で間の間隔が2減るので。

「偶奇で分けた後、"""自由に"""組み合わせることが出来る」ので、偶奇別にmax(0,a[i])の総和が大きいほうを採用します。作り方も答えないといけなくて、これは右端から消していく感じで頑張って実装すると出来ます。O(N)で制約が非常に緩いので、まあ出来るかと。偶数の時は最初にa[0]を削除すると奇数のパターンに容易に帰着できます。

ここで気を付けなくてはいけないのが、「全部負の数」のパターン。max(0,a[i])で全部ダメになるので、これだけ例外処理をしなくてはなりません。この時は足し算すると損をするので、1要素以外すべて2の方法で消します。これは割と簡単に実装できるのではないかと。右から消していくと、要素を過ぎた後が2ではなく3の処理になってしまうので、「1」を連発するか、左から消すことをお勧めします。

https://beta.atcoder.jp/contests/arc092/submissions/2240774

int main() {
    int n; cin >> n;
    vll a(n);
    rep(i, n)   cin >> a[i];
    bool minus = true;
    rep(i, n)   if (a[i] > 0LL)   minus = false;
    if (minus) {
        // 一番大きい要素以外全削除
        int x = 0;
        rep(i, n)   if (a[x] < a[i])   x = i;
        cout << a[x] << endl;
        cout << n - 1 << endl;
        for (int i = n; i > x + 1; i--)  cout << i << endl;
        for (int i = x; i > 0; i--)  cout << 1 << endl;
        return 0;
    }
    ll ret1 = 0, ret2 = 0;
    for (int i = 0; i < n; i += 2)  ret1 += max(0LL, a[i]);
    for (int i = 1; i < n; i += 2)  ret2 += max(0LL, a[i]);
    vint ret;
    if (ret1 < ret2) {
        ret1 = ret2;
        ret.push_back(1);
        n--;
        a.erase(a.begin());
    }
    if (n % 2 == 0) {
        ret.push_back(n);
        n--;
    }
    while (a[n - 1] <= 0) {
        ret.push_back(n);
        n--;
        ret.push_back(n);
        n--;
    }
    while (n > 1) {
        while (n >= 5 && a[n - 3] <= 0) {
            ret.push_back(n - 2);
            n -= 2;
        }
        if (n == 1)  break;
        else if (n == 3) {
            if (a[0] >= 0) {
                ret.push_back(2);
                n = 1;
                break;
            }
            else {
                ret.push_back(1);
                ret.push_back(1);
                n = 1;
                break;
            }
        }
        else {
            ret.push_back(n - 1);
            n -= 2;
        }
    }
    cout << ret1 << endl;
    cout << ret.size() << endl;
    rep(i, ret.size())  cout << ret[i] << endl;
    return 0;
}

感想

Dより簡単なのは思考できたからなんでしょうね…思いつかなきゃ思いつかないです。精進しましょう。