C-たくさんの数式を再帰の観点で眺めてみる

問題

原文はコチラ

自分でやってみた

見事に撃沈。コードはコチラ
今の自分のレベルで分かる敗因は計算量。
あとは自らバグを埋め込んでいる事が想定される。
ま、そういう事もありますよね。

有識者の回答を理解

再帰的なアプローチを発見(コチラ)。
考え方を学ぶ(まねぶ)事にした。

ans.cpp

#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int check(int index, int sum, int val)
{
    if (index == s.size()){
        return (sum * (val == 0));
    }
    return check(index + 1, sum, val * 10 + (s[index] - '0')) + 
           check(index + 1, sum + val * 10 + (s[index] - '0'), 0);
}

signed main()
{
    cin >> s;
    cout << check(0, 0, 0) << endl;
    return 0;
}

コードの追いかけ方

何したら良いかサッパリ分からない場合

 上記のコードを見たときに、全くイメージが出来ない場合は、
 まずは簡単なコードで再帰 動作イメージ作りの練習をお勧めいたします。
 過去に自分なりの記事を用意しました、参考にしていただければ幸いです。

イメージを作る

 再帰的な関数を簡単な図に置き換える

ans.cpp

int check(int index, int sum, int val)
{
    //base case
    if (index == s.size()){
        return (sum * (val == 0));
    }
           // 再帰ステップ A
    return check(index + 1, sum, val * 10 + (s[index] - '0')) + 

           // 再帰ステップ B
           check(index + 1, sum + val * 10 + (s[index] - '0'), 0);
}

再帰ステップ A,B の役割を置いておいて、全体像を考えます。
以下にあるような基本形を保って動作している事が分かります。
(コードは左から読まれるので 左側の A => A=> A=> base ... というように動きます。)

次に A, B の役割を整理してみます。

A : 1, 12, 125 のように再帰ステップを介する度に数字の桁を増やす。
 しかし、計算には使わない。
B : A で用意した数字を使って、残りの数字を足し合わせる

前述の図に具体的な動作を組み込んでみます。

赤枠にある数字を全て足し合わせると正解 176 に辿り着きます。
+ の位置と個数に注目してみてください。
全ての組み合わせを試していませんか？？(笑)

このアルゴは自分のモノになったと言えるのか？

正直よくわからない(笑)
後から見直したり、試行錯誤を
今後継続する事で、少しずつ身に付くかと。。

他に気が付いたことがあれば
後日 update します。

別解

やっぱり、なんで自分の回答がダメだったかが気になる。

1.DFS の計算量を確認
有識者の意見を参考にさせてもらいました。

上記3-5 によると頂点数 N,辺数 M の計算量は O(N + M) とあります。
今回の問題では文字入力は最大 10 なので以下のような概略を考えると
頂点数を最大値で考えると N は 2^0 + 2^1+ ... +2^9 = 1019だと思う。

辺数は 2^1 + 2^2 + .... 2^9 = 1018 って感じでしょうか。
更に葉に到達した場合は、文字を数値に変換して計算します。
あくまで最大値ですが、計算例として 1+2+3+4+5+6+7+8+9+2 を扱う場合を考える。
文字数 19 個について演算し、それが 512(2^9) 個あるはずなので 19 * 512 = 9728.
全てを合算すると O(11765)。よって DFS でも問題なく行ける。

2.int でゴリ押ししていた ort
もはや、この気持ちを形容する事は要らない(泣

っという分けで以下の記述に自分なりに辿り着いてAC となりました。
やっぱり文字列を丸ごと演算できる python とか便利ですね。
探したけど C++ には、そんなライブラリィは用意されていなかった ort.

dfs.cpp

#include <iostream>
#include <string>
using namespace std;
string s;

long long cal(string nums) {
	
	if (nums.length() == s.length()) {
		return atoll(nums.c_str());
	}

	long long sum = 0;
	string x = "";
	for (int i = 0; i < nums.length(); i++) {
		if (nums[i] != '+') {
			x += nums[i];
		}
		else {
			sum += atoll(x.c_str());
			x = "";
		}
	
	}
	sum += atoll(x.c_str());
	//cout << sum << "\n";
	return sum;
}

long long dfs(string nums , int size) {
	if (size == s.length()) {
		//cout << s[0] + nums << "\n";
		return cal(s[0]+nums);
	}
	return dfs(nums + s[size], size + 1) +dfs(nums + "+" + s[size], size + 1);
}

int main() {

	cin >> s;
	cout << dfs("", 1);

	//while (1) {};
	return 0;

}