固定して全探索②

問題

$ N $ 枚のカードがあり、$ i $ 枚目のカードの表には整数 $ A_i $、裏には整数 $ B_i $ が書かれています。

カードを何枚か選び、次のように定義するスコアを最大にしたいです。

[スコア] = [選んだカードにおける表の総和の絶対値] + [選んだカードにおける裏の総和の絶対値]

スコアとして考えられる最大値はいくつになるでしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ -10^9 \leqq A_i \leqq 10^9 $
🔹$ -10^9 \leqq B_i \leqq 10^9 $

解き方・ソースコード

この問題では「表の総和を正/負のどちらにするか」「裏の総和を正/負のどちらにするか」を全探索することで解くことができます。

計算量は $ O(4N) $ となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import random
#--------- 入力例 ----------
N = 5 # カードの枚数
A = [random.randint(-20, 20) for i in range(N)]
B = [random.randint(-20, 20) for i in range(N)]
#---------------------------
print('【入力データの確認】')
print('A', A)
print('B', B)
print()

# omote=True のとき表の総和が正、ura=True のとき裏の総和が正
# omote=False のとき表の総和が負、ura=False のとき裏の総和が負
def solve(omote, ura, A, B):
sum = 0
for i in range(N):
card1 = A[i] if omote else -A[i]
card2 = B[i] if ura else -B[i]
# カード i は選ぶべきかどうか?
if card1 + card2 >= 0:
sum += (card1 + card2)
print('選択したカード:', card1, card2)
print(' 合計:', sum)
print('---------------------')
return sum

# 表の総和の正負と、裏の総和の正負を全探索
Answer1 = solve(True, True, A, B);
Answer2 = solve(True, False, A, B);
Answer3 = solve(False, True, A, B);
Answer4 = solve(True, True, A, B);

# 出力
print('【解】', max(Answer1, Answer2, Answer3, Answer4))

[実行結果]

【入力データの確認】
A [7, -16, 10, -13, 12]

B [18, -13, -14, 4, 18]


選択したカード: 7 18

選択したカード: 12 18

 合計: 55
---------------------

選択したカード: 10 14

 合計: 24
---------------------

選択したカード: -7 18

選択したカード: 16 -13

選択したカード: 13 4

選択したカード: -12 18

 合計: 37
---------------------

選択したカード: 7 18

選択したカード: 12 18

 合計: 55
---------------------

【解】 55