AtCoder【ARC061 C, ABC045 C】たくさんの数式 - Many Formulas

問題

'1'~'9'の数字からなる文字列が与えられるとき、文字の間に任意の数の'+'を入れて表される数式の値の和を求めよ。

制約

C - Many Formulas

前置き

各数字の間に'+'を入れるか入れないかを考えると、全部で通りとなります。 一つの解法として、bit全探索が考えられますが、その解答例はググるといくつか出てくると思います。 そこで今回は、再帰を用いた深さ優先探索で解いてみました。 言語はGoです。

ソースコード

package main

import (
    "fmt"
    "strconv"
)

func dfs(s string, i int, lasti int, sum int) int {
    if i == len(s)-1 {
        last, _ := strconv.Atoi(s[lasti:len(s)]) // 最後に残った項
        return sum + last
    }

    n, _ := strconv.Atoi(s[lasti : i+1])
    sum1 := dfs(s, i+1, lasti, sum)  // i番目の数字の右横に'+'を入れない場合
    sum2 := dfs(s, i+1, i+1, sum+n)  // i番目の数字の右横に'+'を入れる場合

    return sum1 + sum2
}

func main() {
    var s string
    fmt.Scan(&s)

    sum := dfs(s, 0, 0, 0)
    fmt.Println(sum)
}

おまけ: bit全探索

Goでのbit全探索の回答例も載せておきます。

package main

import (
    "fmt"
    "strconv"
)

func solve(s string) int {
    sum := 0
    l := len(s) - 1  // 数字の間の数
    for bit := 0; bit < (1 << uint(l)); bit++ {  // bitの1が立っている位置に'+'を入れる
        lasti := 0
        // 各bitについて'+'を入れていってできる数式を計算
        for i := 0; i < l; i++ {
            if bit&(1<<uint(i)) != 0 {
                n, _ := strconv.Atoi(s[lasti : i+1])
                sum += n
                lasti = i + 1
            }
        }
        last, _ := strconv.Atoi(s[lasti:])
        sum += last
    }
    return sum
}

func main() {
    var s string
    fmt.Scan(&s)

    sum := solve(s)
    fmt.Println(sum)
}