きろく

特筆すべき記録のまとめ

diverta 2019 Programming Contest 2:C - Successive Subtraction

問題

atcoder.jp

解法

A の各要素の正負を反転させることを考える.全ての要素の正負を反転させたり,1 つも反転させないことは不可能.なぜならば,1 回以上の操作によって選ばれた 2 つの要素は x - y という形になり,最低 1 つは反転させる・させない要素が出てきてしまうから.A の要素のうち,負のものは符号を反転させ,正のものは反転させないのがよいが,全て負・正のときどれか 1 つは「不利になる」反転をさせなければいけない.

以上のことより M は簡単に求まるが,操作の過程も考えなければいけない.A を昇順にソートしておき,A[k] < 0 かつ A[k + 1] >= 0 となるような k を前処理で探しておく.全ての要素の正負が一緒の場合は,k = 1 や k = N - 1 とする必要がある.まず,k 番目と k + 2 ~ N 番目を選び,操作を行う.これによって A[k] は

A[k] - (A[k + 2] + A[k + 3] + ... + A[N])

となる.その後,k + 1 番目と 1 ~ k 番目を選び,操作を行う.これによって A[k + 1] は

A[k + 1] - (A[1] + A[2] + ... + A[k])

となる.この結果 M は

M = A[k + 1] - (A[1] + A[2] + ... + A[k] - (A[k + 2] + A[k + 3] + ... + A[N]))

    = -(A[1] + A[2] + ... + A[k]) + (A[k + 1] + A[k + 2] + ... + A[N])

となり,最適な正負の反転ができている.O(N).

解答

atcoder.jp

f:id:babcs2035:20190616124024p:plain