半分全列挙を「高速化」する【ゆっくり解説】

[@for_i_in_loop]

アップロードお疲れ様です！ 今までO(2^n)とO(n * 2^n)の差をあまり考えずに実装をしていましたが、確かに20倍程度の高速化ってなるとかなり違ってきそうですね！ 話は少しそれますが、ABC345-Dでitertools.permutationsを使って順列全列挙するとTLEするのに、DFSで実装すると間に合うのも 3:38 の理由があるかも知れなさそうだと思いました。

[@AngrySadEight]

ご視聴ありがとうございます！ 確かに、順列全列挙についても関数で行うか再帰で行うかの違いもありそうですね。

[@sinxcosxtanx]

うぽつです！ 内容はめっちゃ面白いですが、もうちょっとBGMを小さくしていただけると助かります……！！

[@AngrySadEight]

ご視聴ありがとうございます。 BGMの音量に関しましては、調整が不足しておりました。申し訳ございません。次回以降の動画では適切な調整を行ってまいります。

[@A57278]

Omg you are so strong

[@hiro1729-cn9vr]

3:38 の部分がグレイコードだと定数倍速くなると感じました！　マージソートで計算量落ちる形になってるのすごいです！！

[@AngrySadEight]

ご視聴ありがとうございます！ ご指摘のとおり、グレイコードですと定数倍が速くなりますね（容易に非再帰に出来るというメリットもありそうです）。