AC-JSC2019-B. Kleene Inversion

작성일

문제: https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b

해설: https://img.atcoder.jp/jsc2019-qual/editorial.pdf

  • 처음에는 이게 뭐지 하고 뜨악하다가.. 간신히 inversion count를 세고 $K*(K+1)/2$랑 곱하면 답이 나오는것을 알아냈다.
  • 하지만 거꾸로된 inversion count도 고려해야하는게 함정..
  • 처음에 C로 작성했다가 무참히 패배했다. 멍청하게도 나누기 2 부분을 Modulo 연산 안에다가 넣어버린것…
  • 꼭 다시금 기억하자.. 나누기는 Modulo가 안된다!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long N, K;
  vector<int> A;
  cin >> N >> K;
  A.resize(N);
  for(int i = 0; i < N; i++) cin >> A[i];

  long long left = 0, right = 0;
  for(int i = 0; i < N; i++)
    for(int j = i+1; j < N; j++)
      if(A[i] > A[j]) left++;

  for(int i = N-1; i >= 0; i--)
    for(int j = i-1; j >= 0; j--)
      if(A[i] > A[j]) right++;

  const long long MOD = 1000000007;

  long long ans = 0;
  ans += K * (K+1) / 2 % MOD;
  ans = ans * left % MOD;

  long long rans = 0;
  rans += K * (K-1) / 2 % MOD;
  rans = rans * right % MOD;

  cout << ((ans+rans)%MOD);
}
  • 결국 시험중에는 오류를 못찾고 -_-.. 파이썬으로 다시 써서 제출함. 파이썬의 BigInt 지원이 혜자다 혜자..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
N, K = tuple(map(int, input().split()))
arr = list(map(int, input().split()))

left = 0
for i in range(N):
    for j in range(i+1, N):
        if arr[i] > arr[j]:
            left+= 1

right = 0
for i in range(N-1,-1,-1):
    for j in range(i-1,-1,-1):
        if arr[i] > arr[j]:
            right+= 1

print(((left * K*(K+1) // 2) + (right * K*(K-1)//2)) % (1000000007))