蟻本 §2-1-1 部分和問題 ARC 061 C を Python で AtCoder Regular Contest 061 C

2020年4月26日

蟻本 §2-1-1 部分和問題 類題「ARC 061 C – たくさんの数式」を Python で解説していきたいと思います。
蟻本のこの部分和問題の解説はこちら
類題はもう競プロ界隈ではおなじみとなっている,こちらのAtCoder 版!蟻本 (初級編)から参照させていただきました。
蟻本 §2-1-1 部分和問題の Python でのコードはこちらで解説しています。
それでは,まずは問題文から。
https://atcoder.jp/contests/arc061/tasks/arc061_a


C – たくさんの数式


実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

1 以上 9 以下の数字のみからなる文字列 S が与えられます。 この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。 一つも入れなくてもかまいません。 ただし、+ が連続してはいけません。

このようにして出来る全ての文字列を数式とみなし、和を計算することができます。

ありうる全ての数式の値を計算し、その合計を出力してください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

S

出力

ありうる全ての数式の値の総和を 1 行に出力せよ。


入力例 1

125

出力例 1

176

考えられる数式としては、 1251+2512+51+2+5 の 4 通りがあります。それぞれの数式を計算すると、

  • 125
  • 1+25=26
  • 12+5=17
  • 1+2+5=8

となり、これらの総和は 125+26+17+8=176 となります。


入力例 2

9999999999

出力例 2

12656242944

解説

蟻本で学んだ深さ優先探索(DFS)で解いていきましょう。蟻本の問題と全く同じで,2^nの問題になります。まずは遷移図を書いて考えていきます。初期値を i = 0, l = '1’ とします。ここで i を処理を行った回数,l をその時点での数字の文字列とします。

以上のように,n を文字列 s の長さとすると,i = n-1 になるまで DFS は行われます。そのそれぞれについて,文字列として '足す’ のか,数値計算として '+’ を用いた和として '足す’ のかの2通りがあり,最終の状態は 2^(n-1) 通りとなります。
この操作は,l を文字列として考えているので,

  • 文字列として '足す’ → l_i+1 = l_i + s[i+1] ex.) ’12’ = '1’ + '2’
  • 数値計算として '+’ を用いた和として '足す’ → l_i+1 = l_i + “+" + s[i+1] ex.) '1+2’ = '1’ '+’ '2’

で文字列として表現できます。
最終的に文字列を数値に戻して全体の状態の和を取ればいいのですが,例えば次の文字列 ' 12 + 5 ' は,int を用いて int(’12+5′) としようとしてもエラーがでて怒られます。そこで,まず関数 split() を用いてこれを ’12’ と '5’ の文字列に分解した後に int 型にします。具体的には,まず l.split(“+") とすることで,l を '+’ で分解できます。以上の作業は,競プロの標準入力でおなじみの map を用いて,

map(int, l.split("+"))

で表せます。l の全要素の和を取りたいので,これをリスト型にして sum を用いることで,次のように書けます。

sum(list(map(int, l.split("+"))))

DFS の動きの中身は以上のようになります。
それでは,解答例を載せておきます。

解答例

s = input()
n = len(s)

def dfs(i, l):
    if i == n-1:
        return sum(list(map(int, l.split("+"))))
    return dfs(i+1, l+s[i+1]) + dfs(i+1, l+"+"+s[i+1])

print(dfs(0, s[0]))

いかがだったでしょうか。
慣れないと少し難しい考え方ですが,図を書いたら理解しやすいかと思います。
参考になりましたら,Twitterでフォローお願いします
それでは。

他の蟻本系統の問題も解説していますので,こちらも是非ご覧ください。
AtCoder 版!蟻本 (初級編)を参考にさせていただいております。

蟻本 §2-2-1 部分和問題
ARC 061 C – たくさんの数式
ABC 079 C – Train Ticket