# 蟻本第一回発表メモ
できるだけ自分の言葉で書いたので伝わりにくかったら申し訳ないです。

## 全探索

### 再帰関数

個人的な再帰関数使いたい時
・期待値のメモ化再帰とか、更新順序めんどくさいとき
・forループの回数が決まってないとき
・構築していく系（アルファベット順とか）
長さ１０のアルファベット列を辞書順に並べよとか

### スタック
個人的にはdfsの非再帰化とかでよく意識してつかう。

**括弧列**
((()))(())()()

かっこ列整合性とれてるかどうか

**ヒストグラム中の最大の長方形の面積**

累積minだとO(nlogN)
sparcetable???
seg木だとlogもう一個付く

左から高さを見てく。stackに長方形が作れる高さを格納していく。

* stackの一番目の高さが今の高さより低い時、stackに今の高さを追加
* stackの一番目の高さより今の高さが低いとき、今の高さ以上である限り、popして、面積を計算して現在の最大を更新する。

**Monotonic Stack**
というものがあるらしい。蟻本でそのうちでてくるらしい。

上のやつもこれ説。
[1,3,4,5]
２を入れたい。
3,4,5を消す
[1]
[1,2]
単調性を保つ。

**dequeの実装はstack二個**

**momoyuuさんの話**
モノイド
区間演算でO(1)
スワッグ

https://motsu-xe.hatenablog.com/entry/2019/12/06/192424

スライド最小値

dp
1,2,3,4,5,6,7

5の更新に1,2,3のminとか使う時に、セグ木だとlogつく。スライド最小値

### キュー

後退解析

* dfs-stack
* bfs-queue
* bfs-deque
* dijkstra-p-que

### 深さ優先探索
部分和問題をdfsで解くと$2^n$
Lake Counting(POJ No.2386)
よくあるやつ。連結してるグループの個数

### 幅優先
あんまり意識してなかったこと
* 幅優先探索だとキューに状態入れてくので、状態数に比例するメモリ
* 深さ優先だと再帰の深さ
* 個人的に状態遷移するやつがちょい苦手

### 特殊な状況の列挙
適当におもいつくやつはこんくらい
* bit全探索
* 順列全探索

### 枝狩り
個人的に見逃しがち

