LoginSignup
2
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 1 year has passed since last update.

@AKpirion

再帰が出来ない自分と向き合ってみた

Last updated at Posted at 2022-05-23

初日:例題1 組み合わせカウント

"o", "x" のいずれかを選び、並べて
4文字からなる文字列を作成する場合、何通りあるか？

実際に自力でリストしてカウントしてみた。

a b c d
1 o o o o
2 o o o x
3 o o x o
4 o o x x
5 o x o o
6 o x o x
7 o x x o
8 o x x x
9 x x x x
10 x x x o
11 x x o o
12 x x o x
13 x o x x
14 x o x o
15 x o o o
16 x o o x

答えは 2^4 となるので 16通り。
でも、本当に間違いない？？

漏れの無いリスト作り

手書きだと記載漏れのリスクがあるが
良い考え方が無いだろうか。

試しにソフトウェア先輩に解いてもらったので
以下に添付する。

a b c d
1 o o o o
2 o o o x
3 o o x o
4 o o x x
5 o x o o
6 o x o x
7 o x x o
8 o x x x
9 x o o o
10 x o o x
11 x o x o
12 x o x x
13 x x o o
14 x x o x
15 x x x o
16 x x x x

冒頭にある自力リストと違い、
ソフト先輩はある法則に基づいて
リストされているようです。

それは、右端から少しずつ変化させている点です。
それは例えば4 桁の 2進数を 1 ずつインクリメントしているかの如く。。
このやり方に沿えば、確かに全てを漏れなくリストできる。
美しい、まぶいです!!先輩!!

どうやって右端から変えていくか

適当なサブルーチン(ここでは rec )の中でfor文を使います。
"o" => "x" の順に代入できる記述を用意するイメージです。
ここまでは簡単。

あとは for 文の中に更に rec を呼び出したら
どうなるでしょうか。
例えば、こんな感じで。。。

rec_sample_r0.cpp
void rec(vector<string>& space) {
	string c = "ox";
	for (char c0 : c) {
		space.push_back({ c0 });// <= char c0 をバッファ 
		rec(space);             // <= rec を call 
	}
}

動きを読み上げると以下のようになると思います。

rec call 回数 バッファ値
1回目 for start で "o" をバッファ "o"
rec を call
2回目 for start で "o" をバッファ "oo"
rec を call
3回目 for start で "o" をバッファ "ooo"
rec を call
4回目 for start で "o" をバッファ "oooo"
rec を call
5回目 "o"x4 なので打ち止め。return で再帰 終了

但し、rec_sample_r0.cpp では 5 回目の rec call 時に
文字サイズ == 4 の場合、再帰終了となる記述がありません。
ちょろっと追加してみます。

rec_sample_r1.cpp
void rec(vector<string>& space) {
	if (space.size() == 4) {
		for (int i = 0; i < 4; i++)
			cout << space[i];
		cout << "\n";
		return;                 // <=再帰終了
	}
	string c = "ox";
	for (char c0 : c) {
		space.push_back({ c0 });// <= char c0 をバッファ 
		rec(space);             // <= rec を call 
	}
}

ここまでで "oooo" を表示しました。
先ほどの表の続きを記載しますが、ここが一番厄介w。

rec call 回数 バッファ値
中略
4回目 for start で "o" をバッファ "oooo"
rec を call
5回目 "o"x4 なので打ち止め。return で再帰 終了
追記項目 <= ここまでで、4回目の for 文 変数 = "o" の時のアクションが全て終了

っとなるので、4回目の for にて変数が "o" となる制御が終わったのであれば
次は 4 回目の for 文における変数 = "x" の処理が始まります。
但し、このまま戻って文字を追加すると "oooox" となります、いかんです。
そこで以下のような記述を追加します。

rec_sample_r1.cpp
void rec(vector<string>& space) {
	if (space.size() == 4) {
		for (int i = 0; i < 4; i++)
			cout << space[i];
		cout << "\n";
		return;                 // <=再帰終了
	}
	string c = "ox";
	for (char c0 : c) {
		space.push_back({ c0 });// <= char c0 をバッファ 
		rec(space);             // <= rec を call 
        space.pop_back();       // <= 追加!! 文字列サイズを 3 に落とす
	}
}

以上を文字に起こしてみます。

rec call 回数 バッファ値
中略
4回目 for start で "o" をバッファ "oooo"
rec を call
5回目 "o"x4 なので打ち止め。return で再帰 終了
4回目の for 文に戻る
4回目 pop_back() で文字数を 4 から 3 に削減 "ooo"
ここまでが変数 = "o" における For 文の処理
次は変数 = "x" の場合の For 文が start
4回目 "x" をバッファ "ooox"

以上のように 4 回目の For 文で "o" => "x" が終わると
3回目の For 文に戻り、変数 = "x" の場合で、更に 4 回目の For 文へと
潜っていきます。

2日目:深呼吸して図で整理

文字だけでは分かりにくいと思うので
図に起こしてみます。

まず、ここで定義している rec というルーチンは
for 文で "o" => "x" と制御しています。
イメージは以下です。
※緑の領域が rec という箱を表しており中身(動作)は o => x となっています

無題.png

しかし、for 文の 変数 = "o" とした処理の中で rec を呼び出しています。
そのため呼び出した rec 内で新たな for 文が start します。
更に、この for 文が、新たな rec を call して行くために、
以下のような動きになってしまいます。

無題2.png

rec を 4 回 call するとバッファした文字サイズは 4 となるので
rec の 5 回目の call の際には、文字を表示して再帰を終了します。
処理が終わったので rec 4 回目に戻りましょう。

rec 4 回目に戻ってきたら、以下のコードのコメントにあるように一文字削除します。

rec_sample_r1.cpp
void rec(vector<string>& space) {
	if (space.size() == 4) {
		for (int i = 0; i < 4; i++)
			cout << space[i];
		cout << "\n";
		return;                 
	}
	string c = "ox";
	for (char c0 : c) {
		space.push_back({ c0 }); 
		rec(space);             // <= rec 4 回目から戻ってきた。buffer 値は "oooo" 
        space.pop_back();       // <= 文字列サイズを 3 に落とす。buffer 値は "ooo"
	}
}

