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)