コンテンツにスキップ

ShareOJ Programming Contest vol.1 D - Integers and Operators

サイト
ShareOJ
コンテスト
ShareOJ Programming Contest vol.1
問題
D - Integers and Operators(常設版)

整数のカード A1,…,ANA_1, \dots, A_N と、+ か ^(XOR)が書かれた演算子のカード NN 枚があります。x=0x = 0 から始めて、整数と演算子のカードを 1 枚ずつ選んで xx を更新することを NN 回繰り返します。最後の xx としてありうる最大値と最小値を求める問題です。N≤8N \le 8 です。

N≤8N \le 8 と小さいので、カードの使い方をすべて試します。

ii 回目に使う整数のカードと演算子のカードを決めれば、手続きが 1 通りに決まります。つまり、整数のカードの並べ方と演算子のカードの並べ方の組をすべて試せばよいです。

ただし、そのままでは 8!×8!≈1.6×1098! \times 8! \approx 1.6 \times 10^9 通りになり、間に合いません。演算子のカードには + と ^ の 2 種類しかないので、並べ方を記号の列として見ると重複がたくさんあります。重複を除くと、+ が cc 枚なら (Nc)≤(84)=70\binom{N}{c} \le \binom{8}{4} = 70 通りです。全体では 8!×70≈2.8×1068! \times 70 \approx 2.8 \times 10^6 通りになり、1 通りあたり NN 回の計算で済みます。

Python
from itertools import permutations
N = int(input())
A = list(map(int, input().split()))
op = input().split()
l = []
for p in permutations(op):
l.append(p)
l = list(set(l))
ans0 = 10**18
ans1 = -(10**18)
for t in l:
for p in permutations(A):
x = 0
for i, c in zip(t, p):
if i == "+":
x += c
else:
x ^= c
ans0 = min(ans0, x)
ans1 = max(ans1, x)
print(ans1, ans0)

演算子の並べ方を set に入れて重複を除き、l にしています。ans1 が最大値、ans0 が最小値です。