## 半分全列挙
半分全列挙とは、いくつかのパーツを半分ずつのグループに分け、全探索（全列挙）を高速化するテクニックのことを指します。

$O(N^m)$は間に合わないが$O(N^{m/2})$は間に合うときの解法
2グループに分けて全列挙をして、1つのグループは全探索し、もう一方のグループに関しては二分探索などで高速に処理する(
この場合のオーダーは$O(N^{m/2}\log N^{m/2})$)

レベルがあがってくると使う機会が増えるそうです

### -参考
個人的に面白い問題。
[e8さんの記事](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#9-15-%E3%83%91%E3%82%BA%E3%83%AB%E3%81%A7%E5%BD%B9%E7%AB%8B%E3%81%A4%E5%8D%8A%E5%88%86%E5%85%A8%E5%88%97%E6%8C%99%E3%81%A8%E6%9E%9D%E5%88%88%E3%82%8A%E6%8E%A2%E7%B4%A2)

* 愚直

* 半分全列挙
「ちょうど30 手でゴールできるか」を考えましょう。

* 最初の盤面から
15手動かしたときのあり得る状態$U_i$は$4^{15}$通り
* 目標の盤面から
15手動かしたときのあり得る状態$V_i$は$4^{15}$通り

このとき、$U_i=V_j$となるようなi,j の組が存在すれば、よく、これはソートした後、二分探索をすれば高速に判定できます。

$O(4^{n/2}\log(4^{n/2}))$

### -参考-ナップサック問題が分かる人向け
### 巨大ナップサック
ナップサックのwとvが$10^{15}$。
いつものナップサック$O(nw)$では無理。
$n\leq 40$
に注目して、半分全列挙を考える。
nを半分に分けるこれは高々20。$2^{20}$くらいなら全列挙できる。
ある選び方で、重さの総和が$w_1$,価値の総和が$v_1$になったとすると、もう半分の方では、重さ$w_2\leq W-w_1$なる$v_2$の最大を選べばよい。

重さが重いが価値が薄いようなものは考えなくてよいつまり、

$w_2[i]\leq w_2[j] かつv_2[j]\leq v_2[i]$

上記のようなi,jのペアがあるとき、jは考えなくてよい。
これは$(w_2[i],v_2[j])$でソートして、$w_2$が小さい順にみていく。各$w_2$の値について最大の$v_2$の値を見て、これまでの最大の$v_2$の値よりでかければ、採用。更新。

答えになり得る$w_2[i],v_2[j]$のペアだけをこのアルゴリズムで取り出すと、

$w_2[i]\leq w_2[j] \Leftrightarrow v_2[i]\leq v_2[j]$

であるから、$w_2$を二分探索すれば、各$w_1,v_1$のペアごとに、$v_1+v_2$を最大にする$v_2$を$O(\log 2^{n/2})$で求められる。

よって、$O(2^{\frac{n}{2}}\log 2^{n/2})$

# 座標圧縮
https://drken1215.hatenablog.com/entry/2021/08/09/235400

この問題は座圧と呼ばれるもの。
pythonならdict（ or bisect )
c++ならlowerboundが便利

# dp

> 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
>
> 帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
>
> 計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。
> from wikipedia


**重要な言葉**
・一方通行

これが今回の遷移の性質をよく表しています。
dpとは状態の遷移を考えるものですが、更新の順序が定まっていないとdpができません。

例えば今回の例だと、部屋jまでにたどり着くのに最短何分か？を配列として持って、部屋i-1からi,i-2からiの遷移を考えます。これは、i番目”へ”遷移するとき、部屋i-1,i-2まで最短何分かが確定している必要があります。つまり、i-1,i-2の後にiが更新されないといけないということです。

では、この仮定のない場合を考えてみます。今回の問題で、一方通行ではないとします。つまり、iにたどり着いたあと、i-1,i-2などの部屋に遷移できるとします。以下の場合を見てみましょう。

* dp[i-1] = 1
* dp[i-2] = 100
* i-1からiへのcost1 = 10
* iからi-1へのcostも10
* i-2からiへのcost2 = 10
* iからi-2へのcostも10

この場合、
$dp[i]=min(dp[i-1]+cost1,dp[i-2]+cost2)=11$
となります。

ここでいま、iまでは合計コスト11でたどり着けるので
$dp[i-2] = dp[i]+10 = 21$
と、
$i-2が、i-1 \rightarrow i \rightarrow i-2$
と遷移するのが最小になります。
より複雑にすると例えばi+2にコスト0で行ける手段があったら、i+2からi,i+2からi-1,i+2からi-2に遷移したほうがより良くなる場合もあるかもしれません。
これは、今回の問題のような簡単な更新順序でのｄｐでは解決できません。

ここまでの話で意識すべきなのは、この問題が簡単なｄｐで解決できたのは、

・更新順序が比較的自明だったから

という点です。更新順序が自明でないだけで実はｄｐで解決できる問題は多々あります。その例が先ほど議論していた、両側通行可能だった場合です。これは、あるアルゴリズムに従うと更新順序が決定でき、かなり良いオーダーで解くことができます。鉄則の後ろの方のダイクストラのアルゴリズムです。

これは、もちろん、帰納的な関係という言い方もできます。

以降出てくる問題も、どのような構造の遷移なのかを考えるといいかもしれない！