1文字削除した状態("ooo")で、次は for 文の変数 = "x" の場合で
処理を始めるので、"x" をバッファした "ooox" で 5回目の rec の call に臨みます。
以下にコメントを変えて記載してみました。

rec_sample_r1.cpp
void rec(vector<string>& space) {
	if (space.size() == 4) {
		for (int i = 0; i < 4; i++)
			cout << space[i];
		cout << "\n";
		return;                 
	}
	string c = "ox";
	for (char c0 : c) {
		space.push_back({ c0 });// <= "ooo" に "x" をプラス。
		rec(space);             // <= rec に "ooox" を代入して call
        space.pop_back();       
	}
}

念のため図示してみました。
文字数 4 となり "oooo" を表示したら、文字数を 3 に削減します。
その後、For 文の変数 = "x" の場合の処理に移るイメージです。
無題3.png
"ooox" を表示したら rec 4 回目に戻って 1文字削除します。
ここまで実行することで rec 4 回目の For 文は終了です!! お疲れ様でした。
これが終わると晴れて rec 3 回目に戻ることが出来ます、"ooo" の状態で。
その後の動きがどうなるのか、コードのコメントで補足します。

rec_sample_r1.cpp
void rec(vector<string>& space) {
	if (space.size() == 4) {
		for (int i = 0; i < 4; i++)
			cout << space[i];
		cout << "\n";
		return;                 
	}
	string c = "ox";
	for (char c0 : c) {
		space.push_back({ c0 });
		rec(space);             // "ooo" で rec 4 回目から戻ってくる
        space.pop_back();       // "ooo" から 1 文字削除して "oo" となる
	}                           // for 文の変数 = "x" の場合で Go!!
}

なるほど。
っつーことは、こんな感じになるって事か!!

無題4.png

3日目:自分の理解を疑う

前項で再帰のイメージを我が物顔で語ったが、
本当に正しければ図で追いかけた出力と
冒頭のソフトの output は一致するはずである。
やってみよう。

無題_final.png

以下が、ソフトウェア先輩の出力を上図に併せて変形させたもの

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
rec 1 回目 o o o o o o o o x x x x x x x x
rec 2 回目 o o o o x x x x o o o o x x x x
rec 3 回目 o o x x o o x x o o x x o o x x
rec 4 回目 o x o x o x o x o x o x o x o x

なるほど、一致しますね。
ここまでやって、やっと安心しました。
少しは成長できたかも。

char_combination_rec.cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void rec(vector<string>& space) {

	if (space.size() == 4) {
		for (int i = 0; i < 4; i++)
			cout << space[i];
		cout << "\n";
		return;
	}

	string c = "ox";
	for (char c0 : c) {
		space.push_back({ c0 });
		rec(space);
		space.pop_back();
	}

}

int main() {
	vector<string> space;
	rec(space);
	while (1) {};
	return 0;
}

4日目:別解を考察

@myoukaku さんに頂いたアイディアです。
再帰感をもっと出してみたコードを追いかけてビックリ。

冒頭の解は、ポインタを使って、
rec から rec を呼び出すたびに変更した値を持ち越していました。
そのため、表示が終わった後に pop_back() を使わないと
文字数 4 を維持が出来ません。

しかし今回は、ポインタを使わない事で
文字数 4 となり、return したとしても
そもそも引数そのものを変更したわけではないので
pop_back() を必要としません。

これは vector の記述を必要としないので
シンプルに書けるメリットがあります。すばらしいです。

char_combination_rec.cpp
#include <iostream>
#include <string>
using namespace std;

void rec(string buff) {

	if (buff.length() == 4) {
		cout << buff << "\n";
		return;
	}
	//if (buff.size() == 4) {
	//	for (int i = 0; i < 4; i++)
	//		cout << buff[i];
	//	cout << "\n";
	//	return;
	//}
	
	rec(buff + 'o');
	rec(buff + 'x');

}


int main() {
	string buff = "";
	rec(buff);
	while (1) {}
	return 0;
}

無理やり Vector を使ってみました。

char_combination_rec.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void rec(vector<string>& buff) {

	if (buff.size() == 4) {
		for (int i = 0; i < 4; i++)
			cout << buff[i];
		cout << "\n";
		return;
	}
	
	buff.push_back({ 'o' });
	rec(buff);
	buff.pop_back();

	buff.push_back({ 'x' });
	rec(buff);
	buff.pop_back();

}


int main() {
	vector<string> buff;
	rec(buff);
	while (1) {}
	return 0;
}

ポインタが無い方がスマートなのは一目瞭然ですね(笑)

5日目:例題2 文字列の反転

文字列を反転させる記述を再帰で書いてみました。
文字数が偶数/奇数のいずれでも逆転できます。

reverse_char.cpp
#include <iostream>
#include <string>
using namespace std;

void rec(string s,int i) {

	int target = s.length() / 2;
	
	if (i == target) {
		cout << s << "\n";
		return;
	}

	swap(s[i], s[s.length() - (i + 1)]);
	i++;
	rec(s, i);

}


int main() {

	string s = "abcde";
	rec(s,0);
	while (1) {};
	return 0;

}

手探りでの理解も良いが、ちゃんと教わりたい。
英語だが、ココ に色々説明があった、有難い。

6日目:Leetcode 先生による再帰の講義を翻訳してみた

Recursion is an approach to solving problems using a function that calls itself as a subroutine.
再帰とはサブルーチンとして自らを呼び出すことで問題を解くアプローチを指します。

You might wonder how we can implement a function that calls itself.
The trick is that each time a recursive function calls itself,
it reduces the given problem into subproblems.
The recursion call continues until it reaches a point
where the subproblem can be solved without further recursion.
もしかしたら、どうやって自らを呼び出すのか疑問に思うかもしれません。
再帰として自らを呼び出す度に、問題を分解し、
小さい問題へと変形させていく事が再帰のコツになります。
再帰は終着点まで自らを呼び出し続けます。

A recursive function should have the following properties
so that it does not result in an infinite loop:
再帰処理は無限ループには陥らない為に、以下の制約があります。

 1.A simple base case (or cases)
  — a terminating scenario that does not use recursion to produce an answer.
 2.A set of rules,
  also known as recurrence relation that reduces all other cases towards the base case.
 Note that there could be multiple places where the function may call itself.
 1.単純な base case - 再帰を終了させる記述
 2.漸化式として知られているように、
  base case(再帰を終了させる記述)に向かって問題を分割していきます。
 重複して call する可能性がある事に注意が必要です。

