Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、2問目を解説していきたいと思います。
問題名 【B – Kleene Inversion】
入力 N,K,A
問題
長さNの数列AがK回繰り返される数列Bを作るその中で、転倒数(左の数よりも右の数が小さい)は何個あるかという問題です。
考察
転倒数が起きる条件を場合分けで考える
- パターン1 同じブロック内で転倒数が起きる場合
ex) A = [2,4,3] 4と3のように、与えられたAというブロック内で転倒数がある場合 - パターン2 ブロックをまたいで転倒数が起きる場合
ex) A = [1,2] K = 2 B = [1,2, 1,2] のようにブロックをまたいで転倒数がある場合
パターン1 同じブロック内で起きる場合
A = [2,4,3]の場合、 4と3のように、与えられたAというブロック内で転倒数がある場合
Aというブロック内での転倒数の数を数えます。1ブロック(A)は最大で2000なので、右の数と左の数それぞれに対して全探索可能です(2000*1999/2)。
p = 0 # パターン1で得られる転倒数
for i in range(N-1):
for j in range(i+1,N):
if A[i] > A[j]:
p += 1
pattern1 = p*kここで、AというブロックはK個あるので、同じブロック内での転倒数の数はp*K
パターン2ブロックをまたいで起きる場合
K個のブロックから2つのブロックを選び、選ばれたブロック間での転倒数の数を数えます。
こちらに関しても、選ばれたブロックそれぞれに対して、全探索が可能です(2000*2000/2)
q = 0
for i in range(N):
for j in range(N):
if A[i] > A[j]:
q += 1
pattern2 = q*(K-1)*K//2 # (K-1)*K//2 はブロックの選び方ここで、2つのブロックの選び方はK(K-1)/2通りあるので、ブロック間での転倒数の数は、qK*(K-1)//2
コード
なので最終的なコード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
import math
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N,K =MI()
A = LI()
mod = 10**9+ 7
p = 0
q = 0
for i in range(N-1):
for j in range(i+1,N):
if A[i] > A[j]:
p += 1
q = 0
for i in range(N):
for j in range(N):
if A[i] > A[j]:
q += 1
ans = (p*K + q*(K-1)*K//2) % mod
print(ans)まとめ
今回のように一見難しそうな問題も、要素要素に分解して考えてみると意外と解けたりするのが、競技プログラミングの面白いところ。
コメント