D - Decrease 2 max elements 解説 by MMNMM

より高速な解法

考察を進めることで、より大きな制約でも高速に解ける解法を導くことができます。

まず、\(\displaystyle\sum _ {i=1} ^ NA _ i\) が操作のたびに \(2\) だけ減少するので、答えは \(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\) 以下です。

次に、\(\displaystyle\max _ {1\leq i\leq N}A _ i\) が操作のたびにたかだか \(1\) だけ減少するので、\(\displaystyle\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) は \(1\) 回の操作で \(1\) もしくは \(2\) 減少し、答えは \(\displaystyle\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) 以下です。

以上より、答えは \(\displaystyle\min\Biggl\lbrace\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor,\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\Biggr\rbrace\) 以下です。 実は、この上界が達成されることを示せます。

証明

\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\) と \(\displaystyle\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) の大小関係について場合分けを行います。

\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\gt\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) のとき

このとき、\(A _ i\) が最大になる \(i\) がただひとつ存在します。これが \(1\) として一般性を失いません。このような \(A\) からはじめたとき、操作は常に \(A _ 1\) と \(A _ i\ (i\neq1)\) に対して行われ、操作回数は \(\displaystyle\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) 回です。

\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\leq\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) のとき

まず、\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\leq\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) が成り立っている状態から（操作ができるなら）操作を行っても \(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\leq\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) が成り立つことを示します。

\(\displaystyle A _ 1=\max _ {1\leq i\leq N}A _ i\) として一般性を失わないため、そうします。

  1. \(A _ 1=A _ i\) なる \(1\lt i\leq N\) がたかだか \(1\) つのとき、操作の前後で \(\displaystyle\max _ {1\leq i\leq N}A _ i\) は \(1\) 減少しています。よって、\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor,\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) のどちらも \(1\) だけ減少しているため、大小関係は変化しません。
  2. \(A _ 1=A _ i\) なる \(1\lt i\leq N\) が \(2\) つ以上存在するとき、\(\displaystyle\sum _ {i=1} ^ NA _ i\geq3A _ 1\) なので、\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\lt\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) が成り立ちます。操作の前後で \(\displaystyle\max _ {1\leq i\leq N}A _ i\) は変化しないため、\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\) は \(1\) 、\(\displaystyle\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) は \(2\) だけ減少し、\(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\leq\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\) が成り立ちます。

よって、操作のたびに \(\min\Biggl\lbrace\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor,\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\Biggr\rbrace=\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\) は \(1\) ずつ減少し、操作回数は \(\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor\) 回です。

あとは、これを実装することで \(N\leq10 ^ 6,A _ i\leq10 ^ {18}\) のような制約でも十分高速に問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    int sum_A = 0, max_A = 0;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        // A の合計と A の最大値を更新
        sum_A += A;
        max_A = max(A, max_A);
    }
    // 答えは min(合計 / 2, 合計 - 最大値)
    cout << min(sum_A / 2, sum_A - max_A) << endl;
    return 0;
}

投稿日時:
最終更新: