# 蟻本輪読会 第二回
date: 6/16
author: kyawa
content: 2-3, 2-4 (3-4の一部を含む)

---
## トピック

### 2-3
#### ・DP一般に用いられる考え方
#### ・貯金箱テク
#### ・余談/耳DPについて

### 2-4
#### ・二分木/多分木と分割統治
#### ・平衡二分木の細かな話題
#### ・優先度付きキューの細かな話題
#### ・Union Findの細かな話題

### 発展的なトピック
#### ・2-3の発展 行列累乗 (ホットトピック!)
#### ・2-4の発展 Cartesian Tree (前回のヒストグラム内最大長方形と関連)
---

## 2-3
### DP一般に用いられる考え方
・もとの問題を部分問題にもつ問題の集合を考える
・bool型を持つようなDPは整数型を持つDPとして改良できる場合が多いほか、遷移をbitsetで表せることが多い。bitsetによる高速化、結構好きなトピックだが言語の問題もありコンテストにはほとんどでない。
・次元を追加して立式することがよくある(分割数の例題をみよ)
・計算の順序はDAGとして解釈できる。逆に、DAG上のDPとして捉えることで実装が容易になる。詳しい内容は2-5にゆずる。

>ミニ問題. グリッドグラフであって、左から右へ、上から下へ向き付けられているものはDAGであることを示してください。
<details>
<summary>
略解
</summary>
自明なトポロジカル順序を具体的に与えてやればよい。(完)
</details>

### 貯金箱テク
<a target="_blank" href="https://yukicoder.me/problems/no/42">yukicoder No.42 貯金箱の溜息</a>
<details>
<summary>
上の問題のネタバレがあります
</summary>
<br>
ナップザック問題などで「どの商品もいくつでも選べる」から「商品ごとに高々1つだけ選べる」に帰着させるテクニック。<br>
無限個の商品を1個セット、2個セット、4個セット、8個セット、16個セット...　と分割して考えると、<br>
無限個の商品の中から13個選ぶのは1個セット、4個セット、8個セットを1つだけ選ぶことに帰着できる。
</details>

### 余談/耳DPについて
<a target="_blank" href="https://atcoder.jp/contests/abc211/tasks/abc211_c">ABC211C</a>
↑これとかが耳DPと呼ばれる。

操作の状態/段階をもつDPらしいが、元となった問題「<a target="_blank" href="https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d">Ears</a>」がそんなに特殊でもないDPで解けるので、謎。DPに段階を持たせるという発想が当時は画期的だったのかもしれない。言葉の定義もあまり明確でない。よくわかんないね

## 2-4

実装や計算量の証明については深く踏み込みません。
Union Findの計算量が証明できなくても橙になれる(SPDさん曰く)

### 二分木/多分木と分割統治
・二分木や多分木の形をしているデータ構造、分割統治と対応することがよくある。例えば、Cartesian Treeと呼ばれる二分木(後述する)や重心分解により得られる多分木など。

### 平衡二木探索木の細かな話題
・基本的にstd::setや座圧+セグ木で対応できる。
・ICPCで実装することはまずない...と思う
・std::set は logがやや重い。
・平衡二分探索木の入門はAOJのALDSがおすすめ。

### 優先度付きキューの細かな話題
・logが平衡二分木の次くらいに重い気がする。気がするだけかも
・特に重みが均一なグラフ(グリッドなど)ではdijkstra法ではなくbfsを用いた方がよい
・多点開始のdijkstra法と捉えると見通しが良くなる例 <a target="_blank" href="https://atcoder.jp/contests/abc298/tasks/abc298_f">ABC298F</a> <a target="_blank" href="https://atcoder.jp/contests/abc305/tasks/abc305_e">ABC305E</a>

### Union Findの細かな話題

<a target="_blank" href="https://noshi91.hatenablog.com/entry/2018/05/30/191943#fn-df94b2bd
">・データ構造としての知見の諸々(すごい)</a>
・ICPCでは対数時間のものの実装でも良さそう。おすすめはsizeの記録によるマージテク。
・往々にして「逆から考える典型」と相性がいい。<a target="_blank" href="https://atcoder.jp/contests/abc120/tasks/abc120_d">ABC120D</a>
・超頂点を用いることがたまによくある。<a target="_blank" href="https://atcoder.jp/contests/abc264/tasks/abc264_e">ABC264E</a> <a target="_blank" href="https://atcoder.jp/contests/abc302/tasks/abc302_f">ABC302F</a>

---
## 発展的なトピック
### 2-3の発展 行列累乗 (ホットトピック!)
・直近のABC-G(<a target="_blank" href="https://atcoder.jp/contests/abc305/tasks/abc305_g">ABC305G</a>)で出ている。
・隣接行列から理解するのがよい。 <a target="_blank" href="https://atcoder.jp/contests/dp/tasks/dp_r">EDPC-R</a>
・行列の演算としてのる構造は積と和をもつものとは限らない。 <a target="_blank" href="https://atcoder.jp/contests/abc009/tasks/abc009_4">ABC009D</a>
上の構造は一般に半環とよばれる。 <a target="_blank" href="https://qiita.com/lotz/items/094bffd77b24e37bf20e">参考資料</a>

### 2-4の発展 Cartesian Tree (前回のヒストグラム内最大長方形と関連)

・列を最小値によって分割統治する構造を二分木として取り出したもの。ヒープ構造の一種
・根は与えられた列の最小値である。その位置より左の要素と右の要素に分割して、再帰的に構築される。図示した方が早いと思うので、します。
・実は線形で実装できる(Monotone Stack) → <a target="_blank" href="https://judge.yosupo.jp/submission/145064">実装例</a>
・ある位置より右にあって、その値より大きいもののうち、最も右側にあるもの(左に置き換えても同様)を線形時間で求められるため、ヒストグラム内最大長方形の線形時間解法を容易に記述できる。
・最小値ごとに主客転倒する問題が解ける。 <a target="_blank" href="https://atcoder.jp/contests/abc282/tasks/abc282_h">ABC282H</a>