# :strawberry: Learning Algorithm ~~第3--5回~~ 5 章 :strawberry:

## ファシリ
- 前川 (7/5)
- 山田 (7/12)
- 前川 (7/19)

もくもくしてるのでファシリはあんまりなくなりつつある。あと meet でやるのが主になりそう。もくもくスタイルだとあんまり困らなさそう

## 日程
- ~~6/28~~ → ~~6/30~~ → 7/5 & 7/12 & 7/26---

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

最近はタイムテーブルがあんまりなくて、各々もくもくやって適宜相談するみたいな感じになっている

やることに困ったら確認する用↓

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

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

## メモ
- $1+1/2+1/3+\dots+1/n = O(\log(n))$ みたいなのの件を話すのを忘れてたのを思い出しました。これを利用して計算量改善（・計算量解析）をする話題が出てくるまで後回しでもいい気はしますが、忘れそうなのでメモ / えびちゃん :dog2: :whale:
- 互除法の計算量が $O(\log(n))$ になる話。時間余れば :whale:
- 「こういうことをすれば $n$ から $\log(n)$ に落とせるからうれしい」というのを知っていると計算量を落とすのをやりやすくなるが、そういうのはもっと先でやるべきかも？ となった
- それより、メモ化で計算量が落ちている部分の解析の話をするべきだった？ いや、みんな既にわかっているのかも
- 数列とか漸化式とか高校で出てきた話に関して、無理に思い出したりしようとする必要はない気がします
- $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ とかみたいな公式とかを思い出したり覚えたりする必要はあんまりなくて、$\sum$ の記法の意味（要するに for して sum）をわかっていることと、「$\sum_{i=1}^n i^2$ とかは簡単に計算できる式になったはず、必要になったらググる」くらいの認識があれば十分そう。[こんなサイト](https://www.wolframalpha.com/input?i=sum+i%5E2%2C+i%3D1+to+n) もあるし
- 競プロで使いたくなる部分と高校数学でやった部分がちょっと違ったりもするので、忘れていることを負い目に感じたり身構えたりする必要はない気がしてます（新しく学べばおっけーなので）:dog2:

- DP をするときは以下のようなことを意識しているはず。
- 定義からすぐ計算できることはなにか？
- 大きい問題を解くときに「これさえわかってたらな〜」となる問題はなにか？
- その問題を辿っていけば前者にまで持っていけるか？
- あるいは、「この問題が解ければ、もう少し大きい問題も直ちに解ける」という方向に更新することもある。
- 人にもよるけど、こっちの方が楽だったりするかも
- 逆算して「商品を追加しなかったということは、ここを引いて...」とするより、「商品を追加する」の方が考えやすい
- 再帰とか immutable っぽくとかやるなら、逆算する方（解くべき小さい問題は？）の方が相性がいいがち

- 基本的にえびちゃんに問題がありそうだけど、たくさん書いていると量がかさんできて見にくくなっちゃうかも

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

## 第5章 設計技法(3)：動的計画法

### 目安の時間
60分

### 感想・気づき

#### 5.5 編集距離問題
- > 最初に，以下の２つの操作が等価であることに着目します．Sの好きな箇所に好きな文字を１文字挿入するTの文字を１つ選んで削除するよって「Sの好きな箇所に好きな文字を１文字挿入する」という挿入操作は「Tの文字を１つ選んで削除する」という操作に置き換えて考えることができます．
- :tensai: の発想なので自分で発想できる気がしない / まつもと :whale:
- 最初はみんなそうだと思う（こなみ）
- 「片方を immutable にできないか？（今回の元問題はこっちの形）」とか、「同じ操作の形で書けないか？（削除の操作）」とかを意識して疑ってみると、操作の言い換えがしやすくなるかもしれません？ あと長さとかが減る向きの操作の方が、考えることが少なくなってうれしいがちかも
- Knuth 大先生も言ってた気がするのを思い出したんですが、紙とペンを使いつつ愚直に解いてみるのが重要そうです。「ここの計算さっきもしたじゃん。何回もやり直すの無駄だな」という気づきを得やすいです（その際、雰囲気や見た目でなんとなく計算しないように意識する。雰囲気ベースのものは実装できないので）

### 疑問・わからなかったこと
- 全体的に「わかったようで何もわからない」 / まつもと :cat2:
- :sorena: of :sorena:
- 編集距離とか LCS (Longest Common Subsequence) とか、DP で解ける有名問題ではあるものの、最初に見せられると「なんで思いつくの？」感が強くてしんどそう
- それこそ章末にある [EDPC C](https://atcoder.jp/contests/dp/tasks/dp_c) とかの方がとっつきやすさはありそう（かも？）
- 肝としては、「長さ $n$ に対するこの問題の答えは？」といきなり言われてつらい場合でも、「長さ $n-1$ に対する答えはこれだよ〜」と教えてもらった場合は解けるか？みたいなことを考えるのが DP っぽさあります（それで解けない場合は、「それに加えてどんな情報があれば解けるか？」とかを考える）

#### 5.3.1 緩和
- > 一般に，グラフ上で頂点uから頂点vへと遷移する辺があって，その遷移のコストをcと表したときに， ~(中略)~ とする処理を，その辺に関する緩和（relaxation）といいます．

- なんで`relaxation`なのかがピンときてないです / まつもと
- :sorena: 競プロ界隈で relax(ation) と呼ぶ人はあんまりいない印象があります（最適化界隈・学術界隈の用語？）/ えびちゃん
- 最適化の制約（これこれの条件を満たした上で最適化する必要がある）の文脈で、制約を緩めることを緩和と言ったりするのですが、いろいろ踏まえるとそれと似た感じの概念になったりするのかも？ あんまりわかってないです / えびちゃん
- や、シンプルに、「この辺だけが通れるよ〜」という制約があり、「この辺も使っていいよ〜」というので制約が緩くなっているから、緩和ということか？ / えびちゃん
- んーなんか 14 章に説明があるけど、いまいち「緩和」の説明づけとしてはぴんと来ないな / えびちゃん
- あーもともと張られてたひもがゆるっとなるからって言いたいのかなあ。いまいちしっくり来ないけど / えびちゃん
- ところで`chmin`だとわかりづらいから`choose_minimum`にしたいけど、競プロ界隈では少しでもタイピング数を減らすため？に関数名・変数名を省略しがちなんでしょうか / まつもと
- chmin・chmax は（最小値・最大値を min・max と略したりするのと同じくらい、競プロ界隈では）浸透した単語ではあります。長い名前を採用したいなら choose 以外の動詞（update 感が欲しい）にしたい感はありますが... / えびちゃん
- 省略しがちなのあります。（C++ には最小値・最大値を得る関数 `min`・`max` があり、それと変数名が衝突するのを嫌って）`mi` `ma` などと命名する人たちがそこそこいますが、合わなければ無視していい風潮だと思います。えびちゃんは無視してます / えびちゃん
- コンテスト期間（せいぜい数時間程度。正解すればもう不要）さえ保守できればいい状況が多いので、変数名を長くするメリットがあまりないと思う人もいます。そのせいで数十分前のコードを勘違いする人もいる（愚か）ので、適度な長さにするのがよさそう / えびちゃん

#### 5.5 節 :: 図 5.12の下あたり

- > このアルゴリズムの計算量はO(|S||T|)となります．
- 絶対値なのなんでだろう / まつもと :cat2:
- わ、たしかに記載がないかも。$|S|$ で文字列 $S$ の長さを表します（集合 $S$ に対しては $|S|$ で要素数を表す）
- お気持ちについて触れておくと、$|\bullet|$ で $\bullet$ の大きさとか長さみたいなのを表す感覚があって、実数の絶対値についても、原点からの距離（$-3$ と $0$ の距離は $3$ とか）という気持ちです

#### 5.5 節 :: 図 5.13

- よくわからなくて、この図はどう解釈すればよいのでしょうか / えびちゃん :dog2:

### [任意]章末問題の回答
- 前川:whale:
- (WIP) https://github.com/tomokikun/ands/pull/3
- 山田
- (WIP)https://github.com/YamadaKyohei/kenchon-book/pull/1
- えびちゃん :cat2:
- https://github.com/rsk0315/learn_algo/pull/3
- 解きました〜！

## 章末問題

### 解き方の方針

計算量がやばめでも、「`dp[i][j][k]` みたいにすれば解けるのにな〜」となったら、一旦それを書いてみるのもありかも

#### 5.3（作れる和の種類数を求めるやつ）

$\newcommand\DP{\mathrm{dp}}$

$\DP[i][j] :=$ 先頭 $i$ 個使って $j$ を作れる？

↑これを考えたい

で、自明なパターンは？（どう初期化するか？）

$\top$: true, $\bot$: false
$\DP[0][0] \gets \top$
$\DP[0][j] \gets \bot$ ($0 < j \le W$)

$\DP[i + 1][j] = \DP[i][j] \vee \DP[i][j - a_i]$ みたいなのを、$j$ の範囲がいい感じのときにやる

$|\{0<j\le W\mid\DP[N][j] = \top\}|$ が答え。

実質 5.2 で、答えが何になるかだけが違うみたいな感じ

#### 5.4（サイズ $k$ 以下の部分和で $W$ を作れるか？）

##### わかっていること

- $0$ 個から $0$ をつくるのは、$0$ 個選ぶことで可能
- $0$ 個から $j$ ($j > 0$) をつくるのは無理
- $1$ 個から $0$ をつくるのは、$0$ 個選ぶことで可能
- $1$ 個から $1$ をつくる？ → 入力によるねえ
- $1$ 個から $j$ ($0 < j < a_0$) をつくる？
- むりですね
- $1$ 個から $a_0$ をつくる？
- できるねえ
- $1$ 個でできますね笑
- $1$ 個から $j$ ($j > a_0$) をつくる？
- むりですね

---

「$i$ 個から $j$ を作るのは、$x$ 個選ぶことで可能」とわかっているとしましょう〜
→ $a_i$ を使うと？

:memo: $a_i$ を選んだときの和は $\underbrace{j + a_i}_{x+1\text{ 個選んだ}}$、選ばなかったときの和は $\underbrace{j}_{x\text{ 個選んだ}}$。

$\DP[i][j] = x$ ← こうすればどうか？

$\DP[i][j] :=$ $i$ 個見て、

$\newcommand{\xgets}[1]{\xleftarrow{#1}}$

$\DP[i][j] \xgets{\min} x$ を $\DP[i][j] \gets \min\{\DP[i][j], x\}$ の意味で使うことにします。要するに `chmin(dp[i][j], x)`。

- $\DP[i+1][j] \xgets{\min} \DP[i][j]$
- $\DP[i+1][j] \xgets{\min} \DP[i][j-a_i]$

$\DP[i+1][j] = \min\{\DP[i][j], \DP[i][j-a_i]\}$ とも書けそう〜