AOJ ALDS1_5_D The Number of Inversions
備忘録
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp
回答
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque sys.setrecursionlimit(10000000) ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def merge(A, left, mid, right): n1 = mid - left n2 = right - mid L, R = [0] * (n1 + 1), [0] * (n2 + 1) for i in range(n1): L[i] = A[left + i] for i in range(n2): R[i] = A[mid + i] L[n1] = float('INF') R[n2] = float('INF') i, j = 0, 0 reverse_cnt = 0 for k in range(left, right): if L[i] <= R[j]: A[k] = L[i] i += 1 else: reverse_cnt += n1 - i A[k] = R[j] j += 1 return reverse_cnt def merge_sort(A, left, right): cnt = 0 if left + 1 < right: mid = (left + right) // 2 cnt += merge_sort(A, left, mid) cnt += merge_sort(A, mid, right) cnt += merge(A, left, mid, right) return cnt def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() A = il() q = merge_sort(A, 0, N) print(q) if __name__ == '__main__': main()
考え方
螺旋本より、マージソートの応用問題。
ふーん。。ぐらいの雰囲気で理解した。
マージ処理時に、ai > aj
かつi < j
の組をカウントすることで回答できる。
n
個の要素を持った数列A
([a0, a1, ... an-1]
)に対して、
ai > aj
かつi < j
の組を求める。
螺旋本の解説を元に、マージソートに修正を加えて回答した。
マージソートのマージ処理はソート済みの配列L
とR
のマージを行い、
1つの配列とする。
この時、配列R
の要素は全て、元の配列の真ん中の要素より右に位置する。
つまり、配列L
のインデックスをi
、配列R
のインデックスをj
とすると、
i < j
が成立していることになる。
そのため、配列L
と配列R
をマージするとき、
L[i] > R[j]
となる要素数をカウントすることで回答を得られる。
要素数のカウントは配列L
の要素数 - 既にマージ済みの要素数なので、
n1 - i
で求めることが出来る。