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

# 問題
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/f8236105-100e-ca37-fed5-335f314ba2fc.png)
原文は[**コチラ**](https://atcoder.jp/contests/arc061/tasks/arc061_a)

# 自分でやってみた
見事に撃沈。コードは[**コチラ**](https://atcoder.jp/contests/arc061/submissions/33631468)
今の自分のレベルで分かる敗因は計算量。
あとは自らバグを埋め込んでいる事が想定される。
ま、そういう事もありますよね。

#  有識者の回答を理解
再帰的なアプローチを発見[**(コチラ)**](https://atcoder.jp/contests/arc061/submissions/24558882)。
考え方を学ぶ(まねぶ)事にした。

```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;
}
```

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

https://qiita.com/AKpirion/items/ca5ffa509e97ab3a5468

### イメージを作る
&emsp;再帰的な関数を簡単な図に置き換える

```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 ... というように動きます。)

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/2d581ff1-54bc-fc29-7478-32b8f0e10781.png)

次に _A, B_ の役割を整理してみます。

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

前述の図に具体的な動作を組み込んでみます。
![無題1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/b1ad10ea-0ef1-3e78-024c-7cb462a1eeb5.png)

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

# このアルゴは自分のモノになったと言えるのか？
正直よくわからない(笑)
後から見直したり、試行錯誤を
今後継続する事で、少しずつ身に付くかと。。

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

# 別解

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

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

https://qiita.com/drken/items/4a7869c5e304883f539b#3-5-dfs-%E3%81%AE%E8%A8%88%E7%AE%97%E9%87%8F

上記3-5 によると頂点数 _N_,辺数 _M_ の計算量は _O(N + M)_ とあります。
今回の問題では文字入力は最大 10 なので以下のような概略を考えると
頂点数を最大値で考えると _N_ は 2^0 + 2^1+ ... +2^9 = **1019**だと思う。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/b9a06c37-3612-8193-ea72-b6dcdf8f31c8.png)
辺数は 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** 
もはや、この気持ちを形容する事は要らない(泣

https://qiita.com/hryshtk/items/b848ed3bd78f940ac5af

っという分けで以下の記述に自分なりに辿り着いて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;

}
```