ShareOJ Programming Contest vol.1 D - Integers and Operators
- サイト
- ShareOJ
- コンテスト
- ShareOJ Programming Contest vol.1
- 問題
- D - Integers and Operators(常設版)
整数のカード と、+ か ^(XOR)が書かれた演算子のカード 枚があります。 から始めて、整数と演算子のカードを 1 枚ずつ選んで を更新することを 回繰り返します。最後の としてありうる最大値と最小値を求める問題です。 です。
と小さいので、カードの使い方をすべて試します。
回目に使う整数のカードと演算子のカードを決めれば、手続きが 1 通りに決まります。つまり、整数のカードの並べ方と演算子のカードの並べ方の組をすべて試せばよいです。
ただし、そのままでは 通りになり、間に合いません。演算子のカードには + と ^ の 2 種類しかないので、並べ方を記号の列として見ると重複がたくさんあります。重複を除くと、+ が 枚なら 通りです。全体では 通りになり、1 通りあたり 回の計算で済みます。
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**18ans1 = -(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 が最小値です。