解説 | Integers and Operators

解説

$\mathrm{op}_1, \mathrm{op}_2, \cdots, \mathrm{op}_N$ に含まれる + の個数を $p$ とします。

整数の書かれたカードの出し方 $N!$ 通りと、演算子の書かれたカードの出し方 $\binom{N}{p}$ 通りを全探索することができます。

$N! \cdot \binom{N}{p}$ は $N \le 8$ の制約下だと高々 $2822400$ となるため、適切な手続きで全列挙を行うことで十分実行時間に間に合います。

順列全列挙・組合せ全列挙のライブラリがあればそちらを使うのが簡潔です。（Python3 では itertools.permutations, itertools.combinations が利用できます。）また、適切に枝刈りをすることで、組合せ全列挙の代わりに bit 全探索で実装しても計算量は悪化しません。
なお、 DFS を用いて全列挙をしても正解することができます。

実装例（Python3）

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
30from itertools import combinations, permutations

INF = 10**18

N = int(input())
A = [int(s) for s in input().split()]
ops = input().split()

plus_count = ops.count("+")
max_x, min_x = 0, INF

for perm in permutations(A):
    for comb in combinations(range(N), plus_count):
        comb_ops = ["^"] * N
        for c in comb:
            comb_ops[c] = "+"

        x = 0

        for a, op in zip(perm, comb_ops):
            if op == "+":
                x += a
            else:
                x ^= a

        max_x = max(max_x, x)
        min_x = min(min_x, x)

print(max_x, min_x)

難易度評価

外部サイトへ移動します

Integers and Operators

解説

実装例（Python3）

ユーザー解説