yukicoder 1374 Absolute Game

絶対値なので符号が関係してくる. ここでA君がどちらの符号に合わせるかを決めたとする. すると同符号の要素はできるだけ大きい要素から取っていくのが最適で, 異符号の要素についても同様になる. このときB君も同様の戦略をとるのが最適となる. 以上より単に数列をソートして, A君が左・右どちらから取るのかを両方試していけば答えを求めることができる. 計算量は$ O(N \log N)となる.

実装例: https://yukicoder.me/submissions/613651