最近だと[これ](https://atcoder.jp/contests/abc300/tasks/abc300_d)とか？僕は数学的に場合を絞ってごり押してしまった。。。
しかし、枝狩りで間に合うことを確信するには結局数学なりで検証しなきゃなきがする。

### コラム
* 静的領域
* スタック領域
* ヒープ領域

再帰関数だとスタック領域にローカル変数とか格納されるけど、すぐ埋まっちゃうから気をつけようね。ってことでよい？

vectorはヒープ領域
静的配列よりvectorは遅い
vectorはpushbackがおそい毎回すると終わる

## 貪欲法

### 硬貨
貪欲代表例
倍数じゃないと貪欲むり
ふろべにうす

### 区間

* **重複なし区間スケジューリング問題**
ふつうの区間スケジューリング問題。

**解法**
終了時刻でソートして貪欲に。
証明
> 補題
> 任意の選び方opt集合の元に対して、i番目の仕事を終了した時間$optf_i$が貪欲の結果の$greedyf_i$以上であることを帰納法で示す。

背理法で貪欲が最適だと示す。

前回のex

[これも](https://atcoder.jp/contests/abc225/tasks/abc225_e)

* **重複あり区間スケジューリング問題**
重複がK以下になるように仕事を選ぶ場合，選ぶ仕事の最大化

**解法**
k個のスロットを考えて、それぞれの終了時間を管理する。

まず、終了時間で仕事をソート。終了時間が早いものから仕事をスロットに振っていく。いま、ある仕事が$t=s$に開始するとき、$i,j$の二つのスロットが$t=s$で仕事がないとする。このとき、スロットで最後に仕事を終了する時刻の大小が$endtime_i < endtime_j$とすると、jに仕事を振るのが最適である。これは、終了時刻がより後でスタート時刻がより前の仕事が存在したときに、今iに振ってしまうと、iに振れれた仕事が振れなくなってしまうことからわかる。（と思う）

pythonだとセグ木上の二分探索。

* **重み付き区間スケジューリング問題**
重複なしで、仕事には重みが与えられている。重みを最大化する

**解法**
dp
$dp[i] = (区間iまでの最適)$

**更新の式**
$dp[i] = max(dp[i-1],dp[j(終了が区間iのスタートより前の区間)]+w_i)$

**例題**
http://web-ext.u-aizu.ac.jp/circles/acpc/commentary/ACPC2016Day2/C.pdf


* **重複あり重み付き区間スケジューリング問題**

のちのち蟻本ででてくるっぽいので割愛

**ところで**
重複なし、重み付きで、これを思い出した。
> 競技プログラミング部 AntsではK分間のコンテストが開催される予定です。問題はN問あり、1からNまで番号が付けられています。
コンテスト開始からt分後に問題żに正解した場合、 $max(a_i-t\times b_i, 0)$点を得ることができます。
部員のmomoyuu君はコンテスト開始前に超能力により、コンテスト中に連続したt分を使うことで問題iに正解できることが分かりました。
（略）
問題に正解後、 次の問題を解き始めるまでの時間は考えないものとします。全ての問題に正解する必要はなく、 また問題を好きな順番で解くことができるとき、momoyuu君は最大で何点取ることができますか。 一度正解した問題を再び解くことはできないものとします。

ただ別に問題がいつ解くか決定されていないのであんまり関連なさそう。いつ解くかの代わりとして、優先度が定まる。

### 辞書順最小

個人的には構成してくイメージが強くて、前の章の再帰関数っぽいイメージがつよい。

[これとか](https://atcoder.jp/contests/arc160/tasks/arc160_a)
### その他

**Fence Repair**
いろいろ関連する話題がありそうな問題

この問題を、並び替えできないとしたとき、どの順番で切るべきかは
> 行列連鎖積問題
> 行列を乗算するとき、使用される乗算の総数が最小になる乗算の順序を見つける問題。

に帰着される。

(n,m)(m,l)
の行列積は
$A_{ij}=\sum{a_{ik}\times b_{kj}}$
から、$n\times m \times l$回の計算

行列の積は非可換だが、結合則が成り立つので、順序を保ったままどこを先に計算するかは自由。しかし、その計算の順序によって乗算の総数が異なってくる。それを最小化したい。

**解法**
メモ化再帰とかDP

$dp[i][j]=i番目からj番目の行列までの積の最小コスト$

**更新の式**
$(i番目の行数＝$h_i$,k番目の列数は$w_k$,j番目の列数は$w_j$)$

$dp[i][j] = min_{i\leq k\leq j}(dp[i][k]+dp[k+1][j]+h_iw_kw_j$)

j-i=lとしてlで回せばいい感じに更新できる。

$O(N^3)$

**一般化**
この問題を一般化すると、ある集合Xの元からなる列があったときに、全体をXで定義される結合法則のある二項演算で計算するとき、コストを最小にしたい。

**文字列の連結**
m文字の文字列とn文字の文字列を連結する場合、コストは$O(m+n)$。n個の文字列の長さが$a_i$で与えられるとき、すべてを順序を保ったまま、（時間的な）順番は関係なく結合するとき、コストを最小化したい。

これって**実質Fence Repairの順序固定ver**

https://atcoder.jp/contests/abc289/tasks/abc289_g

//追加
コスト関数にもんじゅ性があると$O(N^2)$
に落とせる。これはそれがある。

https://www.spoj.com/problems/BRKSTRNG/

### ハフマン符合
さいころとか振ったときに、１の状態が起きる確率とか、３の状態が起きる確率とかを生起確率という。
生起確率が低いものに長いbitを割り当てて、高いものに短いbitを割り当てる。すると、さいころをn回振ったときに何回目に何が出たかを示すbit列長の期待値は小さくなる。

送られるbit長の平均（＝平均符号長）を短くしたいという情報通信上で重要な概念。

twitterの誰かが問題っぽくしてたので引用。これはまさにfencerepairと同じ問題。
> 問題 : 正整数 w_1, w_2,.. w_n が与えられる。これらを2分木の葉に割り当てる。w_i が割り当てられた葉の深さを d_i としたとき、Σw_id_i を最小化するような木と配置を求めよ。

**解法**
> 補題:与えられた情報源に対し、以下の２つの条件を満たし、かつ平均符号長が最短の符号が存在する

> （１）確率が最も小さな2つは、木の中で深さ最大である
> 説明：深さが最大ではない、ほかの葉と、入れ替えたときに、シグマがでかくなることを言えばよい
> （２）確率が最も小さな2つは同じ節点から出ている2つの葉に割り当てられる
>説明：（１）より、深さ最大。どちらも同じ深さなので、スワップしてもシグマ不変。よって構成可能。
>

今、ｎ＋１個の葉があるとき、上の２つをみたす最適な木（シグマ＝Ｓ）とする。重さが最も小さな2つを削除して、親の頂点を重さが、その重さの和に等しい頂点で置き換えると、葉がｎ個になる。（シグマ＝Ｔ’）このｎ個の葉の重さで、ハフマン符号木を構成する。（シグマ＝Ｔ）これは仮定より、シグマを最小化する。先ほどの葉を再び二つに戻す。（シグマ＝Ｓ’）
このとき、Ｓは最適、Ｔは最適だから
* S-S'<=0
* T-T'<=0

が成り立つ。また、S-T'=wi+wj,S'-T=wi+wjと合わせて、S=S'.

以上から、縮退したn個の葉で、ハフマン符号木を作れば題意を満たすことが得られた。つまり、これを繰り返せば、最適な木が得られる。

**イメージ**
* 重さが最も小さな2つを削除して、親の頂点を重さが、2つの葉の重さの和に等しい頂点で置き換える
* 上を、頂点数１になるまで繰り返した後、展開する。

[これの証明](https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/InformationTheory-2005-Slide-06.pdf)をアレンジしました