パリティ②

パリティ

操作に関する問題は、決まったパターンを持たず 柔軟な思考 を必要とするものが多くあります。

しかしながら、次のように問題を解くための指針となる考え方があります。

  • 操作をわかりやすく言い換える。
  • 操作によって作れるものを特徴付ける。

[問題]

Ｎ個の整数が一列に並んでいます。

この整数列に対して次の操作を好きなだけ行うことができます。

「隣り合う２つの整数を選んで、両方の整数に－1を掛ける」

操作終了後のＮ個の整数の 総和 として考えられる最大値を求めて下さい。

解法・ソースコード

今回の操作を分類すると、次のいずれかになります。

  • 数列の「プラス」「プラス」が連続している箇所を「マイナス」「マイナス」にする。
  • 数列の「プラス」「マイナス」が連続している箇所を「マイナス」「プラス」にする。
  • 数列の「マイナス」「プラス」が連続している箇所を「プラス」「マイナス」にする。
  • 数列の「マイナス」「マイナス」が連続している箇所を「プラス」「プラス」にする。

上記により「マイナス」の個数は「２つ増える」か「変わらない」か「２つ減る」 かのいずれかであることが分かります。

つまり「マイナス」の個数の パリティ（偶数／奇数） は 操作の前後で不変 です。

実装は次のように行います。

  • 数列の中のマイナスの数値が 偶数個 ある場合
    マイナスの数値を全てなくして（絶対値をとって）、総和を算出する。
  • 数列の中のマイナスの数値が 奇数個 ある場合
    マイナスの数値を全てなくして（絶対値をとって）、総和を算出する。
    その総和から、絶対値が最小 である数値を ２回差し引く。
    （総和にはすでに最小の数値が含まれているため ２回差し引く 必要があります。）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#---------- 入力例 1 ---------
lst = [-10, 5, -4]
#---------- 入力例 2 ---------
# lst = [1, 2, -3, 10, 100]
#-----------------------------
# マイナスの個数
cnt_minus = sum(x < 0 for x in lst)

# Ｎ個の整数の絶対値の総和
total = sum(map(abs, lst))
# Ｎ個の整数の絶対値の最小値
abs_minus = min(map(abs, lst))

# マイナスの個数が[偶数の場合]は、[絶対値の総和]を出力。
# マイナスの個数が[奇数の場合]は、[絶対値の総和] － [絶対値の最小値×２]を出力。
print(total if abs_minus % 2 == 0 else total - abs_minus * 2)

[実行結果 (入力例 1)]

19

マイナスの数値の個数が 偶数 なので、すべての整数の 絶対値の総和 が解となります。

[実行結果 (入力例 2)]

114

マイナスの数値の個数が 奇数 なので、すべての整数の 絶対値の総和 から 絶対値の最小値×２ を引いた値が解となります。