Ark's Blog

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

ようこそ

2018-02-14

競プロ

この問題の解説で

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

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

参加記競プロ

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

tips 参加記

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

競プロ

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

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

アルゴリズム競プロ

DPについて調べてたらKadane's algorithmという聞いたことないアルゴリズムが出てきたので調べてみた。

Kadane's algorithmは、最大部分配列問題(maximum subarray problem)を $O(n)$ で解くアルゴリズムみたいです。以下は、最大部分配列問題とそれを解くアルゴリズムの解説です。