固定して全探索②

問題

$ 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