search

habara-k / ICPCLibrary

https://habara-k.github.io/ICPCLibrary/
3 stars 0 forks source link

最大独立集合を追加 #54

Closed kanra824 closed 3 years ago

kanra824 commented 3 years ago

まだ早くなるはずなので、改善する

habara-k commented 3 years ago

テストコードの入出力は変えずに、MaximumIndependentSetの部分だけkyopro_friendsさんのに変えた場合、yosupo judgeの速度を比較してもらっても良いですか？

kanra824 commented 3 years ago

@habara-k https://judge.yosupo.jp/submission/5455 https://judge.yosupo.jp/submission/27151

kanra824 commented 3 years ago

たいてい大丈夫だと思うので、修正はいらないかなと思っています Mixture Drug（最大独立集合の問題）も試してみる

kanra824 commented 3 years ago

ア！

kanra824 commented 3 years ago

落ちました...（書きます...）

kanra824 commented 3 years ago

friendsさんを参考にしたらfriendsさんより早くなった(なんで？)

kanra824 commented 3 years ago

forループでbit演算使わず愚直にn回ループ回したので、逆に最適化効きやすくなったりキャッシュに乗りやすくなってるとかかな

habara-k commented 3 years ago

再帰になってる、すごい

kanra824 commented 3 years ago

再帰の各時点で次数が最大の頂点を使うのがミソっぽい

kanra824 commented 3 years ago

あーこの修正するとO(n1.466^n)がO(n1.381^n)になりますね

habara-k commented 3 years ago

この実装をする上で参考にしたサイトのリンクとかあれば、ここに残してほしいです！ コードはおっけーです！

kanra824 commented 3 years ago

参考 https://judge.yosupo.jp/submission/5455

habara-k commented 3 years ago

https://www.slideshare.net/wata_orz/ss-12131479