Leetcode 先生から Example を賜る

Let's start with a simple programming problem:
簡単なプログラムに挑戦してみよう

Print a string in reverse order.
文字列を反転させて表示しよう

You can easily solve this problem iteratively, i.e.
looping through the string starting from its last character.
But how about solving it recursively?
私たちは最後の文字から一文字ずつループで
表示させることで簡単に問題を解決できます。
では、これを再帰で解決してみましょう。

First, we can define the desired function as printReverse(str[0...n-1]),
where str[0] represents the first character in the string.
Then we can accomplish the given task in two steps:
最初に再帰処理を printReverse(str[0...n-1]) として定義します。
因みに str[0] は文字列の先頭を指します。
以下の 2 ステップで実現する事が出来ます。

 1.printReverse(str[1...n-1]): print the substring str[1...n-1] in reverse order.
 2.print(str[0]): print the first character in the string.
Notice that we call the function itself in the first step, which by definition makes the function recursive.
 1.printReverse(str[1...n-1]): str[1...n-1] を逆順で表示
 2.print(str[0]): 文字列の先頭を表示
最初に自分を呼び出してください、さすれば、再帰処理となるであろう。

example_reverse_string.cpp
void printReverse(const char *str) {
  if (!*str)
    return;
  printReverse(str + 1);
  putchar(*str);
}

Next, you will find an exercise that is slightly different from the above example.
You should try to solve it using recursion.
Note: For this exercise, we also provide a detailed solution in this Explore chapter.
次は、上記例題と少し異なる例題があります。
再帰を駆使して解いてみましょう。
注意:この章では詳解も併せて提供しております。

Leedcode 先生の回答例の考察

どこぞの素人解とは比べ物にならないくらいスマートな解で衝撃。
ポインタを使い、文字列の最後に至るまでアドレスをインクリメント。
格納した文字列の次のアドレスが空であることを前提にプログラムされていると思いますが、
これを超えて開いたアドレスに値が無ければ、再帰を終了としています。
あとは格納データの最終アドレスから先頭アドレスに向けて一つずつデータを呼び出すことで
逆転した文字列を表示しております、素晴らしい。
こんな素晴らしい世界があるんですね、もっと知りたい。。

結局 Leetcode 先生は何が言いたかったのか

"再帰" というアプローチで問題を分割し、
それぞれの結果を統合する事で問題を解く手法を御教示してくれたのでしょう。
有難うございます。

7日目:例題3 最大値の探索

int nums[4] で与えられる正の整数から最大値を探索してみよう。
但し、nums[4] の要素はランダムで配置されています。

レベルを下げて考える

再帰処理のポイントは以下でした。
1.base case を意識(さもなくば無限ループとなる)。
2.問題を分割しながら、それぞれの部分解を繋ぎ合わせて問題を解く(次へ渡しつつ、今、部分的に解けないか考える)

問題の意図にあるように配列から最大値を選ぶのであれば、
右 or 左端まで移動し、隣接する値と一個ずつ比較していく事が望ましい。

まずは、与えられた配列を一個ずつ端から表示して、連結してみる。

step1_view.cpp
#include <iostream>
using namespace std;

void rec(int nums[], int i) {
	if (i == 3) {
		cout << nums[i];
		return;
	}
	rec(nums, i+1);
	cout << nums[i];
}

int main() {
	int nums[4] = {1,3,2,1};
	rec(nums, 0);
	while (1) {};
	return 0;
}

詳細な解説は不要だと思うが
一番最後の項目まで辿り着いたら表示。
その後、一つ手前の値を表示。
これを再帰で処理してみた。

上記をベースに変更ポイントを考察した。
・rec 内では i+1 と i を両方表示する事が出来る
=>表示ではなく比較に変換できないか？
=>比較した値を return すれば再帰処理で比較ができる

これを反映させたコードが以下の記述です。

findMax.cpp
#include <iostream>
using namespace std;

int rec(int nums[], int i) {
	int x,y;
	if (i == 3) {
		return nums[3];
	}
	x = rec(nums, i + 1);
	y = max(x, nums[i]);

	return y;
}

int main() {
	int nums[4] = {1,3,2,1};
	int ans;
	ans = rec(nums, 0);

	cout << ans << "\n";

	while (1) {};
	return 0;
}

別解

以下のような変態的アプローチもあります。

SearchMax.cpp
#include <iostream>
using namespace std;

int SearchMax(int A[], int l, int r) {
	int m, u, v, x;
	m = (l + r) / 2;
	if (l == r - 1)
		return A[l];
	else
		u = SearchMax(A, l, m);
		v = SearchMax(A, m, r);
		x = max(u, v);
		return x;
}

int main() {
	int ans;
	int nums[] = {1,7,3,4};
	ans = SearchMax(nums, 0, 4);
	cout << ans << "\n";
	while (1) {};
	return 0;
}

解説 STEP1 大枠をイメージ

基本に忠実が大事です。
1.base case を意識(さもなくば無限ループとなる)。
2.問題を分割しながら、それぞれの部分解を繋ぎ合わせて問題を解く
 (次へ渡しつつ、今、部分的に解けないか考える)

まずは、配列を表示させるプログラムから考えます。

view_nums.cpp
#include <iostream>
using namespace std;

void rec(int nums[], int l, int r) {
	int m;
	m = (l + r) / 2;
	if (l == r - 1)
		cout << nums[l];
	else {
		rec(nums, l, m);
		rec(nums, m, r);
	}
}

int main() {
	int nums[4] = { 1,2,3,4 };
	rec(nums, 0, 4);
	while (1) {};
	return 0;
}

動作イメージは以下です。

image_overview.png

これを表示ではなく、比較するために
以下のようにイメージしてみました。

image_overview_comp.png

これで晴れて変態的アプローチでも問題を解くことが出来るようになります。
オメデトウございます。

解説 STEP2 配列長を変えてみる

冒頭では 0, 4 を入力して nums[0:3] を表示していました。、
では、 0,3 を入力したら nums[0:2] を表示できるのでしょうか。

kisuu.png

解説 STEP3 考えをまとめる

自分が考える本アルゴリズムのポインタは以下だと思う。

