ALDS1_5_D: The Number of Inversions (続きの続き)

やっぱり挿入ソートベースじゃダメなのか

じゃあマージソートかクイックソートかバケツソートか

バケツソートは値が10⁹あるからありそうにない
なにか別の値に置き換えるっていう技があるかもしれないけど

バブルソートや挿入ソートと見比べてみると、クイックソートのほうが
その場で入れ替えていく分似てるところがあるような気がする
違うのは、バブルソートや挿入ソートが隣同士で入れ替えているのに対し
クイックソートは離れた要素を入れ替えていること

離れた要素を入れ替えるときは要素間の距離を足せばいいかな？
swapで足せばすぐ試せる

・・・

ダメだった
離れた要素を入れ替えるときは、間に挟まれた要素も結果に影響を与えるのに
そこが考慮できてないし影響を判断するやり方も思いつかない

マージソートかなあ
あんまりできる気はしてないけど

そもそも何を数えればいいのやら
右と左が入れ替わる回数かなあ
違う
入れ替えの距離の合計かなあ
違う

このあたりはコンピュータ使わずひたすらノートに数字を並べたり
入れ替えたりしてるわけですが
対応する数字の間に線を引いていると何やら交点の数が気になってきました
交点の数と、反転数っておんなじなんじゃ？
うんおんなじ
これは考えてみると当然

ソート前の列とソート済みの列を並べて、対応する数字の間に線を引いて、
交点の数を調べれば反転数が求まる
問題は、交点の数を求める方法がわからないってことなわけだが

でもマージソートの各段階で交点の数を求めて、それを合計してやると
全体の反転数になるっぽい
なぜ合計でうまくいくのかはよくわからない

そして、交点の数は、右側の数を取り出すときに左側に残ってる数の数を
足していけばよさそうだってのもわかる

紙の上でいくつか試す
数学的じゃない帰納法によってうまくいきそうな気がしてきたので書いてみる
結局イテレータがじゃまになってきたので素のインデックスを使う
あとはinvという変数に交点の数を累積してるだけ

from math import inf

inv = 0

def merge(A, left, mid, right):
    global inv

    L = A[left:mid]
    L.append(inf)
    R = A[mid:right]
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            inv += len(L) - 1 - i
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    merge_sort(A, 0, n)
    print(inv)

main()

なんか合わない合わないと思ったらLとRに要素付け足してるの忘れてたりとか
あったけどAC
考え方は合ってたらしい

でも証明してくださいとか言われると困るなー
証明とはいかなくても感覚的にこれは合ってるというところまでも行ってないので
これで漏れなく重複なく数えられてるのかと言うと

このやり方で離れた要素の入れ替えを数えられるなら
クイックソートでも同じ作戦が使えないかな？

ダメか
間に挟まってる数が本来の入れ替えに含まれる場合と含まれない場合があるみたい
それをいちいちチェックするとやっぱりオーダが変わってしまいそう
という観点で見ると、マージソートだと間に挟まってる数が必ず入れ替えに
なる数になっている
というのはあるな
少し確からしさが増した

これくらいで解説を読もう
たぶんマージソートを使うところは合ってると思うので
あとは感覚的に納得できるかどうか

・・・

自分で考えたこと以上の説明はなかった
残念

まあでも解けたのでだいたいさっぱり
次いこ次