torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces 160, Division 2, B : Roma and Changing Signs

概要

n 項からなる単調非減少な数列が与えられる。
この数列の任意の項をちょうど k 回符号反転し、和を最大化したい。
得られる和の最大値を求めよ。

解法

まず、より小さい負数から順に符号を反転させます。
全ての負数を反転しても k が余る場合、残りの k が偶数であれば同一の数字を偶数回反転することで k を消費できます。
また、奇数の場合でも数列に 0 が存在すれば、k を消費することができます。
残りの k が奇数で、且つ 0 が無い場合は、最も小さい項の符号を反転することで k を消費します。

コード

import Control.Applicative
import Control.Monad
import Data.List

main = do
	[ n, k ] <- map read . words <$> getLine
	as <- map read . words <$> getLine
	let
		negas = min ( length ( filter ( < 0 ) as ) ) k
		rest = ( k - negas ) `mod` 2
		tmp = sort . change negas $ as
		res = if 0 `elem` tmp then sum tmp else sum $ change rest tmp
	print res

change :: Int -> [Int] -> [Int]
change _ [] = []
change 0 as = as
change n (a:as) = a * ( -1 ) : change ( n - 1 ) as