1.(l+r)/2 = m かつ、再帰的に rec(l,m) , rec(m,r) と call する事で
 どこかで l=r-1 に辿り着ける。※l=r-1 は Base case (再帰の終了地点)
2.rec(l,m) , rec(m,r) と、それぞれ入力に m を必要としているが
 一貫して num[l] を return するため、重複なく正常にアルゴが機能している。

絶妙なバランスでアルゴリズムが
成立している,素晴らしい。

別解2 もっとシンプルに考える

最終項から初項へ戻る再帰処理に
最大値を探す処理を埋め込んでみた。

search_maximum.cpp
#include <iostream>
using namespace std;
int test[5] = {1,2,3,4,5};

int rec(int n) {
	if(n == 4) 
		return test[4];

	int num = rec(n+1);
	return max(num, test[n]);
}

int main() {
	cout << rec(0);
	while (1) {}
	return 0;
}

まぁ、当初の回答と、
そんなに変わらないかも。。(笑)

8日目: 例題4 全探索

num[5] = {1,5,7,10,21} の何れかを足し合わせて、
m[4] = { 2,4,17,8 } の各項が作れるか確認してください。
出来る場合は yes, 出来ない場合は no と回答してください。

解答

例題 3 にあるように base case まで到達したら start 地点まで値を返す。
但し、比較しながら返す事で最大値を求める 例題 3 とは異なり、
True(1) or False(0) を返すだけで良い。

AllSerch.cpp
#include <iostream>
using namespace std;

int rec(int num[], int sum,int i,int m) {
	int u, v;
	if (i == 5) {
		if (sum == m)
			return 1;
		else
			return 0;
	}

	u = rec(num, sum + num[i], i + 1,m);
	v = rec(num, sum         , i + 1,m);

	if (u == 1 or v == 1)
		return 1;
	else
		return 0;
}

int main() {
	int sum = 0;
	int num[5] = { 1,5,7,10,21 };
	int  m[4] = { 2,4,17,8 };
	

	for (int j = 0; j < 4; j++) {
		if (rec(num, sum, 0, m[j]))
			cout << "yes\n";
		else
			cout << "no\n";
	}

	while (1) {};
	return 0;
}

//実行結果
//no  m[0] = 2 は 実現できる？
//no  m[1] = 4 は 実現できる?
//yes m[2] = 17は 実現できる？
//yes m[3] = 8 は 実現できる？

しかし、いきなりココに辿り着いたわけではないです。
一旦は { 選ぶ、選ばない} を組み合わせた結果を全て表示する所まで
レベルを下げました。

all_case_view.cpp
#include <iostream>
using namespace std;

void rec(int num[], int sum,int i) {
	if (i == 5) {
		cout << sum << " ";
		return;
	}
	rec(num, sum + num[i], i + 1);//選ぶ
	rec(num, sum         , i + 1);//選ばない
}

int main() {
	int sum = 0;
	int num[5] = { 1,5,7,10,21 };
	
	rec(num, sum, 0);

	while (1) {};
	return 0;
}
//実行結果
//44 23 34 13 37 16 27 6 39 18 29 8 32 11 22 1 43 22 33 12 36 15 26 5 38 17 28 7 31 10 21 0

イメージは以下のような感じの全探索です。

zen_search_image.png

うん、問題なさそうだ。
あとは、各 base case と 取り急ぎ m[0] を比較してみる。
一個でも一致すれば 1 を返す、こんな感じで。

view1.png

その結果が以下になります。

all_serch_m0.cpp
#include <iostream>
using namespace std;

int rec(int num[], int sum,int i) {
	int u, v;
	if (i == 5) {
		if (sum == 2)//m[0] とイコール？
			return 1;
		else
			return 0;
	}

	u = rec(num, sum + num[i], i + 1);
	v = rec(num, sum         , i + 1);

	if (u == 1 or v == 1)
		return 1;
	else
		return 0;
}

int main() {
	int sum = 0;
	int num[5] = { 1,5,7,10,21 };
	
	if (rec(num, sum, 0))
		cout << "yes\n";
	else
		cout << "no\n";

	while (1) {};
	return 0;
}

あとは m[0] だけでなく、m[0:3] と確認したいので、
以下のようなアプローチで変更を掛けていきます。

1.rec には m の値を持ち越せるように変数を追加
2.その m の値を for 文で切り変えるように考察
3.冒頭の回答に辿り着く

別解の無駄を省けないか検討

今回 m は 4 つの要素を含んでいたので、4 回、以下の全探索を繰り返していた。

view1.png

例えば、4 回 探索する事は仕方ないにしても、
m と該当する要素を見つけたら探索を Stop する事は出来ないのでしょうか。
取り急ぎ、こんな記述で動作確認ができました。

all_search_until_Fit.cpp
#include <iostream>
using namespace std;

int rec(int num[], int sum, int i, int m,int u,int v) {

	if (i == 5) {
		cout << sum << " ";
		if (sum == m)
			return 1;
		else
			return 0;
	}
	
	if (u != 1)
		u = rec(num, sum + num[i], i + 1, m,u,v);

	if (u != 1 && v != 1)
		v = rec(num, sum, i + 1, m,u,v);

	if (u == 1 or v == 1)
		return 1;
	else
		return 0;
}

int main() {
	int sum = 0;
	int num[5] = { 1,5,7,10,21 };
	int  m[4] = { 2,4,17,8 };
	int v = 0;
	int u = 0;

	for (int j = 0; j < 4; j++) {
		if (rec(num, sum, 0, m[j],u,v))
			cout << "yes\n";
		else
			cout << "no\n";
	}

	while (1) {};
	return 0;
}

/*
実行結果
44 23 34 13 37 16 27 6 39 18 29 8 32 11 22 1 43 22 33 12 36 15 26 5 38 17 28 7 31 10 21 0 no //m[0]=2
44 23 34 13 37 16 27 6 39 18 29 8 32 11 22 1 43 22 33 12 36 15 26 5 38 17 28 7 31 10 21 0 no //m[1]=4
44 23 34 13 37 16 27 6 39 18 29 8 32 11 22 1 43 22 33 12 36 15 26 5 38 17 yes                //m[2]=17
44 23 34 13 37 16 27 6 39 18 29 8 yes                                                        //m[3]=8
*/

