ABC077 C – Snuke Festival

はじめに

競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC077 C – Snuke Festivalを解きました。

難易度は緑色。

考察

ABCの三つのパーツがそれぞれ異なる組み合わせで、かつサイズがA<B<Cとなればよい。

普通に全探索をするとO(N^3)になり間に合わないので、BとCのパーツは2分探索で見つけていくことにする。 →しかしこの方法では、Aを全探索、Bの値でCを2分探索を繰り返す、というロジックになり、最悪計算量がO(N^2logN)となり間に合わない。

そこで、AとCをソートし、中間となるBの値で全探索を行う。

この方法なら、O(NlogN)で解を求めることができる。

コード

from bisect import bisect_left, bisect_right

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort()
C.sort()
    
ans = 0
for b in B:
    mina = bisect_left(A, b, lo=0, hi=len(A))
    if mina == 0:
        continue

    else:
        minc = bisect_right(C, b, lo=0, hi=len(C))
        if minc == N:
            continue
    
    ans += mina * (N-minc)

print(ans)

まとめ

シンプルな2分探索の問題かと思ったらちょっとひねりがあって勉強になりました。