【AtCoder版!蟻本】ABC045 C - たくさんの数式【bit全探索】
AtCoder版!蟻本のbit全探索で類題としてあげられているABC045 CをPythonで解いていきます。
リンク
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
リンク