どうしても該当がない場合は全探索してしまいます。
該当を見つけた場合は切り上げている事が分かります。

9日目:例題5 フィボナッチ数列を表現

まずは定義を確認
無題.png
n==0 のとき,F2 = F0 + F1 となることから
プログラムで表現するときは F2,F3,F4... となるように
F2 から start する記述である必要があります。

Fibonacci.cpp
#include <iostream>
using namespace std;

int rec(int n) {
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	return rec(n - 1) + rec(n - 2);
  //return rec(n - 2) + rec(n - 1); also works 
}

int main() {
	int ans = 0;
    //rec() needs more than int value 2.
	ans = rec(5);
	cout << ans << "\n";
	while (1) {};
	return 0;
}

動作イメージを図にしてみました。
無題_tree.png
図を眺めていると計算の重複が確認できます。
これをメモで適時残しながら処理できると
処理時間を短縮できます。

ベースは以下のような感じで OK

memo_Fibonacci.cpp
#include <iostream>
using namespace std;

int rec(int n,int *table) {
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (table[n] > 0)
		return table[n];
	table[n] = rec(n - 1, table) + rec(n - 2, table);
}

int main() {
	int ans = 0;
	int table[6] = { 0,1,0,0,0,0 };
	rec(5,table);
	cout << table[5] << "\n";
	while (1) {};
	return 0;
}

ポインタの理解が怪しいので
いつか修正するかも(笑)。。

10日目:もっと基礎を固めたくなった

ココ に Good lecture を発見。
早速、読みつつ、自分で検討してみる。

0からnまでの総和を計算する関数

自分は以下のように考えた。

sum.cpp
#include <iostream>
using namespace std;
int rec(int n) {
	if (n == 0)
		return 0;
	return n + rec(n - 1);
}

int main() {
	cout << rec(10) << "\n";
	while (1) {};
	return 0;
}

/*
//lecture を受けると以下の
//記述もイメージできるようになる。
int rec(int n) {
	if (n == 0)
		return 0;
	int s = rec(n - 1);
	return s + n;
}
*/

AからBまでの総和を求める関数

あれ？冒頭の記述をカスタムすると実現出来る気が。。
0 から 10 を足してみます。

sumAtoB.cpp
#include <iostream>
using namespace std;

int rec(int n) {
	if (n == 10)
		return 10;
	int s = rec(n + 1);
	return s + n;
}

int main() {
	cout << rec(0) << "\n";
	while (1) {};
	return 0;
}

上記は a + a+1 + a+2 のように下から足していくパティーン。
他にも b + b-1 + b-2 のように上から足していくパティーンを勉強させてもらった。

sumBtoA.cpp
#include <iostream>
using namespace std;

int rec(int a,int b) {
	if (a == b)
		return a;
	return b + rec(a, b - 1);
}

int main() {
	cout << rec(0,10) << "\n";
	while (1) {};
	return 0;
}

素数を判定する

素数の定義 を明確にしてからコードを書いてみる。
判定したい自然数を n とする。

1,2,3,4..n-1 について、n の約数であれば false
違うのであれば true とそれぞれ判定して論理積で合算。
all ture であれば素数と言える。
逆に false であれば素数と言えない。
但し、1 は n の約数ではあるが素数ではないので取扱いに注意する。

isPrime.cpp
#include <iostream>
using namespace std;

bool isPrime(int n,int i) {
	if (i == n)
		return true;

	bool flag;
	if (n % i == 0)
		flag = false;
	else
		flag = true;

	return flag && isPrime(n,i+1);
}

int main() {

	int nums[] = { 1,2,12,13,57 };

	for (int n:nums) {
		if (n!=1)
			if (isPrime(n, 2))
				cout << 1 <<"\n";
			else
				cout << 0 << "\n";
		else
			cout << 0 << "\n";
	}

	while(1) {};
	return 0;

}

解説を読んで回答を再考察してみると
以下のポイントが浮かび上がる。

・ n%i==0 であれば如何なる時でも false を return できれば
 1,2,3,...n-1 を全て検証する必要は無い

・n==i まで処理を進めたのであれば素数と判断して OK

よって、以下のように最適化できる。

isPrime.cpp
//before
bool isPrime(int n,int i) {
	if (i == n)
		return true;

	bool flag;
	if (n % i == 0)
		flag = false;
	else
		flag = true;

	return flag && isPrime(n,i+1);
}

//after
bool isPrime(int n,int i) {
	if (i == n)
		return true;

	if (n % i == 0)
		return false;

	return isPrime(n,i+1);
}

配列の逆転(reverse_array)

問題はシンプル。
今回はポインタを使って、下図のイメージで
再帰的に各要素を逆転させてみました。

reverse_image.png

reverse_array.cpp
#include <iostream>
using namespace std;

void reverse(int nums[], int l, int r) {

	if (l >= r)    //if length of array is odd , base case trigger is l==r
		return;    //if length of array is even, base case trigger is l>r

	int buf = nums[l];
	nums[l] = nums[r];
	nums[r] = buf;

	reverse(nums, l + 1, r - 1);
}

int main() {

	int nums[5] = { 0,1,2,3,4 };
	for (int n : nums)
		cout << n << " ";
	cout << "\n";

	reverse(nums, 0, 4);

	for (int n : nums)
		cout << n << " ";

	while (1) {};
	return 0;
}

/*
実行結果
0 1 2 3 4
4 3 2 1 0
*/

別解

例えば以下のような vector を使って表現してみる。
まずは、再帰を使わずに書いてみる。

reverse_vector.cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> reverse(vector<int> nums, vector<int>buff) {
	for (int i = 0; i < 5; i++){
		buff.push_back(nums.back());
		nums.pop_back();
	}
	return buff;
}

int main() {

	vector<int> nums{ 0,1,2,3,4 };
	vector<int> buff;

	buff = reverse(nums,buff);

	for (int i = 0; i < 5; i++)
		cout << buff[i] << " ";

	while (1) {};
	return 0;
}

これをベースに再帰的な処理に改造する。

アイディアとしては、
元データ nums と push_back で少しずつデータを追加している buff を
再帰的に関数の引数として持ち運べば、解けるかもっと考えた。

reverse_vector_r1.cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> reverse(vector<int> nums, vector<int>buff, int i) {
	if (i == 5)
		return buff;

	buff.push_back(nums.back());
	nums.pop_back();
	return reverse(nums,buff,i+1);
}

