【bit全探索】ARC061 C - たくさんの数式 / Many FormulasをPythonで解いてみた

今日も昨日に引き続きbit全探索を解いていきます。

練習したいですしね。
ささっと解けるようになりたい。

思考の過程

選択肢のそれぞれにある二択の可能性をチェックする問題。
これこそbit全探索ですね。

昨日の問題と異なるのは、空白も選択肢の一つということですね。
ちなみに昨日の問題とはこれです。

さて、空白も選択肢ということで、最初に用意しておくリストのすべての要素は空の文字列にしましょう。
そして、bit全探索を用いて2進数表示で1の箇所を "+" で上書きしていく、ということにします。

問題は足していく過程です。
単純に空白を数字と数字の間に入れるだけでは、2桁の数字になりません。
そこで、少し工夫をしてみました。
2桁の数字、例えば12というのは、10+2で計算されますよね。
それを利用して、リストの要素が空白だったら、その数字に10を掛けてキープしておくことにします。
そして、リストの要素が+だったとき、キープしたやつと+の手前の数字を同時に足していきます。
…多分文面じゃ何を言っているかわからないと思うので、以下のコードを見てください。

コード実装

プログラムの流れは以下のようにする。
1. スキマの数を計算
2. + or 空白の組み合わせの数だけ、for文でbit全探索
3. 2進数表示で1の箇所を "+" で上書き
4. 更新したリストを用いて方程式作成
5. リストの要素が空白なら、その数字に10を掛けてをキープ
6. リストの要素が+なら、その数字とキープしたものを足していく
7. もし標準入力が1桁なら、そもそもスキマがないので、入力された数字をそのまま出力

s = input()
n = len(s) - 1  # スキマの数を計算
sum_ = 0
keep = 0
for i in range(2**n):  # + or 空白の組み合わせの数だけ、for文でbit全探索
    p_or_no = [""] * n
    for j in range(n):
        if ((i >> j) & 1) == 1:  # 2進数表示で1の箇所を "+" で上書き
            p_or_no[n-1-j] = "+"

    for k in range(n):  # 更新したリストを用いて方程式作成
        if p_or_no[k] == "+":  # リストの要素が+なら、その数字とキープしたものを足していく
            sum_ += int(s[k]) + keep
            keep = 0
        else:  # リストの要素が空白なら、その数字に10を掛けてをキープ
            keep = int(s[k]) * 10 + keep * 10
        if k == n-1:
            sum_ += int(s[-1]) + keep
            keep = 0
if len(s) == 1:  # もし標準入力が1桁なら、そもそもスキマがないので、入力された数字をそのまま出力
    sum_ = int(s)
print(sum_)