ABC63 C - Bugged を解いた

ビット探索が頭をよぎったけど、2^100 って無理だな。
OK
じゃあ,if で行こう。

Bugged.py

N = int(input())
S0 = [] #10の倍数
S1 = [] #not 10 の倍数
for _ in range(N):
    s = int(input())
    if s%10 == 0:
        S0.append(s)
    else:
        S1.append(s)

S1.sort()
Total = sum(S0)+sum(S1)

if Total%10 != 0:             #全部足した状態で not 10 の倍数なら答え
    print(Total)
else:
    for i in range(len(S1)):  #not10倍数だけのリスト S1 から小さい順に引いていく
        Total -=S1[i]
        if Total%10 != 0:     #TotalSum%10 != 0 なら最大値
            print(Total)
            break
    else:
        print(0)#26ms

気を付けたのは入力 S。
求めたいのは合計の最大値。
よって、引いていきたいのは not 10 の倍数を一個ずつ引いて試したい。
だから入力時に s1,s2... はデータを受け取る時点で分別した。

例えば、 10,15,25 って入力の場合、小さい順で引いていくと最大値は 25 になる。
でもそれって、15 だけ引けば、最大値は 35 になるよね？的なイメージ。

---

ちょっとだけ早くなりました。

abc63c.py

N = int(input())
S = [int(input()) for _ in range(N)]

if sum(S)%10 != 0:
    print(sum(S))
else:
    S.sort()
    X = sum(S)
    for i in range(N):
        if S[i]%10 != 0:
            X -= S[i]
            if X%10 != 0:
                print(X)
                exit()
    print(0)#24ms