AtCoder Beginner Contest 304 D - A Piece of Cakeの勉強

・問題:
atcoder.jp


・参考:
https://atcoder.jp/contests/abc304/submissions/41948730
https://atcoder.jp/contests/abc304/submissions/41961121


・説明
 a,bの線でケーキを切るのでa,bの格子(切り分けられたケーキ)の中でいちごの位置を二分探索してそれをtにいれる。
 c(辞書型で{key、value}と1つの要素に2つの値を持つ)を作ってcのkeyにtがすでにあったらc[t](cのvalue)に++、それ以外はc[t]=1
 cのvalue(場所毎のいちごの数)のうち最大、最小を求める。


pythonでの実装例:

w,h=map(int,input().split())
n=int(input())
pq=[list(map(int,input().split())) for _ in range(n)]  #いちごの位置
A=int(input())
a=list(map(int,input().split()))
B=int(input())
b=list(map(int,input().split()))
c={}
import bisect

for p,q in pq:
  #print(p,q)
  x,y=bisect.bisect_left(a,p),bisect.bisect_left(b,q)

  t=(x,y)      #a,bをグリッドとするいちごの位置。
  if t in c:    #cのkeyにtがあったら。
    c[t]+=1
  else:
    c[t]=1
    
#print(c)  #{(2, 0): 2, (1, 0): 2, (0, 2): 1}  (テストケース1で)。key,いちごの位置。value,その位置でのいちごの個数。

#miが最小のいちごの数
#ifを満たすときmi=min(c.values())、それ以外はmi=0。また(an+1)*(bn+1)はいちごの位置として考えられるところ(A,Bはグリッドの数なので例えばan=1,bn=1ではケーキを4等分した場合になる)つまり下の文はいちごが全部の場所にあればmi=min(c.values())、なかったら最小値miは0。
#下と同じ意味。mi=min(c.values()) if len(c)==(A+1)*(B+1) else 0
if len(c)==(A+1)*(B+1):  #いちごが全部の切り分けられた場所にあれば
  mi=min(c.values())
else:
  mi=0  
ma=max(c.values())
print(mi,ma)