競プロ

転倒数 アルゴリズム

転倒数 (inversion number) とは? 数列 a = {a_0, a_1, a_2 ... a_n-1 } が与えられたとき, i < j かつ a_i > a_j を満たす (i, j) の組の個数を転倒数または反転数という. たとえば a = {3, 1, 5, 4, 2} のとき, i < j かつ a_i > a_j となっている組は, (3…

逆ポーランド記法による数式処理

逆ポーランド記法とは 逆ポーランド記法(Reverse Polish Notation: RPN)は、演算子をオペランドの後に記述する数式やプログラムの記法の一つです。 例えば、一般的な中間記法で記述された数式 (1+2)*(5+4) は逆ポーランド記法では 1 2 + 5 4 + * と記述され…

尺取法についてのあれこれ

はじめに 尺取法というものを知った。 尺取法の概要 JOI用語集によると、 配列に対して二つのインデックスを持ち、条件に応じて片方を進める操作を繰り返すことで答えを得る方法のこと。尺取虫の動きにちなんで名付けられた。DPの一種ともとれる。またキュー…