Ark's Blog

引っ越しました→ https://blog.arkark.dev/

ようこそ

2018-03-07

アルゴリズム数学競プロ

bitテクニックで、集合の部分集合を列挙するものがあります。その紹介と数学的理解です。

競プロ

この問題の解説で

実験結果から分かるように， ${g_i = }$ （ ${i}$ を割り切る最大の $2$ の冪）であることが示せます．

とあります。たしかに計算してみるとそうなるのですが、実際に成り立つのか気になるので証明しました。

参加記競プロ

第4回ドワンゴからの挑戦状本戦に参加しました！

tips 参加記

1/17(水)にTokyotechTrap LT#3というLTがありました。発表したのでそのときのスライドとか補足とかです。

競プロ

この問題は、制約がゆるいので $O(n^2)$ 解法で十分通るのですが、解説によれば $O(1)$ でも通せるみたいです。

計算したら $O(1)$ 解法ができたので書きます。