ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

【AtCoder版!蟻本】ABC045 C - たくさんの数式【bit全探索】

f:id:ebisuke33:20210318222526p:plain
AtCoder版!蟻本のbit全探索で類題としてあげられているABC045 CをPythonで解いていきます。

atcoder.jp

AtCoder Beginner Contest 045 C - たくさんの数式

問題文

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

制約

・1≤|S|≤10
・S に含まれる文字は全て 1 〜 9 の数字

解答例

# bit全探索
s = input()

# 全ての数式の合計
ans = 0

# bit全探索
for i in range(2 ** (len(s)-1)):
    tmp = 0
    for j in range(len(s)):
        if (i >> j) & 1:  # bitが1なら+をいれる
            ans += tmp*10 + int(s[j]) 
            tmp = 0
        else:
            tmp = tmp*10 + int(s[j])
    ans += tmp

print(ans)

解説

bit全探索を用いて+が入る位置を決めていきました。

bitが1なら+を入れるという意味合いにしました。
tmpは+がはいるまでの値の記憶です。
tmpが1で次の桁が2とすると、tmp = 1 × 10 + 2となり、+を入れるまでの値を記憶していきます。
+が入るときはtmpと次の桁を、ans変数に足して、tmpをクリアします。

この繰り返しですべての数式の合計値が求まります。



AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com