ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Binary Indexed Tree(BIT)

AGC029 A - Irreversible operation

問題 提出コード AGCのA問題は最近相性が悪いイメージがありますね、気を付けたいです。 解法 最終的な状態は、左側にW、右側にBが来るような形になります。 ということは、Bを1、Wを0としたときの昇順にバブルソートしたときにスワップする回数、すなわち転…

ABC107 D - Median of Medians

D - Median of Medians 提出コード 初めてBITを使った問題です。 この問題では、中央値となる条件をうまく言い換えていき、最終的に転倒数を求める問題に帰着させます。転倒数を求める段階で、BITを利用します。蟻本をみたらそこにも載っていた問題になりま…