半分全列挙を「高速化」する【ゆっくり解説】
#ゆっくり解説
#競技プログラミング
#AtCoder
ABC032-D→atcoder.jp/contests/abc032/ta...
ABC184-F→atcoder.jp/contests/abc184/ta...
ABC271-F→atcoder.jp/contests/abc271/ta...
ABC326-F→atcoder.jp/contests/abc326/ta...
ABC336-F→atcoder.jp/contests/abc336/ta...
東京海上日動2020-D→atcoder.jp/contests/tokiomari...
参考資料とした半分全列挙高速化の記事→fairy-lettuce.hatenadiary.com...
0:00 オープニング
0:35 Section 1 - 半分全列挙とは？
2:03 Section 2 - 半分全列挙の計算量
3:00 Section 3 - 半分全列挙高速化 Level 1
4:24 Section 4 - 半分全列挙高速化 Level 2
6:50 Section 5 - 半分全列挙高速化の問題例
7:36 エンディング
競技プログラミングでは、半分全列挙が登場することが多いですが、実装によっては実行時間が厳しくなることがあります。
こんなとき、実は実装を工夫すると計算量が落とせることがあります。
計算量を落とすための実装の工夫について、説明を行います。
------------
当チャンネルでは、競技プログラミング（コンテスト参加・作問など）についての発信を行っていきます！
AtCoder アカウントはこちら→atcoder.jp/users/AngrySadEight
X はこちら→ / sad_eight
Пікірлер: 7
アップロードお疲れ様です！ 今までO(2^n)とO(n * 2^n)の差をあまり考えずに実装をしていましたが、確かに20倍程度の高速化ってなるとかなり違ってきそうですね！ 話は少しそれますが、ABC345-Dでitertools.permutationsを使って順列全列挙するとTLEするのに、DFSで実装すると間に合うのも 3:38 の理由があるかも知れなさそうだと思いました。
@AngrySadEight
Ай бұрын
ご視聴ありがとうございます！ 確かに、順列全列挙についても関数で行うか再帰で行うかの違いもありそうですね。
3:38 の部分がグレイコードだと定数倍速くなると感じました！ マージソートで計算量落ちる形になってるのすごいです！！
@AngrySadEight
Ай бұрын
ご視聴ありがとうございます！ ご指摘のとおり、グレイコードですと定数倍が速くなりますね（容易に非再帰に出来るというメリットもありそうです）。
うぽつです！ 内容はめっちゃ面白いですが、もうちょっとBGMを小さくしていただけると助かります……！！
@AngrySadEight
Ай бұрын
ご視聴ありがとうございます。 BGMの音量に関しましては、調整が不足しておりました。申し訳ございません。次回以降の動画では適切な調整を行ってまいります。
Omg you are so strong