# :tangerine: Learning Algorithm 第2回 :tangerine:

## ファシリ
- 山田

## 日程
- 2022/06/21 19:00 -- 20:30+

| 時間 | 所要時間 | 内容 |備考 |
| -------- | -------- | -------- | -------- |
| 19:00- | - | 集合 | |
| 19:00-19:10 | 10分 | 感想記入&HackMDに書かれた感想・気づき・疑問でもっと掘り下げたいものに :+1: 付ける | |
| 19:15-20:25 | 70分 | 本の章ごとに:+1:が多いものからディスカッション（ここでも適宜HackMDに気づきとか書いてOK） | |
|20:25-20:30 | 5分 | 次回開催日と読む範囲決めてクローズ | |

全員が :+1:（同じ絵文字）をつけると、すでに自分がつけたのか他の人がつけたのかわかんなくなったりしそう（しないかも）/ えびちゃん

やることに困ったら見る↓

- :+1: が多いのを眺める
- わからない箇所とかは書いていそうなので、本を読むのはいらなさそう
- コードを読む
- メモを読む？

## 範囲
- 4章
- [回答例](https://github.com/drken1215/book_algorithm_solution/blob/master/solutions/chap04.md)

## メモ

- $1+1/2+1/3+\dots+1/n = O(\log(n))$ みたいなのの件を話すのを忘れてたのを思い出しました。これを利用して計算量改善（・計算量解析）をする話題が出てくるまで後回しでもいい気はしますが、忘れそうなのでメモ / えびちゃん :strawberry:
- 章末 6.7 に ★5 の問題が出てきたが、まだ本で出ていないデータ構造を使わないと指定された計算量を達成できなくて、ずるい。取り組むの自体はいいかもだけど、そういう出題のされ方だと認識しておいた方がよさそう / えびちゃん
- まえがきのあたりに ★ に関する話あったね
- あ！ 先出しで言っておくのですが、C++ では識別子（変数や関数、マクロなど）として `_` で始まるものは宣言しないでください（コンパイラとか用に予約されているので）（本当は `_` 始まりでも使えるものもあるけど、あれこれ覚えるメリットもなさそうなので特に触れません。コンパイルエラーになったりならなかったりするので厄介）/ えびちゃん

- 難かしげな問題多めですが、分野別になってて復習に良さげかも。https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F :eyes::strawberry:
- 「復習でこれ解いたよー」みたいなのを各自紹介してレビューするコーナーみたいなのを設けてもよさそうですね / えびちゃん
- 上級者は Topcoder Div. 1 easy やれと書かれていたので、やってみようかなという気持ちになってきました

- 「$a_i-a_j$ の差のうち、最大のもの（章末問題 3.4）ではなく、2 番目に大きいものを $O(n)$ で求めてね」というのはどうでしょうか / えびちゃん
- 「○○を示してください」と言われて、どうすれば示したことになるのかわからないという人もいるのではないでしょうか / えびちゃん

- `:cat2:` のねこちゃん (:cat2:) かわいい :+1: :strawberry:

- 章末 4.3、自力でそれを導く必要はなくて、帰納法回し学だったじゃん（おてての運動をしてもらうのもよかったかも）
- あと 4.3 を既知とすれば 4.4 の話は大事な気がするので、時間があったら話すのもいいかも

-------------------------------------

## 第4章 設計技法(2): 再帰と分割統治法

### 目安の時間
60分

### 感想・気づき
- 章末問題4-5
- 最初753数の意味がわからなかったのでググった（AtCoderの問題を見て意味がわかった） / まつもと

- 文系的には部分和問題を全探索で解くより再帰で解く方が5trillion倍わかりやすい / まつもと
- アメリカ英語とイギリス英語で値が変わるやつだ！
- 再帰でも全探索自体はしてたりしそう？ ビット全探索でがちゃがちゃやるのは、理系でも慣れないうちはわかりにくかったりしそう
- 高校数学で出てくる二項係数の↓これになんか似てるような...関係ないか...
- ${}_n C_r = {}_{n-1} C_{r-1} + {}_{n-1} C_r$
- https://integraldx.info/combination-formula-922
- :+1: 関係なくなさそう（[FYI] ${}_{n-1} C_r$ は `{}_{n-1} C_r` とか書くのがよさそう）

### 疑問・わからなかったこと
- 4.2 わかってない / まつもと
> なお、ユークリッドの互除法の計算量は $m >= n > 0$ として、 $O(\log n)$ となります :cat2:
- [FYI] `\ge` → “$\ge$” (*g*reater than or *e*qual to)。`\log` って書いててえらすぎ
- まともに説明されてないのでわからなくても当然ぽい。説明してくれと言われればできます

- 章末問題パッと読んだだけじゃ`int`で足りるのか`long long`にせんとあかんのかがわからないので回答見てびっくりする / まつもと :cat2: :tangerine:
- たしかに最初はむずかしい。答え（や計算途中の値）がどのくらい大きくなるか？とかを考える必要がある
- $10^9$ くらいに収まるか？ → `int`
- $10^{18}$ くらいに収まるか？ → `long long`
- 収まらない → 別の解法を考える（or 多倍長整数を使う？）（「`double` を使う」は基本的に悪手）

### [任意]章末問題の回答
- 前川 (tomokikun)
- https://github.com/tomokikun/ands/pull/2
- 4.5全然再帰的に解けなかった
- `oj t` 便利 :cat2:
- :tangerine: 山田 (YamadaKyohei)
- https://hackmd.io/cNN7Ki9ZTb270dbLJfNdBw#4%E7%AB%A0
- 🐱 :cat: :cat2: えびちゃん (rsk0315)
- https://github.com/rsk0315/learn_algo
- 4.6 まで解いちゃってたので、次回分から PR 形式にします :innocent:（章ごとじゃなくて問題ごとに作る感じにしようかな）
- 前回ぶんの補足説明（max-min でいいというのに気づくまでのパート） https://github.com/rsk0315/learn_algo/issues/1#issuecomment-1158602279