ツバサの備忘録

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

Binary Indexed Tree(BIT)

AOJ 2312 - 魔法少女さやかちゃん

問題 提出コード 解法 添え字は0-indexedとします。 区間の総和は、BITや累積和を用いて高速に取得できるものとします。 とします。 仮に円環でなく直線上に音符を配置しているとした場合、明らかに音符をの昇順に配置するのが最適です。 しかし今回は、音符…

ABC153 F - Silver Fox vs Monster

問題 提出コード 解法 について、で割り、切り上げをしておきます。これで、が 番目のモンスターを倒すまでにかかる攻撃回数 となります。加えて、全てのモンスターを、の昇順で並び替えます。 1番目のモンスターについて考えると、回どこかで攻撃しなければ…

AGC029 A - Irreversible operation

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

ABC107 D - Median of Medians

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