ツバサの備忘録

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

Binary Indexed Tree(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を利用します。蟻本をみたらそこにも載っていた問題になりま…