int main() {
	vector<int> nums{ 0,1,2,3,4 };
	vector<int> buff;

	for (int i = 0; i < 5; i++)
		cout << nums[i] << " ";
	cout << "\n";

	buff = reverse(nums, buff, 0);

	for (int i = 0; i < 5; i++)
		cout << buff[i] << " ";

	while (1) {};
	return 0;
}

/*
実行結果
0 1 2 3 4
4 3 2 1 0
*/

とりあえず自力で目星をつけることが出来た。
解説を読んでみた。***.at(3) というような
記述で vector 内の任意の値を取り出せるようだ。
これがあれば確かに関数の引数を減らすことが出来る。
こんな感じだ。

reverse_array.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> reverse(vector<int> nums, int i) {
	vector<int>space;

	if (i == 5)	
		return space;

	space = reverse(nums, i + 1);
	space.push_back(nums.at(i));

	return space;
}

int main() {

	vector<int> nums{ 0,1,2,3,4 };
	vector<int> buff;

	for (int i = 0; i < 5; i++)
		cout << nums[i] << " ";
	cout << "\n";

	buff = reverse(nums, 0);

	for (int i = 0; i < 5; i++)
		cout << buff[i] << " ";

	while (1) {};
	return 0;
}

勉強になりました。

報告書の伝達時間

個人的にはラスボス感が半端ない問題でした。
ヒントや tree の考え方をしっかり参考にして
生まれて一番頭を使いました(泣)。

・vector による多次元配列を初体験

・例えば 0 を上司とする 1, 3, 5 をまとめてメモ。
 イメージとしては vector>parent を用意して parent.at(0) に、
 {1,3,5} が格納されているよーな感じ

・ヒントにある _for (int x: parent.at(i))_を使う
 格納されている要素を頭から取り出す。今回 1 を取り出したら、
 _parent.at(1)_に移動、かつ移動回数を数える。空だったら return(=base case)
 移動回数が最も多い経路を return できればイケるのでは???

last_boss.cpp
#include <iostream>
#include <vector>
using namespace std;

int rec(vector<vector<int>>parent, int i) {

	if (parent.at(i).empty())
		return 0;

	int Vmax = 0;
	for (int x: parent.at(i)) {       // <= ヒントを流用
		int ref = rec(parent, x) + 1;
		Vmax = max(ref, Vmax);
	}
	return Vmax;
}

int main() {

	vector<int>pin{ -1, 0, 0, 1, 1, 4 };
	vector<vector<int>> parent(6);   // <= サイズをキッチリ定義しないと
                                     //    再帰処理時に無限loop に入る

	for (int i = 1; i < 6; i++) {
		parent.at(pin.at(i)).push_back(i);
	}

	cout << rec(parent, 0) <<"\n";

	while (1) {};
	return 0;
}

途中で出力する例

再帰ステップに入る前に現状を print すれば下っているように見える。
再帰ステップから出た後に現状を print すれば上がっているように見える。
下り、上りの基本動作がイメージできていれば、この問題はむしろ楽しい。

down2up.cpp
#include <iostream>
using namespace std;

void func(int i) {

	if (i == 0) {
		cout << "func in :" << i << "\n";
		cout << "func out:" << i << "\n";
		return;
	}
	cout  << "func in :" << i << "\n";
	func(i - 1);
	cout  << "func out:" << i << "\n";

}

int main() {

	func(3);
	while (1) {};
	return 0;

}

引数の配列を変化させる例

迷路から抜けれるかどうか。っという問題。
回答をパッと見たがコードが長い。
やる気が失せたort

自力で検討したが、難しかったので、
過去の自分の記事を読み直した(コチラ)。
なるほど。。
さてさて、どう C++ に落とそうか、どう 再帰処理としようか。。
以下のような記述はどうだろうか。

maze.cpp
#include <iostream>
#include <vector>
using namespace std;


bool rec(int x,int y, int N, vector<vector<char>> map, vector<vector<bool>> memo) {

	if (x == N - 1 && y == N - 1)
		return true;
		
	vector<vector<int>> direction{ {0,1},{1,0},{0,-1},{-1,0} };
	bool flag = false;
	int dx, dy;

	for (int i = 0; i < 4; i++) {

			dx = x + direction.at(i).at(0);
			dy = y + direction.at(i).at(1);

			if ((0 <= dx && dx <= N - 1) && (0 <= dy && dy <= N - 1) &&  /*NxN のマスを出ない*/
               (map.at(dx).at(dy) == '.') && (memo.at(dx).at(dy)==false) &&/*通路を判定、未開の地であることも確認*/ 
                (flag == false)){/*一度ゴールに辿り着いたら、他を探索しない:要補足確認*/
				memo.at(dx).at(dy) = true;
				flag = rec(dx, dy, N,map,memo);
			}

	}

	return flag;
}

/*
■補足
再帰的に未開の地を全探索するのが上記のコードの基本イメージです。
そのため、以下のようなケースはゴールを通過したとしても、未開の地であり
通行可能であれば、プログラムは探索を継続します。

探索終了地点が N-1, N-1 でなければ False を return するので、
False が返ってきてしまいます。

4
.#..
.#..
.#..
....

ゴールに辿り着いた時点で Flag に true を格納して
保持できればいい訳です。

言い換えると、Flag = false の時のみ探索すれば良いのです。
よって if 文の条件に (flag == false) が必要なわけです。
*/


int main() {
	int N;
	cin >> N;
	vector<string>buff(N);
	vector<vector<char>> map(N);
	vector<vector<bool>> memo(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++) {
		cin >> buff.at(i);
		for (int j = 0; j < N; j++) {
			map.at(i).push_back(buff.at(i).at(j));	
		}
	}

	if (rec(0,0,N,map,memo))
		cout << "Yes" << "\n";
	else
		cout << "No" << "\n";

	while (1) {};
	return 0;
}

相互再帰

複数の関数が互いに呼び合って再帰処理をする事を指すそうです。
まずは、コードを読み、学ぶ(まねぶ)ことから始めました。

is_even_odd.cpp
#include <iostream>
using namespace std;
bool even(int);
bool odd(int);

bool even(int n) {
	if (n == 0)
		return true;

	return odd(n - 1);
}

