0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

アルゴリズム力UP!『ABC 045 C たくさんの数式 』を解いてみよう

Last updated at Posted at 2020-12-13

記事を読むとわかること

  • 記事の作者の『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の引数がやや冗長的な印象。
0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?