競プロ典型90問 007 - CP Classes（★3）コード解説

はじめに

お疲れ様です。私事ですが、昨日Netflixを契約しました！今までアマプラで十分かな～とか思って 契約してなかったけど、いざ契約してみたら見たかったものがあれもこれも…。ジョジョ6部にヴァイオレットエヴァーガーデン、バキ、etc...。これは年末まで忙しくなりそうですね！

さて、本日は競プロ典型90問の★3問題から『007 - CP Classes』を解説していきたいと思います。

競プロ典型90問

atcoder.jp

007 - CP Classes（★3）

007 - CP Classes

競技プログラミングの塾には、クラスのレーティングと生徒のレーティングがあり、各生徒のレーティングとその生徒が所属するクラスのレーティングの差が最小になるようにするという問題です。

考え方としては、各生徒のレーティングとそれぞれのクラスとの差を取って不満度を計算して最小の不満度を算出し、それを合計するといったものです。しかし、そのまま実装しようと思ってもTLEとなってしまいます。

ここで、少し考え方を変更する必要があります。

自分のレートに最も近いクラスを見つけるには、全てのクラスのレートと比べるのではなく、「クラスをレートが低い順に並べたときに、自分のレーティングはどのクラスに一番近いのか」を考えていきます。以下に流れを示します。

1. クラスのレーティングを低い順に並べる。
2. 自分のレーティングがどのクラスの間にあるのかを調べる。
3. その2つのクラスのレーティングと自身のレーティングを比較して、小さいほうを不満度として加算する。

ここで2について、２分探索というアルゴリズムを用いることで、効率的にどのクラスの間に値を挿入できるかを求めることが出来ます。２分探索のアルゴリズムの詳細については解説しませんが、Python ではbisectライブラリで簡単に実装することが出来ます。

コード

from bisect import bisect_left
 
n = int(input())
a_list = list(map(int, input().split(" ")))
q = int(input())
a_list.sort()
 
for i in range(q):
    b = int(input())
    if b <= a_list[0]:
        distance = abs(a_list[0] - b)
        print(distance)
    elif b >= a_list[-1]:
        distance = abs(a_list[-1] - b)
        print(distance)
    else:
        x = bisect_left(a_list, b)
        distance = min(abs(b - a_list[x]), abs(b - a_list[x-1]))
        print(distance)

おわりに

今回は競プロ典型90問の★3問題を解説していきました。次回以降ですが、ABC281の解けなかったD問題が動的計画法で解けるらしいので、そちらを本格的に学習していこうかなと考えています。 お疲れ様でした。