競プロ初中級者100問

ABC077C Snuke Festival

この記事で使うアルゴリズム

二分探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc077/tasks/arc084_a

方針

  • Bを固定しながら、Bより小さいAはいくつあるかBより大きいCはいくつあるかを考える
    • ソートしてから二分探索すると良い。
      • 計算量はソートがO(logN)でそれをBの数だけ行うO(N)ので、O(NlogN)となる。
      • 標準ライブラリbisectを使うと良い。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import bisect
N = int(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:
    a = bisect.bisect_left(A, b) # 挿入点はどの同じ値よりも左
    c = bisect.bisect_right(C, b) # 挿入点はどの同じ値よりも右
    ans += a * (len(C)-c)
print (ans)

着想

上段（下段）を固定することはすぐに思い浮かぶが、中段を固定することは思い浮かび難いので慣れる必要がある。3層の構造になっている場合は中段の固定を考えた方が問題が簡単に解くことができる。

Bが増えるほど、Aの候補は増えCの候補が減るというような単調性を見つける。単調性があるときは二分探索で計算量を減らす。

関連記事

記事情報

  • 投稿日：2020年4月11日
  • 最終更新日：2020年6月19日