典型90【066 – Various Arrays（★5）】をpython解説

AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。

今回は、その内、の66問目である「 Various Arrays（★5）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！

問題名　【066 – Various Arrays（★5）】

問題

考察

期待値を求める問題です。今回期待値は以下の計算で求まります。

\(\Sigma\frac{A[i]>A[j]の数}{A[i],A[j]のありうる組み合わせの数}\)

そこで、分子分母それぞれの求め方について考えていきます。

A[i],A[j]のありうる組み合わせの数

\(A[i]\) と\(A[j]\)の全ての可能な組み合わせの数を計算するために、各要素が取りうる値の範囲を考えます。

ある任意のi,jを選んだ時、\(A[i]\) と\(A[j]\)の全ての可能な組み合わせの数
\((r1 – l1 + 1) * (r2 – l2 + 1)\)

\(A[i]\)の取りうる値の範囲は \(l2\) から \(r1\) までですので、\(A[i]\)が取り得る値の数は \((r1 – l1 + 1)\) になります。

A[i]>A[j]の数

ここから、任意のA[i],A[j]について転倒数の数を数えていきます。

具体的にどのように考えるかというと、

\(A[i]\)の[L1,R1]の値valについて、\(A[j]\)の[L2,R2]の中にvalよりも小さい数の個数を数え上げます

for val in range(l1, r1 + 1):
    cnt += max(0, min(r2, val - 1) - l2 + 1)

• R2<valのときは[L2,R2]すべてがvalいかとなるため
  R2-L2+1
• L2,val<R2のときは[L2,val)の区間が転倒数となる
  val-1-L2+1 (未満なのでval-1してる)
• val<L2のときは転倒数は発生しない
  0

計算量

今回、N<100,L,R<100なので、i,jの組み合わせは\((100*99)/2\)
各i,jについて転倒数の数え上げは100

よって合計の計算量はO(10*6)で十分高速です。

コード

N = int(input())

if N == 1:
    print(0)
    exit()

lr = [list(map(int, input().split())) for _ in range(N)]  # [l, r]のペアを格納
ans = 0

for i in range(N):
    for j in range(i+1, N):
        l1, r1 = lr[i]
        l2, r2 = lr[j]

        all_cnt = (r1 - l1 + 1) * (r2 - l2 + 1)
        cnt = 0

        for val in range(l1, r1 + 1):
            if r2 <= val-1:
                cnt += r2-l2+1
            elif l2 <= val-1 < r2:
                cnt += val-1-l2+1
            else:
                continue
        ans += cnt / all_cnt  # 期待値を足す

print(ans)

まとめ

前の問題【064 – Uplift（★3）】
次の問題【】