JSC2019 Qual B - Kleene Inversion

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
# MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    A = il()

    ret = 0
    for i in range(N):
        overall, right = 0, 0
        for j in range(i+1, N):
            # Aの内部に存在する転倒数
            # （A[i]より右に存在する転倒数）
            if A[i] > A[j]:
                right += 1
        for j in range(N):
            # A[i]より小さい値
            # （Aの内部に存在するA[i]の転倒数）
            if A[i] > A[j]:
                overall += 1
        # A[i]より右に存在する転倒数は K回出現する
        ret += right * K
        ret %= MOD
        # A[i]より小さい値は全体でK * (K - 1) // 2回出現する
        # =>等差数列の和の公式(n(a + l)//2)より
        #   初項0, 末項overall * (K-1), 項数Kから求める
        ret += overall * (K - 1) * K // 2
        ret %= MOD
    print(ret)


if __name__ == '__main__':
    main()

考え方

求める転倒数は2種類存在します。
一つ目はAの内部に存在する転倒数です。
あるi, j(0 <= i <= j <= N-1)を対象としたとき、A[i] > A[j]となる転倒数です。
この転倒数はK回出現します。

2つ目はAが複数個結合されたとき（Bとなったとき）、初めて出現する転倒数です。
Aが複数個結合された場合に出現するため、Aに存在する値のうち、ある値A[i](0 <= i <= N-1)よりも小さい値が全て転倒数の対象となります。
この転倒数の出現回数は等差数列の和から求めることが出来ます。
（こちらの解説が分かりやすいです B - Kleene Inversion - 個人的な競プロメモ）