Yukicoder No.297 カードの数式
やるだけなのだけど、少し手間。
solution
やる。sortが入るので$O(N \log N)$。
implementation
- 演算子の数をそれぞれ数え、数値に関しては整列して保持する。
+
演算子の量に$1$を足しておくことで、演算子の量と同じ量の数を作って割り当てる問題となる。+
と-
の量を入れ換え結果に$-1$を掛けることで、最大化/最小化の一方からもう一方を作ることができる。- 最大化に際して、
+
の演算子が使えるかどうかで場合分け+
があるとき、大きなひとつの整数を作る。小さい数字から-
に当てていき、+
に関しても単一の+
になるまで同様にし、残りをまとめてひとつの整数にする。+
がないとき、均等に割り振る。-
が$n$個あるとき、$1$の位になれるのは$n$個、$10$の位になれるのも$n$個、のように枠がある。大きい数字から順に、下位の桁を埋めていく。
#!/usr/bin/env python3
_ = int(input())
nums = []
plus = 1
minus = 0
for c in input().split():
if c == '+':
plus += 1
elif c == '-':
minus += 1
else:
nums.append(int(c))
def ev(nums, plus, minus):
nums = sorted(nums)
acc = 0
if plus:
for i in range(minus):
acc -= nums[0]
nums = nums[1:]
for i in range(plus - 1):
acc += nums[0]
nums = nums[1:]
acc += int(''.join(map(str,reversed(nums))))
else:
e = 1
while nums:
for i in range(minus):
if not nums:
break
acc -= nums[-1] * e
nums = nums[:-1]
e *= 10
return acc
print(ev(nums, plus, minus), - ev(nums, minus, plus))