【Pythonメモ2-1】bisectを使ってC問題を解く。
・最近この曲をループ再生しながらPythonすることが多いです。(謎宣伝)
サビの高音から低音にかけていくのが本当にｷﾓﾁｲｲ･･･
・次のふたつのC問題をbisectモジュールを使って解いてみよう。
■【ABC212】C - Min Difference
■【ABC213】C - Reorder Cards
・bisectモジュールのちょっとした使い方については次を参考にしました。
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
・軽くbisectの説明。
- import bisect
a=[10,20,30,40,50,60,70,80,90,100,100]
print(bisect.bisect_left(a,55)) ⇒ 5
print(bisect.bisect_left(a,50)) ⇒ 4
print(bisect.bisect_left(a,5)) ⇒ 0
print(bisect.bisect_left(a,100)) ⇒ 9
print(bisect.bisect_left(a,105)) ⇒ 11
・importでbisectを呼び出します。
・関数はbisect_leftとbisect_rightのふたつがありますが、rightは使わないことが多いみたいな記事を拝見した記憶があるのでleftだけ使えるようになればいいと思います。(一方の使い方を理解すれば他方も理解できるはずなので)
・aというリストは大まかに背の順だと思ってください。身長が10m,20m,...,100mの人がいます。そこに身長55m,50m,5mの人が入るには左から何番目が適しますか？という質問をbiseect.bisect_left(list,int) で送ればインデックスが返ってきます。
・恐らく意味は「list中にintが入るなら何番目ですか？」かと思われ、(int,list) で書くとエラーが返ってくるので逆にしないようにしましょう。
(「int中にlistが入るなら何番目ですか？」では意味が分かりませんね。)
■bisect.bisect_left(a,55) = 5 について
・身長が5mの人がいれば先頭(=0)に立ちます。for文が0から始まるのと同様に、左から0カウントなので、55は5カウント目に入ることからインデックスとして5が返ります。
■bisect.bisect_left(a,50) = 4 について
同様の値が存在する場合、bisect.bisect_leftのleftの意味から察し、左側としてカウントします。なので5になりません。(もし、bisect.bisect_rightであれば、5が返ってきます。)
■bisect.bisect_left(a,5) = 0 について
・10mの人の左側の最も左側に立ちます。for文と同様に、0カウント始まりなのでインデックスは0として返ってきます。
■bisect.bisect_left(a,105) = 11 について(重複している場合！非常に重要！)
・100mの人の右側に立つのですが、100mの人は二人いますね。このように同じ要素があっても各々独立したものとして考えるので、100mの人が二人いたら二人分として数えます。背の順と全く同じ考え方であり、二人分を一人分として数えることはありません！
・更に bisect.bisect_left(a,100) = 9 であることにも注目しておきましょう。(二人分飛ばしなので100mの人は9番目、105mの人は11番目であることに注目します。)
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
・先に、C - Min Differenceを解説します。
▼コードは以下の通りです。
- import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
li =
b.sort()
for i in range(n):
c = bisect.bisect_left(b, a[i])
if c == 0:
li.append(abs(a[i]-b[0]))
elif c == m:
li.append(abs(a[i]-b[m-1]))
else:
li.append(min(abs(a[i]-b[c-1]), abs(a[i]-b[c])))
print(min(li))
Submission #24930971 - AtCoder Beginner Contest 212
・さて、本問は幾つかの解法があるはずですが、なぜ「bisectを用いれば解けるのでは？」と思いついたのかを説明します。
・というのも、bisectの性質自体が本問に直接役立たせているから、としか言いようがないんですが、折角上記でbisectの使い方を軽く説明したので、その例を用いて簡単な具体的な処理から考えることにします。
■■■リストaがN個の整数値の要素を持つとき、aの各々の要素に対し整数値bとの差が最小になる値を求めよ。■■■
▼この程度であれば、Nの制約にもよりけりですが
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
- li=［］ で予めリスト宣言をする。
- for文(for i in range(N)) を用意する。
- li.append(abs(a[i]-b)) でリストに内蔵する。
- print(min(li)) で内蔵された差のうち、最も小さいものを出力する。
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
といった４ステップを踏めば、流れは典型的なB問題です。
・さて、本問に対して同様な操作を行うとどうなるでしょうか？
・制約を覗くとAとBの要素の個数の最大数は 2*10⁵ と書いてありますね。
・つまり、脳死二重for文ループで abs(a[i]-b[j]) とかしていたら O(10¹⁰) 相当の計算量になるためTLEになります。
・そこで。このｸｯｯｯｯｯｯｯｯｯｯｿ莫大な計算量を大幅に削減するために、bisectくんが活躍します。
・上記の４ステップにbisectくんを追加する６ステップで本問を完封することが可能です。
・なぜなら、bisectくんによって背の順で指定された位置の前後との差を取ればよいからです。この一工夫を行うだけでACを獲得できます！
▼ということで、bisectくんを追加した６ステップは以下のようになります。
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
- li=［］ で予めリスト宣言をする。
- for文(for i in range(N)) を用意する。
- c=bisect.bisect_left(b,a[i]) と定義する。
- if文でcが最前列or中間or最後尾で分別し、該当するbの背の前後との差を求める。
- (a[i]が中間ならば)li.append(min(abs(a[i]-b[c-1]),abs(a[i]-b[c]))) でリストに内蔵する。
- print(min(li)) で内蔵された差のうち、最も小さいものを出力する。
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
・追加点、改善点は緑色にしました。
・今まで言及していませんでしたが、配列bは背の順並びなので予めソートをしておく必要があります。aもソートをしても構いませんが、特に意味はないです。
・手順５において、a[i]が中間じゃないとき、それは最前列か最後尾に属し、例えば最前列であればその前に要素bはありません。故にbの最前列の b[0] との差を求めるしかないのです。(b[-1]は最後尾ですが、これと比較してはいけません。)
・同様に、a[i]が最後尾である場合はbの最後尾の b[m-1] との差を求めるしかありません。これをif文で条件分岐を作ったわけです。数学でいう場合分けと同じですね。
・上記を踏まえれば本問を解くことができます。もう一度コードを載せておきます。
▼myコード
- import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
li =
b.sort()
for i in range(n):
c = bisect.bisect_left(b, a[i])
if c == 0:
li.append(abs(a[i]-b[0]))
elif c == m:
li.append(abs(a[i]-b[m-1]))
else:
li.append(min(abs(a[i]-b[c-1]), abs(a[i]-b[c])))
print(min(li))
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
・次はC - Reorder Cardsを解説します。
▼コードは以下の通りです。
- import bisect
h, w, n = map(int, input().split())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]
lix =
liy =
X = list(set(x))
Y = list(set(y))
X.sort()
Y.sort()
for i in range(n):
lix.append(bisect.bisect_left(X, x[i]) + 1)
liy.append(bisect.bisect_left(Y, y[i]) + 1)
for i in range(n):
print(lix[i], liy[i])
Submission #24933916 - AtCoder Beginner Contest 213
・こちらの問題は座標圧縮を実行する問題です。
・座標圧縮とはリストに幾つかの整数値の要素があり、小さい順から1,2,3...とか0,1,2...という風に名前を付けていくことです。(端的に言うとね)
・例えば [10,3,2,5] であれば [4,2,1,3] と変換したいのです。ソート化と二重for文を用いればできなくもないんですが、本問の制約は要素の最大数が 10⁹ と書いており、要素分だけfor文を２回回すので O(10¹⁸) では十分に間に合いません。(実際にTLE以外にWAが出たりで解法としても非常によろしくない)
Submission #24887358 - AtCoder Beginner Contest 213
↑こんな感じ
・そこで、このｸｯｯｯｯｯｯｯｯｯｯｯｯｯｯｯｯｯｯｿ莫大な計算量を大幅に削減するために、またまたbisectくんが活躍します。
・さて、どのようにbisectを使えばいいのかについてですが、a=[10,3,2,5] をソートすると A=[2,3,5,10] になりますね。そこで「bisect_rightを用いて a[i]がAの何番目に入るのか」というのが直接座標圧縮に繋がっているのが分かりますか？
・a[0]=10 が bisect_right でAのどこに位置するのかは左側から数えて４番目なので、インデックスとして４を返します。
・a[1]=3 についても同様の操作を行うことで 2 を返してくれます。
・a[2], a[3] についても同様な操作を(ry
・という操作をaの要素分だけfor文で回せばよさそうです。
・ただし、一番最初のbisectの軽い説明の所にもあった通り、重複している要素は省く必要があります。
・例えば [10,3,2,5,3] であれば [5,2,1,4,2] と変換されてしまうので、重複している要素を省く羽目になるからなんです。
(a=[10,3,2,5,3] をソート化した A=[2,3,3,5,10] において、a[0]=10 は左側から５番目にありますが、４を返す必要があるからなんです。)
▼ということで、以上の流れを箇条で書いてみましょう。
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
- lix=［］, liy=［］ を予めリスト宣言をする。
- リストx,yをset化し、それを再度リストに直してソート(X,Y)する。(重複をなくすため)
- for文(for i in range(n)) を用意する。
- bisect_rightで要素 x[i],y[i] が X,Y のどこに位置するかを返し、それをそれぞれ lix, liy に内蔵する。
- for文を用い、内蔵されたn個の要素 x[i], y[i] を出力する。
◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢
・上記を踏まえれば本問を解くことができます。もう一度コードを載せておきます。
▼myコード
- import bisect
h, w, n = map(int, input().split())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]
lix =
liy =
X = list(set(x))
Y = list(set(y))
X.sort()
Y.sort()
for i in range(n):
lix.append(bisect.bisect_left(X, x[i]) + 1)
liy.append(bisect.bisect_left(Y, y[i]) + 1)
for i in range(n):
print(lix[i], liy[i])
・書くのに疲れるし、時間がかかるのでもっと簡素に書きたいが・・・復習する際にこれぐらい書いておけば楽にできると思うから書かざるを得ないと思ってる（
・もっともっと学ぶべきことが多いから若干挫折してるが、一ヵ月ぐらい頑張ってみる。
お疲れさまでした。
