AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の7問目である「007 – CP Classes（★3）」を解説していきたいと思います。
問題名 【007 – CP Classes（★3）】
考察
対象レーティングと生徒のレーティングの差が小さいクラスに入れれば良い
しかし・・・
今回、制約がN = Q= 3*10**5なので、Q人の生徒に対して、N個のクラスを総当りで全探索したら間に合いません。
Question ではどうするか？
今回、N個のクラスの対象レーティングは決まっているので、予めソートしておき、何点以上何点以下ならどのクラスに分類されるかわかります。
そのため、
- ソートしておき、何点以上何点以下ならどのクラスに分類されるかを判別するためのしきい値を設ける
- Q人の生徒において、配列2分法(名称が違ったらごめんなさい)を用いてどのクラスが適正かを求めます。
※配列2分法は、ソートされている配列(長さN)に対し、ある数xが何番目に位置するかをO(log(N))で求めることのできるアルゴリズムです。
これにより、O(Q log(N))なので間に合う
pythonの場合は、bisectというライブラリを使用することで楽に実装できます。
典型解法：配列二分法
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import bisect
N = II()
A = LI()
A.sort()#対象レーティングをソートしておく
C = []#何点以上ならどのクラスになるかを表すしきい値
for i in range(N-1):
c = (A[i+1]+A[i])//2#対象レーティングが何点以上ならi番目のクラスになるかを求める
C.append(c)
# print(C)
Q = II()
for q in range(Q):
b = II()
ind = bisect.bisect_left(C,b)
#しきい値C[ind]なので、A[ind]のクラスが一番絶対値の差が小さい
ans = abs(b-A[ind])
print(ans)
まとめ
競技プログラミングで使うライブラリ一覧表みたいのがあったら嬉しい
コメント