AtCoder / ABC077 / C: Snuke Festival

C - Snuke Festival

なお、コンテストに参加したもののCで詰んでしまいました。。

問題概要

N個の正の整数からなるA, B, Cの3つの配列が与えられる。それぞれの任意の要素をa, b, cとしたときa<b<cとなるような組み合わせの個数を答えよ

最初やってた解答

※これはダメ解答です

n = int(input())
A, B, C = [list(sorted(map(int, input().split())))  for _ in range(3)]
cnt = 0
# O(3*N) でギリギリ？pythonだと微妙かも
for a in A:
    for b in B:
        for c in C:
            if a<b<c and len(set([a, b, c]))>1:
                cnt+=1
print(cnt)

コメント、今なら声を大にして言える。微妙かもじゃねぇよ！！！まるっきりダメだよ！！！あとオーダーすら間違ってるよ！！N^3だよ！！！！

・・・で、コンテスト終わる間際くらいに諦めてトイレ行ってたら気づきました。「あれ？a<bってのは『Aを越える最小のb』ってことだよな、、最近どこかでこの形を見た気が・・・」

or3.hatenablog.com

自分で書いてんじゃん！！！！！！！！！１

・・・つい直前の記事だというのに忘れていた。。。脳が弱すぎる。。。。

あとで書いた解答

# バイナリサーチで解く。
# Bの要素を基準にしてa<b<cとなるものを選ぶ。すべての配列はソート済みとして、
# a<bとなる最大のa, b<cとなる最小のcを選び、それら独立する事象の数の積を足していく

n = int(input())
A, B, C = [list(sorted(map(int, input().split())))  for _ in range(3)]

cnt = 0

def bs_left(lis, target):
    # ソート済みのlisのうちtargetがどこに入るか（index）
    # 要素がtargetと重複する場合はより小さいインデックスを返す。すなわち「lisのうちtarget未満となる最大の要素のインデックス」
    # ex) min(lis)=mとするとtarget<=mのとき0
    low, high = 0, len(lis)
    while low<high:
        mid = (low+high)//2
        if lis[mid]<target:
            low = mid+1
        else:
            high = mid
    return low

def bs_right(lis, target):
    low, high = 0, len(lis)
    while low<high:
        mid = (low+high)//2
        if target<lis[mid]:
            high = mid
        else:
            low = mid+1
    return low

for b in B:
    # 探索のときにちゃんとみているので a!=b and b!=cみたいな条件は必要ない
    cnt += (bs_left(A, b) * (n-bs_right(C, b)))
print(cnt)

すんごい情けなくなりましたがACしました・・・ちくしょう・・・・

解法

ポイントは、a<bとb<cは独立する事象であるということです。ソートしてあれば、jを増やしていって初めてb<=A[j]となるときのA[0]~A[j]と、同じくkを増やしていって初めてb<C[k]となったときのC[k]~C[N-1]では、それぞれの要素に対し他方のぶんだけ組み合わせが存在することになります。

A=[1, 1, 3, 5]
C=[2, 3, 4, 7]

b=2とすると、A[j]<bとなる最大のjは2です。すなわちA[0]=1, A[1]=1の2つが該当します。
b<C[k]となる最小のkは1です。したがってC[1]からC[N-1]まですべてが該当します。
よって(a, c)の組を考えると、aの取りうる値はA[0], A[1]、cの取りうる値はC[1], C[2], C[3]なので2*3=6個の組が考えられる、というわけです。b=3だとA[3]とC[2], C[3]なので1*2=2つですね。

結局、Aのうちbを下回る最大のaのインデックスとCのうちbを上回る最小のcのインデックスがわかるとそれぞれ該当する個数が出せるので、それらの積をとってどんどん足していく、という感じになります。わかりにくかったらすみません。間違ってたらごめんなさい。

自分用まとめ

やったことは覚えておけ。。。。