差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:dynamic_programming:inversion [2022/08/17] – ikatakos | programming_algorithm:dynamic_programming:inversion [2022/08/22] – ikatakos | ||
---|---|---|---|
行 64: | 行 64: | ||
最大値がわかっている必要がある。 | 最大値がわかっている必要がある。 | ||
- | 最大値が大きすぎると、数列の要素自体は疎でも、BITにおける計算に時間がかかってしまう。\\ | + | 以下のような場合は、事前に圧縮する。 |
- | そのような場合は、数列の要素を事前に小さい順に $1,2,3,...$ に対応づけて圧縮してもよい。\\ | + | |
- | すると数列の長さ $N$ が最大値の上限となる。\\ | + | * 負の数や、小数を含む |
+ | * 続く実装では、数列の各要素をBIT上のindexに対応づけるので、非負整数である必要がある | ||
+ | * 最大値が巨大すぎる | ||
+ | * 同じ理由で、時間的・メモリ的に無理 | ||
+ | |||
+ | 圧縮とは、数列の要素を事前に小さい順に $0,1,2,3,...$ に対応づけて置き換えることを指す。\\ | ||
+ | すると数列の長さ $N$ が、最大値の上限となる。\\ | ||
転倒数では大小関係しか見ないので、圧縮しても結果は変わらない。 | 転倒数では大小関係しか見ないので、圧縮しても結果は変わらない。 | ||
+ | |||
+ | A = [ 1000 -5 1001 1000 -1000 ] | ||
+ | ↓ | ||
+ | A'= [ 2 | ||
行 125: | 行 135: | ||
数列を末尾から処理してもよい。($i=N-1, | 数列を末尾から処理してもよい。($i=N-1, | ||
- | その場合、各 $i$ におけるBITの | + | その場合、各 $i$ における $SUM(p_i-1)$ で「自身より右にある、自身より小さい値の個数」を直で得られるので、$i$ から引くというプロセスが省け、人によっては多少わかりやすいかもしれない。ただしSUMの引数は $p_i-1$ にする必要がある。 |
行 147: | 行 157: | ||
転倒数を求める上では、(同じ数字を含まない場合でも変わらないが、今一度)境界に注意。 | 転倒数を求める上では、(同じ数字を含まない場合でも変わらないが、今一度)境界に注意。 | ||
- | 上記の左から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、 | + | 上記の、先頭から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、 |
$i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。 | $i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。 | ||