Mister雑記

競プロやります。

Diverta 2019 2 - C「Successive Subtraction」 (500)

atcoder.jp

問題

長さ Nの整数列 Aに対して、以下の操作を長さが1になるまで繰り返す。

  •  A_i, A_jを消し、末尾に A_i - A_jを追加する。

最終的に残る値の最大値を求め、それを実現する操作列を1つ構成せよ。

制約

  •  2 \leq N \leq 10^5
  •  |A_i| \leq 10^4

考察

まず Nが小さいケースで考えてみる。  N = 3, A = \{ 1, 3, 6 \}のとき、  1 - 3 = -2, 6 - (-2) = 8で最大値 8が得られる。

これを展開してみると 6 - (1 - 3) = -1 + 3 + 6となり、 最小値はマイナスで他全部プラスのやつが作れることに気づく。 実際、 A_N - ( \cdots ((A_1 - A_2) - A_3) \cdots - A_{N - 1} ) =
-A_1 + A_2 + \cdots + A_Nで構成できることが分かる。

 A_1 + \cdots + A_Nはどう考えても作れないから、これが最大! ということで提出したらWA。 これは負の数が含まれる場合は A_1 + \cdots + A_Nが最善ではないためである (なぜこの段階で提出してしまったのか自分でも分からない)。

 Aをソートしたとき、 A_m \lt 0かつ A_{m + 1} \geq 0だったとする。 このとき上のを少し変更して  A_N - (A_1 - A_{m + 1} - \cdots - A_{N - 1}) -
A_2 - \cdots - A_mとすれば、  - A_1 - \cdots - A_m + A_{m + 1} + \cdots + A_N となって最大値が得られる。 また Aが全て正、及び全て負のケースでも これで最大値が得られることが場合分けで分かる。

実装例

atcoder.jp

int main() {
    /* ----- 入力 ----- */
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& a : A) cin >> a;
    sort(A.begin(), A.end());

    /* ----- 最大値を求める ----- */
    int sum = 0;
    for (auto& a : A) sum += abs(a);
    if (A.front() > 0) sum -= A.front() * 2;  // 全て正の場合
    if (A.back() < 0) sum += A.back() * 2;    // 全て負の場合
    cout << sum << endl;

    /* ----- 操作列の構成 ----- */
    int acc = A.front();

    // 正の要素を引く
    for (int i = 1; i < N - 1; ++i) {
        if (A[i] >= 0) {
            cout << acc << " " << A[i] << endl;
            acc -= A[i];
        }
    }

    // 正負逆転
    cout << A.back() << " " << acc << endl;
    acc = A.back() - acc;

    // 負の要素を引く
    for (int i = 1; i < N - 1; ++i) {
        if (A[i] < 0) {
            cout << acc << " " << A[i] << endl;
            acc -= A[i];
        }
    }
    return 0;
}

反省

  • いや注意力が低いなんてもんじゃない。
  • 具体例なしでパッと構成法が浮かぶようになるもんなのかね。