水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.297 カードの数式

回答

#58090 No.297 カードの数式 - yukicoder


結構,めんどくさい感じになってしまった(コード長め)



まず,最大値について考える.
(作れる限りで一番大きな数字) + (一桁で大きい物) - (一桁で小さいもの)
で求められる.
作れる限りで一番大きな数字は,数字の数 - "+"の数 - "-"の数(桁)となる.

4
1 2 3 + 
-> 32

5
1 2 3 + -
-> 3

という感じに考えると良い?
だから,まずはそれを作る.文字列を連結してから数値に変換したほうが良いと考え,基本的に文字列で処理.
そしてこれができたら,とりあえず最大値の答えの変数に足しておく.
残った数字のうち,大きい物を足す,小さいものを引く,という手順で最大値が求まる.



小さい時の処理が厄介.
"-"が一つでも入っていれば,最大値を求める手順の逆でも止まる.
この場合,(一桁で小さいもの)- (一桁で大きい物) - (作れる限りで一番大きな数字)
で求まる
"-"がない場合は,ここでまた計算処理が必要.
足し算で使う要素数は,"+"の数+1で求まるので,この数になるようにひたすら分割.手順としてはこんな感じになる.

9 8 6 6 4 2 1
-> ["1", "", ""]
-> ["1", "2", ""]
-> ["1", "2", "4"]
-> ["16", "2", "4"]
-> ["16", "26", "4"]
-> ["16", "26", "48"]
-> ["169", "26", "48"]

こんな形で求めておいて,最後に整数に変換して計算,という手順が楽そうです….

そして求まったものを出力.
変数を長めにつけていることを考えたとしても,少し処理手順が煩雑で厳しい問題でした.
(コンテスト中は計算手順がよくわからなかったうえ,スマホコーディングなので,投げてしまいました)

numstrs = []
pluscount = 0
minuscount = 0

N = int(input())
for c in input().split():
    if c == "+":
        pluscount += 1
    elif c == "-":
        minuscount += 1
    else:
        numstrs.append(c)

numstrs.sort(reverse=True) # 大きい順位に並び替え
bignum = ""
bigres = 0
numcount = len(numstrs)
# 大きい数字をつくる
for i in range(numcount - pluscount - minuscount):
    bignum += numstrs[i]
bigres += int(bignum)
# 残った数字で大きい物を足す
for i in range(numcount - pluscount - minuscount, numcount - minuscount):
    bigres += int(numstrs[i])
# 残りを引く
for i in range(numcount - minuscount, numcount):
    bigres -= int(numstrs[i])

minres = 0
if minuscount >= 1:
    # 最小値を求める
    # 小さいものを足す
    for i in range(numcount - pluscount - 1, numcount):
        minres += int(numstrs[i])
    # 余ったものを引く
    for i in range(len(bignum), numcount - pluscount - 1):
        minres -= int(numstrs[i])
    # さっき作った大きい数字を引く
    minres -= int(bignum)
else:
    # とにかく分散させて,最小値を求める
    # 足すしかない場合は,長さ"+"の数+1の配列を作る
    li = ["" for i in range(pluscount + 1)]
    # 前から順番に,配列へ割り振り
    for i in range(numcount - 1, -1, -1):
        li[i % (pluscount + 1)] += numstrs[i]
    # 足し合わせる
    minres = sum([int(i) for i in li])

print(bigres, minres)