bool odd(int n) {
	if (n == 0)
		return false;

	return even(n - 1);
}

int main() {
	
	if (even(4))
		cout << "4 is even \n";
	else
		cout << "4 is odd\n";

	while (1) {};
	return 0;

}

一見、魔法のように見えたコードも
以下のように捉える事が出来ないだろうか。

■4を判定
even(4) => odd(3) => even(2) => odd(1) => even(0) => True

■3を判定
odd(3) => even(2) => odd(1) => even(0) => True

あれ？ 正解なら必ず even に戻るのでは？
不正解も試す。

■4を判定
odd(4) => even(3) => odd(2) => even(1) => odd(0) => false

■3を判定
even(3) => odd(2) => even(1) => odd(0) => false

これは n==0 の時に判定するのが味噌だと思いました。
これによりステップの回数が数値+1 になっているので
正しければ even , 間違っていれば odd にシフトするようになっています。

11日目:EX20-報告書の枚数

報告書の枚数を数え上げ。
愚直に再帰的に数えてみた。

cnt_report.cpp
#include <iostream>
#include <vector>
using namespace std;

int rec(vector<vector<int>>tree, int i,vector<int>*nums) {

	if (tree.at(i).empty())
		return 0;

	int buff = 0;
	int n;
	for (auto x : tree.at(i)) {
		n = rec(tree, x,nums) + 1;
		nums->at(x) += n;
		buff += n;
	}
	return buff;
}



int main() {

	int N;
	cin >> N;

	vector<int> pn(N);
	pn.at(0) = -1;
	for (int i = 1; i < N; i++)
		cin >> pn.at(i);

	vector<vector<int>> tree(N);
	for (int i = 1; i < N; i++)
		tree.at(pn.at(i)).push_back(i);

	vector<int> nums(N);
	rec(tree, 0, &nums);

	for (auto y : tree.at(0))
		nums.at(0) += nums.at(y);
	nums.at(0) += 1;

	for (int i = 0; i < N; i++)
		cout << nums.at(i) << "\n";

	return 0;

}

一応、AC ですが、このコードには不完全な個所があります。
それは赤丸から葉の領域までしか、再帰的に処理できない点です。
これを補うために main にて残りを足し合わせています。

無題.png

再検討

別解を検討しました。

step 1:葉に到達したら 1 をカウント。
step 2:節に戻ったら、葉の値を全て加算していく。
step 3:節からもレポートするので 1 インクリメント、return する。
※root まで、return , 加算を繰り返す。

report_cnt.cpp
#include <iostream>
#include <vector>
using namespace std;

int rec(vector<vector<int>>tree,int n,vector<int> *buff) {

	if (tree.at(n).empty()){
		buff->at(n) = 1;
		return 1;
	}

	int num = 0;
	for (auto x : tree.at(n)) {
		num += rec(tree, x,buff);
	}
	num += 1;
	buff->at(n) = num;
	return num;

}

int main() {
	
	int N;
	cin >> N;

	vector<int>p(N);
	p.at(0) = -1;

	vector<vector<int>>tree(N);

	for (int i = 1; i < N; i++){
		cin >> p.at(i);
		tree.at(p.at(i)).push_back(i);
	}

	vector<int> buff(N);
	rec(tree,0,&buff);

	for (int i = 0; i < N; i++)
		cout << buff.at(i) << "\n";

	while (1) {};// <= 動作確認用の記述。判定の際はコメントアウト。 TLE になってまう。
	return 0;

}

12日目:埋め立て

コチラ に挑戦してみました。
手垢バリバリのコードで申し訳ない。

今回は自分なりにチャレンジを盛り込みました。
それは、base case がない再帰処理の書き方。
base case は return ~~。

つまり、
base case に該当しない場合だけ再帰ステップに入れば
base case は要らないのでは？？

judge.cpp
#include <iostream>
#include <vector>
using namespace std;

/*
//base case あり
void rec(vector<vector<char>>map, vector<vector<bool>>& memo, int sy, int sx) {

	if (sx < 0 || sx > 9 || sy < 0 || sy > 9) return;
	if (map.at(sy).at(sx) == 'x') return;
	if (memo.at(sy).at(sx)) return;

	memo.at(sy).at(sx) = true;

	rec(map, memo, sy + 1, sx);
	rec(map, memo, sy - 1, sx);
	rec(map, memo, sy, sx + 1);
	rec(map, memo, sy, sx - 1);

}
*/

//base case なし
void rec(vector<vector<char>>map, vector<vector<bool>>& memo, int sy, int sx) {

	vector<vector<int>>direction{ {1,0},{-1,0},{0,1},{0,-1} };
	int dx, dy;

	for (int i = 0; i < 4; i++) {
		dy = sy + direction.at(i).at(0);
		dx = sx + direction.at(i).at(1);
		
		if ((0 <= dx && dx <= 9) && (0 <= dy && dy <= 9) && (map.at(dy).at(dx) == 'o') && (memo.at(dy).at(dx) == false)) {
			memo.at(dy).at(dx) = true;
			rec(map, memo, dy, dx);
		}

	}

}

void view(vector<vector<char>> map, vector<vector<bool>>memo) {
	cout << "\n";
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cout << map.at(i).at(j) << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cout << memo.at(i).at(j) << " ";
		}
		cout << "\n";
	}

}

int main() {

	vector<vector<char>> map(10, vector<char>(10));

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> map.at(i).at(j);
		}
	}

	int sx, sy;
	bool flag = false;

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map.at(i).at(j) == 'o') {
				sy = i;
				sx = j;
				flag = true;
				break;
			}
		}
		if (flag)
			break;
	}

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {

			vector<vector<bool>>memo(10, vector<bool>(10, false));
			bool ans_flag = true;

			if (map.at(i).at(j) == 'x') {
				map.at(i).at(j) = 'o';
				rec(map, memo, sy, sx);
                //view(map,memo);　// <= デバック用

				for (int k = 0; k < 10; k++) {
					for (int l = 0; l < 10; l++) {
						if (map.at(k).at(l) == 'o' && memo.at(k).at(l) == false)
							ans_flag = false;
					}
				}
				if (ans_flag) {
					cout << "YES\n";
					while (1) {}//<=動作検証用、判定する際はコメントアウト
					return 0;
				}
				map.at(i).at(j) = 'x';
			}

		}
	}

	cout << "NO" << "\n";

	while (1) {}//<=動作検証用、判定する際はコメントアウト
	return 0;
}

