名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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)