Atcoder ABC 146 の記録

Atcoder 146 の C問題で出された二分探索について復習していきたいと思います。

二分探索とは

まずはそもそも二分探索ってなんだっけ？というところから振り返ります。
Wikipediaによると、

二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

二分探索 - Wikipedia
  ということでポイントは、ソートすること、配列にすることですね。

二分探索をしたいとき

二分探索をしたいときとはどのようなときでしょうか？

今の理解だとふんわりこんな感覚で捉えています。

  • 総当りで何かの値を探したいとき。
  • データ量が多くて線形探索(1から値を見ていく)は使いたくない、使えないとき。
  • 総当りする対象がソートできそうなとき。(intでもstrでも)  

どういう仕組み？

すみません。他の記事を参照ください。。

  • 最初に見る

www.youtube.com

  • わかりやすい解説

qiita.com

  • 文字列でソートした配列を二分探索する

qiita.com

pythonによる実装

20個のランダムな数字の配列を作り、その中からランダムな数字ひとつの位置を導出する処理を書いてみました。

import random


array = [random.randint(0,1000) for i in range(20)]
search = array[0]
array.sort()

l = -1
r = 20

while abs(l-r) != 1:
    mid = abs(l+r)//2
    print('array:', array,'/ search:',search,'/ mid:',mid,'/ l:',l,'/ r:',r)
    if search < array[mid]:
        l = mid
    elif search >= array[mid]:
        r = mid

print(array[mid],mid)

動かしてみるとどういう動きをするのか追えると思います。

//1回目
array: [11, 29, 75, 79, 153, 187, 308, 371, 375, 384, 398, 425, 565, 598, 667, 713, 778, 803, 807, 820] / search: 778 / mid: 9 / l: -1 / r: 20
array: [11, 29, 75, 79, 153, 187, 308, 371, 375, 384, 398, 425, 565, 598, 667, 713, 778, 803, 807, 820] / search: 778 / mid: 4 / l: -1 / r: 9
array: [11, 29, 75, 79, 153, 187, 308, 371, 375, 384, 398, 425, 565, 598, 667, 713, 778, 803, 807, 820] / search: 778 / mid: 1 / l: -1 / r: 4
array: [11, 29, 75, 79, 153, 187, 308, 371, 375, 384, 398, 425, 565, 598, 667, 713, 778, 803, 807, 820] / search: 778 / mid: 0 / l: -1 / r: 1
11 0

//2回目
array: [5, 121, 138, 231, 231, 294, 296, 312, 384, 414, 450, 476, 486, 551, 555, 580, 633, 639, 721, 781] / search: 121 / mid: 9 / l: -1 / r: 20
array: [5, 121, 138, 231, 231, 294, 296, 312, 384, 414, 450, 476, 486, 551, 555, 580, 633, 639, 721, 781] / search: 121 / mid: 14 / l: 9 / r: 20
array: [5, 121, 138, 231, 231, 294, 296, 312, 384, 414, 450, 476, 486, 551, 555, 580, 633, 639, 721, 781] / search: 121 / mid: 17 / l: 14 / r: 20
array: [5, 121, 138, 231, 231, 294, 296, 312, 384, 414, 450, 476, 486, 551, 555, 580, 633, 639, 721, 781] / search: 121 / mid: 18 / l: 17 / r: 20
array: [5, 121, 138, 231, 231, 294, 296, 312, 384, 414, 450, 476, 486, 551, 555, 580, 633, 639, 721, 781] / search: 121 / mid: 19 / l: 18 / r: 20
781 19

ABC 146 C - Buy an Integer

整数屋さん。
ABC146当日は、この問題を見て二分探索を使えば解けることにすぐ気づかなかったんですよねー。
最大値を求める＝式の条件を満たす値を探すという思考が無かったんですね。

a, b, x = map(int,input().split())

l = -1
r = 10 ** 9 + 1

ans = 0

while abs(l-r) != 1:
    n = abs(l+r)//2
    tmp = a * n + b * len(str(n))
    if tmp == x:
        ans = n
        break
    elif tmp < x:
        l = n
        ans = n
    elif tmp > x:
        r = n

print(ans)

雑記

作者はてんぷら(@tempura_cpp)さんという方ですね。

twitter.com

まとめ

手軽にブログ投稿がんばるぞ。