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