巨大密室問題

https://tioj.ck.tp.edu.tw/problems/1619

Description

有長度 $n$ 的 $P_i$ 和 $O_i$ 兩個正整數序列，請任意排列這兩個序列使得 $\prod _ i (P_i + O_i)$ 盡量大。

$n\leq 20000, 1 \leq P_i, O_i \leq 1000$。保證答案至多是 $60000$ 位數。

Solution

既然兩個序列都可以動不妨令 $P_i$ 是從小排到大的。那麼可以 greedy 的猜說 $O_i$ 從大排到小會是最佳解，sort 完乘起來就是答案。

證明：
$$
(P_i + O_i) (P_j + O_j) - (P_i + O_j) (P_j + O_i)
= P_i O_j + P_j O_i - P_i O_i - P_j O_j
= (P_i - P_j) (O_j - O_i)
$$
如果沒有排好的話就必定存在 $i < j$ 使得 $O_i > O_j$，又 $P_i \leq P_j$，所以交換之後乘積不會變小。

然後接下來的問題是答案可能會很大，因為我很懶惰所以就用 python 直接過了。有一個優化可能是乘法不一定要照順序乘，可以用分治或是霍夫曼樹之類的方法讓大位數的乘法的次數減少。

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import sys

sys.set_int_max_str_digits(60025)

n = int(input())
# a = [1000 for _ in range(n)]
# b = [1000 for _ in range(n)]
a = sorted(map(int, input().split()))
b = reversed(sorted(map(int, input().split())))

p = [ai + bi for ai, bi in zip(a, b)]
prod = 1
for x in p:
    prod *= x
print(prod)

請注意 set_int_max_str_digits，不加上這行的話遇到極限測資會 RE。可以自己隨便在本地生大測資，跳出來的 RE 訊息就會提示你要用這個函式。