このシリーズではレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】でまとめられている100問をPythonで解いています。
問題
AtCoder Beginner Contest 077 C - Snuke Festival
ポイント
祭壇中部を中心に考えていきます。
祭壇中部で使用するパーツの大きさをYとすると、作成できる祭壇の種類は、
(祭壇上部に用意されているYより小さいパーツの数) x (祭壇下部に用意されているYより大きいパーツの数)
となります。
祭壇中部に用意されているパーツそれぞれについて、作成できる祭壇の種類を求めていきます。
(祭壇上部に用意されているYより小さいパーツの数) と、(祭壇下部に用意されているYより大きいパーツの数) は 祭壇中部で使用するパーツの大きさYをそれぞれ二分探索することで求めることが可能です。
コード
def main():
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = input()
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
C = list(map(int, input().split(" ")))
A.sort()
B.sort()
C.sort()
# 祭壇中部に用意されているパーツそれぞれについて、作成できる祭壇の種類を求める
ans = 0
for b in B:
use_a = bisect_left(A, b) # 祭壇上部で使用できるパーツの数
inx_c = bisect_right(C, b) # 祭壇下部での二分探索結果
use_c = (len(C) - inx_c) # 祭壇下部で使用できるパーツの数
ans += use_a * use_c # 作成できる祭壇の種類
print(ans)
if __name__ == '__main__':
main()
