差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:inversion [2022/08/17] – ikatakos | programming_algorithm:dynamic_programming:inversion [2022/08/17] – [同じ要素を含む場合] ikatakos | ||
|---|---|---|---|
| 行 120: | 行 120: | ||
| print(ans) | print(ans) | ||
| </ | </ | ||
| + | |||
| + | === 末尾からでもよい === | ||
| + | |||
| + | 数列を末尾から処理してもよい。（$i=N-1, | ||
| + | |||
| + | その場合、各 $i$ における $SUM(p_i-1)$ で「自身より右にある、自身より小さい値の個数」を直で得られるので、$i$ から引くというプロセスが省け、人によっては多少わかりやすいかもしれない。ただしSUMの引数は $p_i-1$ にする必要がある。 | ||
| 行 141: | 行 147: | ||
| 転倒数を求める上では、（同じ数字を含まない場合でも変わらないが、今一度）境界に注意。 | 転倒数を求める上では、（同じ数字を含まない場合でも変わらないが、今一度）境界に注意。 | ||
| - | 上記の左から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、 | + | 上記の、先頭から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、 |
| $i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。 | $i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。 | ||
