米田氏が企画した「競プロ典型90問」を解いていきます。
ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。
競プロ初心者なのでどうか温かい目で見守ってください。
なお、本記事中のPythonコードはブラウザ上で実行可能です。
よろしければ遊んでいってください。
問題
kyopro_educational_90/007.jpg at main · E869120/kyopro_educational_90
やってみよう！
テストデータ・テスト関数定義 ↓
# 縮小表示
test_data = [
{
"in":[4, [4000, 4400, 5000, 3200], 3, [3312, 2992, 4229]],
"out": """112
208
171"""
},{
"in":[1, [4000], 10, [3582, 3538, 3320, 3312, 3296, 3257, 3111, 3040, 3013, 2994]],
"out": """418
462
680
688
704
743
889
960
987
1006"""
},{
"in":[10, [869120000, 998244353, 777777777, 123456789, 100100100, 464646464, 987654321, 252525252, 869120001, 1000000000], 10, [4229, 20210406, 1, 268435456, 3582, 536870912, 1000000000, 869120, 99999999, 869120001]],
"out": """100095871
79889694
100100099
15910204
100096518
72224448
0
99230980
100101
0"""
},{
"in":[100, [298750376, 229032640, 602876667, 944779015, 909539868, 533609371, 231368330, 445484152, 408704870, 850216874, 349286798, 30417810, 807260002, 554049450, 40706045, 380488344, 749325840, 801881841, 459457853, 66691229, 5235900, 8100458, 46697277, 997429858, 827651689, 790051948, 981897272, 271364774, 536232393, 997361572, 449659237, 602191750, 294800444, 346669663, 792837293, 277667068, 997282249, 468293808, 444906878, 702693341, 894286137, 845317003, 27053625, 926547765, 739689211, 447395911, 902031510, 326127348, 582956343, 842918193, 235655766, 844300842, 438389323, 406413067, 862896425, 464876303, 68833418, 76340212, 911399808, 745744264, 551223563, 854507876, 196296968, 52144186, 431165823, 275217640, 424495332, 847375861, 337078801, 83054466, 648322745, 694789156, 301518763, 319851750, 432518459, 772897937, 630628124, 581390864, 313132255, 350770227, 642944345, 677742851, 448945480, 688009163, 160941957, 290297295, 5532462, 823543277, 19634445, 15791361, 193309093, 66202596, 72364149, 743270896, 297240520, 264035189, 898589962, 59916738, 307942952, 403411309], 30, [930579110, 22697034, 44652533, 280533771, 753567118, 684927419, 923477579, 557613803, 779616458, 389130756, 323671659, 3117850, 408004003, 224808850, 18421958, 359047808, 364572866, 334631363, 854759331, 647435074, 826055423, 668443532, 620408208, 32237184, 67299071, 251185742, 217292659, 16181227, 850865411, 218577687]],
"out": """4031345
3062589
2044744
2866703
4241278
3081744
3070186
3564353
6718521
8642412
2455689
2118050
700867
4223790
1212487
8277581
13802639
2447438
251455
887671
1596266
9299319
10219916
1819374
607842
12849447
11739981
389866
648537
10454953"""
},
]
def test_all(f):
for i, data in enumerate(test_data):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}")
import unittest
下のmain0関数を完成させて「Run」ボタンをクリックしよう！
def main0(N, A, Q, B):
pass
test_all(main0)
自由欄
try
出ました、二分探索。
【競プロ典型 90 問】001 - Yokan Partyで二分探索を身につけた俺の敵ではない！
def main(N, A, Q, B):
A = sorted(A)
ans = list()
for b in B:
low = -1
high = N
while high - low > 1:
mid = (high + low) // 2
if A[mid] > b:
high = mid
else:
low = mid
if high == len(A): a = abs(A[-1] - b)
elif low == -1: a = abs(A[0] - b)
else:
a = min(abs(A[low] - b), abs(A[high] - b))
ans.append(a)
return "\n".join(map(str, ans))
test_all(main)
結果
当然のAC✌
提出 #32662063 - 競プロ典型 90 問
解説・想定コード
一応確認。
kyopro_educational_90/007.jpg at main · E869120/kyopro_educational_90
想定コード：
kyopro_educational_90/007.cpp at main · E869120/kyopro_educational_90
二分探索なのはいいとして、想定コードが短くてスッキリしてる…
lower_boundってなんだ、ズルいぞ！
ていうかPythonで二分探索する標準ライブラリ無いのかな～無いだろうな～
ありました
bisect --- 配列二分法アルゴリズム — Python 3.10.4 ドキュメント
あるんかい！！知らなかった…
というわけでbisectを使って実装したのが以下。
from bisect import bisect
def main(N, A, Q, B):
A = sorted(A)
ans = []
for b in B:
i = bisect(A, b)
if i == N:
ans.append(abs(A[-1] - b))
else:
ans.append(min(abs(A[i] - b), abs(A[i-1] - b)))
return "\n".join(map(str, ans))
test_all(main)
提出 #32662063 - 競プロ典型 90 問
速度もほぼ変わらず。
まとめ
bisectを覚えた。
自由欄
