ABC045 C – たくさんの数式

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC045 C – たくさんの数式、を解きました。

1 以上 9 以下の数字のみからなる文字列 S が与えられます。
この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。
一つも入れなくてもかまいません。 ただし、+ が連続してはいけません。
このようにして出来る全ての文字列を数式とみなし、和を計算することができます。
ありうる全ての数式の値を計算し、その合計を出力してください。

難易度は緑色。

考察

制約が 10 以下なので、全探索を使えそうです。

ここで、+ が入りうるのは、「各数列の隙間」であるので、len(S)-1個のスペースに、+を入れる場合と入れない場合についてbit全探索で求めました。

コード

S = input()

def bruteforce_bin():
    P = pow(2, len(S)-1)
    ans = 0
    sum = 0
    for bit in range(P):
        f = []
        for i in range(len(S)-1):
            if bit & (1 << i):
                # 部分集合にA[i] が含まれる時の挙動
                f.append(True)
            else:
                f.append(False)

        num = S[0]
        for i in range(len(S)-1):
            if f[i]:
                ans += int(num)
                num = S[i+1]
            else:
                num += S[i+1]

        if num != "":
            ans += int(num)

    return ans

print(bruteforce_bin())

まとめ

Diffは緑上位でしたが、恐らく今のABCで出ると茶色下位くらいのDiffになりそうです。

bit全探索の部分と和の計算を同時にやってもよさそうでしたが、なぜか実装が上手くいかず分離したので少し冗長になりました。