見事 AC で実験 成功!!おもろ～

13日目:深さ優先探索

問題文は コチラ。
入力のデータ数が今までと違い 500 とかになると
vector ではスピードが間に合わなくなる。
そこだけ気を付けてあげれば基本スタンスで問題は解ける。

search.cpp
#include <iostream>
#include <vector>
using namespace std;

int H, W;
char map[500][500];
bool memo[500][500];

void rec(int x, int y) {

	if (x < 0 || W <= x || y < 0 || H <= y)
		return;
	if (map[y][x] == '#')
		return;
	if (memo[y][x])
		return;

	memo[y][x] = true;

	rec(x + 1, y);
	rec(x - 1, y);
	rec(x, y + 1);
	rec(x, y - 1);

}

int main() {

	cin >> H >> W;

	int sx, sy;
	int gx, gy;
	for (int h = 0; h < H; h++) {
		for (int w = 0; w < W; w++) {
			cin >> map[h][w];
			if (map[h][w] == 's') {
				sy = h;
				sx = w;
			}
			if (map[h][w] == 'g') {
				gy = h;
				gx = w;
			}
		}
	}

	rec(sx, sy);

	if (memo[gy][gx])
		cout << "Yes";
	else
		cout << "No";

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

14日目:ARC061C-たくさんの数式

問題文はコチラ
処理としては複雑に見えるが
動作は基本形を流用して解けるようです。

丁寧に整理したかったので別記事で用意しました。

15日目:ABC079C-Train Ticket

無題.png
参考元はコチラ

コードを組み立てたときの方針

一応 AC になりました。コードはコチラ
以下のように + , - を組み合わせて全探索します。
その結果、7 になるのであれば、式として表示。
無題2.png
一点、注意点としては、答えが複数あるケースです。
output が 1 つになるようにケアしないと複数 output によりコケます。

もっとシンプルに書きたい!!

余計な if 文は取っ払い、
全探索の結果は全て vector に格納します。
あとは vector の先頭に格納された string を引っ張れば OK

dfs.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string s,ans;
vector<string> space;
int sum = 0;

void rec(int sum,int n,string ans,vector<string>&space) {

	if (ans.size() == 6) {
		if(sum == 7){
			space.push_back(s[0] + ans + "=7");
			return;
		}
		return;
	}
	
    rec(sum + (s[n+1]-'0'), n + 1, ans + "+" + s[n + 1],space);
	rec(sum - (s[n+1]-'0'), n + 1, ans + "-" + s[n + 1],space);

}


int main() {

	cin >> s;
	rec(s[0]-'0', 0,"",space);
	cout << space.at(0);
	//while (1) {};
	return 0;

}

有識者の回答も眺めてみました、おもろいですね～
・素直に条件分け => 〇
・dfs の解法 => 〇

16日目: All Green

無題.png
無題.png
参考元はコチラ

どうやってアプローチすべきかはボンヤリあるが、コードに落とせない。
ガッツリ回答を調べて、ココに辿り着きました。

問題に必要なアプローチ

問題の意図として Pi の得点は i = D のとき、100*D を Pd 個解くので、最も得点が高い
これでも総合得点が G 以上とならないのであれば、上記に加算する形で i = D-1 を試す。
それでもダメであれば D-2, D-3 , D-4..... 1 と試す。
以下のコードはそれが出来ている。

dfs.cpp
#include <iostream>
#include <vector>
using namespace std;
int D, G;
int cnt = 0;
int ans = 1000000;

void dfs(vector<int>p,vector<int>c,int idx,int sum,int cnt, int &ans,int index) {

	if (idx == D) {
		if (sum < G) {
			for (int i = 0; i < p[index]; i++) {
				sum += (index+1) * 100;
				cnt++;
				if (sum >= G)break;
			}
		}
		if (sum >= G) ans = min(ans, cnt);
		return;
	}

	dfs(p,c,idx + 1, sum,cnt,ans,idx);
	dfs(p,c,idx + 1, sum + (idx+1) * 100 * p[idx] + c[idx], cnt+p[idx], ans, index);

}


int main() {

	cin >> D >> G;
	vector<int> p(D);
	vector<int> c(D);

	for (int i = 0; i < D; i++) {
		cin >> p[i] >> c[i];
	}

	dfs(p,c,0,0,cnt,ans,-1);
	cout << ans;

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

}

一番簡単な入力例で試してみました。
case1.png
まだ "問題に必要なアプローチ" を体現できているとは言えない。
入力例を以下に変えて検証してみる

5 25000
20 1000
40 1000
50 1000
30 1000
1 1000

無題.png
競プロの時間制限というプレッシャーの中で
サクッと、こんなコード書くなんて天才過ぎる ort

17日目:ARC029 A - 高橋君とお肉

無題1.png
無題2.png
原文はコチラ

アプローチ

まずは、何を取って何を取らないかを全探索してみようと思いました。
イメージは以下です。取る・取らない が 4 桁あるので 2^4 = 16 通り。
無題.png
次に、足さなかったお肉も別で集約して、
足したお肉と比較できれば良いのではないでしょうか？

以上から、ベーシックな構成を少しいじるだけで
AC が獲得できます。

dfs.cpp
#include <iostream>
#include <vector>
using namespace std;
int N;
int ans = 100000000;
int sum = 0;
int res = 0;

void rec(int idx,int sum, int res, int &ans,vector<int>&t) {
	if (idx == N) {
		//cout << sum << " " << res << "\n";
		ans = min(ans, max(sum, res));
		return;
	}
	rec(idx + 1, sum, res+t[idx], ans, t);
	rec(idx + 1, sum + t[idx], res, ans,t);
}


int main() {
	cin >> N;
	vector<int> t(N);
	for (int i = 0; i < N; i++) {
		cin >> t[i];
	}
	rec(0,sum,res,ans,t);
	cout << ans << "\n";
	while (1) {};
	return 0;

}

15日目:ABC002 D-派閥

無題.png
原文はコチラ

有識者の回答を考察

コチラを参考にさせて頂きます。

2
1
2

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
Sign upLogin
2
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?