Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

転倒数を題材にした問題

転倒数とは

配列の中、インデックスがi < jなのに、ai > ajな(i,j)の数を言う。

これはバブルソートをする際のスワップの回数に等しい。

これを題材にした問題が時々出されるのでまとめておく。

転倒数の求め方

バブルソートの中でスワップの回数を計算すれば求まることは自明。この場合オーダーはO(N2)。

これで遅い場合、O(NlogN)のアルゴリズムで求める。

方針としては以下、

  1. 各jについて個数が求まれば、その総和で良い
  2. 各jについての個数は、それより前にあるai > ajな数である
  3. これは、前にあるai <= ajの数が求まれば求まる。この数をbjとすると、j-bj

bjを逐次的に求めていくことを考える。

例えば、1,3,2,4,2,1のような数列があった時に、3番目の2にいった時に、{ 1 => 1, 3 => 1 } のようにカウントがわかれば、自分より小さい数は1つだとわかる。しかしこれでは一回あたりO(N)かかることになる。

代わりに、[0,1,0,1,0,0,0,0...]のような配列にすることとして、これをBITと表現することで、2以下の数の和をO(logN)で計算出来るようにする。

fn inversion(xs: &[usize]) -> Vec<usize> {
    let mut max_v = 0;
    for &x in xs {
        max_v = max(max_v, x);
    }
    let mut res = vec![];
    let mut bit = BIT::new(max_v+1, &0, |a: &mut usize, b: &usize| *a += b);
    for i in 0..xs.len() {
        let x = xs[i];
        let cnt = bit.sum_excl(x+1); // cnt of <= x
        res.push(i-cnt);
        bit.add_0_orig(x, &1);
    }
    res
}

問題集