AtCoder精選良問「D - Flipping Signs」Diff 833

この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。

https://note.com/kuri_tter/m/m622eeb3d9ca2

問題リンク

D - Flipping Signs

問題概要

整数列 A1, A2, ..., AN が与えられ、以下の操作を好きなだけ行うことができる

操作: 1≤i≤N-1 を満たす整数 i を選ぶ。Ai と Ai+1 に -1 を乗算する。Aの取りうる範囲は、-10^9 ≤ Ai ≤ 10^9。

操作終了後の整数列を B1, B2, ..., BN としたとき、B1 + B2 + ... + BN の最大値を求める、という問題。

考え方

要するに配列Aの正負をなんやかんやで変えて、その時の総和の最大値を求めよ、という問題。

競プロをやっていると、「直感的にそうと思ったことが正しかった」というタイプの問題に出くわすことがある。そのような問題に対して「エスパー」を働かせるというように言うこともある。

この問題もいわゆる「エスパー」問題。結論から言うと、全部の数字を正にできるか、負の数を１個だけにできるかの２択しかない、ということになる。すこし思考の流れを追ってみよう。

「エスパー」をするには入力例から直感的に閃かせる。
まず、入力例１を見てみる。

3
-10 5 -4

偶奇を変えていくと全てプラスにできる

10 -5 -4
10 5 4

なので答えは19となる。

入力例２はどうだろうか。出力例は30なので、10+4+8+11-3とすると30になる。3だけマイナスになっている気がする。そういう操作ができるか試してみる。

5
10 -4 -8 -11 3

10 4 8 -11 3
10 4 8 11 -3

できた。

このあたりまで来て「エスパー」が働きはじめる。
つまり、「全部プラスにできるか、１個だけマイナスになるんじゃない？」というような仮説だ。
ではその違いはどこにあるかと言うと、負の数が偶数個あるか奇数個あるか、ということ。
例えばN=5の場合で考えてみる。

1 -1 1 -1 1

こういう場合でも全て正にできる。

1 1 -1 -1 1
1 1 1 1 1

じゃあ-1が３個あった場合はどうか。この場合は-1を0個にすることはできない。

-1 1 -1 1 -1

こういう場合には…

1 -1 -1 1 -1
1 1 1 -1 1

このように、どうやっても-1が一つだけ余ってしまう。

この時点でほぼ確信的に「エスパー」が正しいと思えるが、一応解説記事なので、もう少し突っ込んでみる。

操作対象となる二つの数字の正負のパターンと操作後の正負のパターンを考える。

正正 => 負負
正負 => 負正
負正 => 正負
負負 => 正正

負の数字の増減個数に着目したときに-2か0か+2だ。
つまり、負の数の偶奇はどう操作しても変わらない。

また、どんな数字が与えられても、貪欲に負負の組み合わせを作っていけば正の数をできるだけ増やせる。

そのため、負の数が奇数個あるときは負の数を１個だけにするのが、最適。負の数が偶数個だったら全て正にできる。

以上からこの問題を以下のように言い換えられる。

• 負の数字の数が奇数個の時は絶対数が一番小さいものを負にする

• 負の数字の数が偶数個の時は、全て正にできる

• 総和を計算して答えを出力する。

実装

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";


function main() {
    const n = nextNum()
    const arrA = nextNums(n)
    // 負の数字の数
    let cnt = 0
    // 絶対値が一番小さい数
    let mi = 10 ** 10
    // 答え
    let ans = 0n
    for (const num of arrA) {
        mi = Math.min(Math.abs(num), mi)
        if (num < 0) cnt++
        // とりあえず絶対値をぜんぶ足しておく
        ans += BigInt(Math.abs(num))
    }
    if (cnt % 2 == 0) {
        // 偶数個なのでそのまま答えを出力
        log(String(ans))
    } else {
        // 奇数個なので、一番ちいさい数字をマイナスにする
        // 上で一回足してしまっているので、ｘ２でマイナスする
        ans -= BigInt(mi) * 2n
        log(String(ans))
    }
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}


// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}