差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:inversion [2022/08/17] – ikatakos | programming_algorithm:dynamic_programming:inversion [2022/08/17] – ikatakos | ||
|---|---|---|---|
| 行 76: | 行 76: | ||
| ==自分より左にある自分より大きい数の個数を求める== | ==自分より左にある自分より大きい数の個数を求める== | ||
| - | 先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。 | + | 先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。\\ |
| + | その個数の総和は $i$ である。 | ||
| - | 自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$（$1$～$p_i$ の和）を求めることで得られる。 | + | 自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$（$p_1～p_i$ の和）を求めることで得られる。 |
| - | 逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ | + | 逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ |
| 数列の各要素につきこれを足し合わせることで、転倒数が得られる。 | 数列の各要素につきこれを足し合わせることで、転倒数が得られる。 | ||
| 行 86: | 行 87: | ||
| ==BITに加算する== | ==BITに加算する== | ||
| - | BITの $p_i$ の位置に、1を加算する | + | $i+1$ 以降のために、BITの $p_i$ の位置に |
| * $ADD(p_i, 1)$ | * $ADD(p_i, 1)$ | ||
| 行 130: | 行 131: | ||
| バブルソートの交換回数においても、同じ要素は交換しても状況が何も変わらないので行う必要は無く、最小回数には入らない。 | バブルソートの交換回数においても、同じ要素は交換しても状況が何も変わらないので行う必要は無く、最小回数には入らない。 | ||
| - | つまり、（転倒数自体とは関係ないが）ソートする前と後とで同じ要素内の順番は変わらない。 | + | つまり、（転倒数自体とは関係ない話題だが）ソートする前と後とで同じ要素内の順番は変わらない。 |
| ソート前 | ソート前 | ||
| 行 138: | 行 139: | ||
| ソート後 | ソート後 | ||
| - | 今一度、境界に注意。 | + | 転倒数を求める上では、（同じ数字を含まない場合でも変わらないが、今一度）境界に注意。 |
| 上記の左から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、 | 上記の左から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、 | ||
| - | 全体から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。 | + | $i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。 |
| 行 165: | 行 166: | ||
| 数列の最大値もわからないし、先読みもできないので圧縮もできない、みたいな変な状況がもしあったら、、、 | 数列の最大値もわからないし、先読みもできないので圧縮もできない、みたいな変な状況がもしあったら、、、 | ||
| - | 平衡二分探索木等を使うと、ここまでに出てきた数のうち自身が何番目に小さいかを取得できるので、代用できるはず。 | + | BITの代わりに平衡二分探索木等を使うと、値の上限を気にせずここまでに出てきた数のうち自身が何番目に小さいかを取得できるので、代用できるはず。 |
