アルゴリズム学習—白駿1541号:失われた括弧

もんだいぶんせき

ポテンシャル俊は正数,+,−,カッコで式を行い,その式の値を最小にすることを目的とする.
1.55-50+40の場合

マイナスするとスキップして後ろの数字を最大にして

と計算します

1)50+40計算2)55-90

を行う.
2.10+20+30+40の場合

なら負の値は出ていないので加算します.

3000009-00009時

0前に数字がなくて、1)数字がなくて、2)+、-後ろがちょうど0なら0を捨てます.

新しいエンクロージャ10-20+30-40の場合

1)10入力2)-スキップ3)新しい-

を加える

10-50以降、新しい演算子なしで数字をスキップ-受け入れた場合、既存の結果は-40処理

を行う.

アルゴリズムコード

1）最初に実施形態で得られたコード

calculate = list(input())

answer = []
num = ""

while len(calculate) > 0:
    word = calculate.pop(0)
    if word == "+":
        answer.append(int(num))
        num = ""
    elif word == "-":
        answer.append(int(num))
        num = ""
        answer.append("-")
    else:
        num += word

answer.append(int(num))
ans = answer[0]
minus = False

if '-' not in answer:
    print(sum(answer))
else:
    for i in answer[1:]:
        if i == "-":
            minus = True
            continue

        if minus:
            ans -= i
        else:
            ans += i
    
    print(ans)

2)他者のコードによる報告

a = input().split('-')
num = []
for i in a:
    cnt = 0
    s = i.split('+')
    for j in s:
        cnt += int(j)
    num.append(cnt)
n = num[0]
for i in range(1, len(num)):
    n -= num[i]
print(n)

メモリと時間はそれぞれ30864 KBと68 msである.
1.1つ目の方法は+-残したときだけ
2.2つ目の方法は-を抜き、+を基準にマークしてから問題を解くことです.
2つ目の方法はO(N^2)で、もっと時間がかかるかもしれませんが、同じ時間なのでよく見ると、儀式の長さが50以下なのかもしれません.