記事を読むとわかること
- 記事の作者の『ABC 045 C たくさんの数式 』の解法がわかる
- 記事の作者のアルゴリズム問題全般へのアプローチがわかる
今回の問題
ABC 045 C たくさんの数式 → 問題文はこちら
記事の作者の回答のコード
def solve_many_formulas(num: int) -> int :
# ==============================================================
# return: ある整数値を代入すると、数と数の間に+を入れてできる数式の和の合計を返す
# pre: 125
# post:176 = (125) + (26 = 1+25) + (17 = 12+5) + (8 = 1+2+5)
# ==============================================================
# ★ step1 整数値を文字列にし、数と数の間に+を入れられるようにする
# ★ step2 文字列にした数の長さを取り、インデックスで+をいれる場所を指定できるようにする。
# ★ step3 再帰関数を用いて、+が入れられる場所を、+をいれる/入れない時で全通り調べる
# ★ step4 数と数の間に+を入れてできる数式の和を返す
#整数値を文字列にする
str_num = str(num)
#文字列にした数字の長さを取る
len_str_num = len(str_num)
#idxがlen_str_numの文字列のインデックス, sentenceが+と数値を含む文字列
def dfs(idx: int , sentence: str, str_num: str, len_str_num: int) -> int:
# 文字列idxが一番後ろに到達したかどうかを判定
if idx == len_str_num - 1:
#+で挟んでいるところで数字をわけ、数値に変更し合計値を出す
return sum(list(map(int, sentence.split("+"))))
#間に+を入れるか入れないかで分岐させ、全通り検索できるようにする
#最終的に佐伯関数からreturnした値を足算していく
return (
dfs(idx + 1, sentence + "+" + str_num[idx + 1], str_num, len_str_num)
+ dfs(idx + 1, sentence + str_num[idx + 1], str_num, len_str_num)
)
#初期値として文字列の最初のインデックス, 文字列にした数値の0行目の値,
return dfs(0, str_num[0], str_num, len_str_num)
N = int(input())
print(solve_many_formulas(N))
回答の解説
記事の作者が思う今回のアルゴリズム問題の回答ポイント
- +を入れられるように、整数値を文字列にする
- +を入れられる場所を指定できるように、文字列にした数字の長さを取る
- 全文検索で+を間に入れるかどうかで分岐をさせつつ、最終的に合計値を返す
記事の作者が思うコードのみで理解しにくい部分の解説
再帰関数"dfs"のreturn部分の処理
対象のコード
return (
dfs(idx + 1, sentence + "+" + str_num[idx + 1], str_num, len_str_num)
+ dfs(idx + 1, sentence + str_num[idx + 1], str_num, len_str_num)
)
ここでは+がある/なしのdfsを返り値に置いているが、イメージ
- 1回目dfs
-
- 2回目の(プラスありdfs + プラスなしdfs)
-
- 3回目の(プラスありの(プラスありのdfs + プラスなしのdfs) + + プラスなしの(プラスありのdfs + プラスなしのdfs))
とどんどん分岐して、最終的に dfs + dfs + dfs + ・・・・ と 合計値を返すようになる。
#このコードの課題感
- 再起関数を利用しているためメモリを食い、現場での実用性がそこまで高くない。
- dfsの引数がやや冗長的な印象。