ALDS1_5_D: The Number of Inversions

チャレンジ問題

数列AでA[i]>A[j]かつi<jとなるi,jの組の個数を求める
バブルソートの交換回数に等しいんだけどそれだとTLEになるそうな
さてどう考えるのかな

・・・
・・・

わからん！

ソートの章にあるんだからなにかソートするんだろう
普通にソートしてその結果を使うのか、
ソート自体の方法を応用して数えるのか

ソートアルゴリズムはどれを使うんだろう
マージソートかクイックソートかバケツソートか
結果だけ使うならどれでもよさそうだ
O(n² )のソートではないんだろうな
nの上限が200000で、バケツソートのときと同じになってるのが気になるけど、
値の上限が10⁹ だから少なくともそのままでは使えない

ソートした数列と元の数列を比較したらなにかわかるかと思ったけど
どうもあうまくいかない

・・・

なにはともあれ一度バブルソートでTLEをくらってみるか

def swap(A, i, j):
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp

def count_inversion(A):
    cnt = 0
    for i in range(len(A)):
        for j in reversed(range(i + 1, len(A))):
            if A[j] < A[j - 1]:
                swap(A, j, j - 1)
                cnt += 1
    return cnt

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(count_inversion(A))

main()

rangeで1ずつ減らす数列を作ろうとするとわかりづらくなるので
rangeでは増える数列を作っておいてreversedしてみた

そして予定通りTLE
データ数は100000

このソースがなにか参考になるか
どこか変えたらオーダ下がるかな

内側のループでは、ひとつずつ見なくてもそれまでの
結果を使えば速くなるような気もする

あるいは挿入ソート的なやりかただけど二分探索してみるとか
でも挿入するのにO(n)かかるとあんまり変わらないかもしれない

それともぜんぜん違うやり方が必要なのか