ただのメモ

他の人に見せても良い方のメモ

Competitive Programing Typical 90 Problem day1

I decided to solve 1 problem 1 day to acquire programming skill.

 

Binary Search

N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split())) + [L]

def greedy_cut_try(xthreshold):
  temp = 0
  now_cut_num = 0
  end_point = -1
  for i in range(N):
    #N-1までなのは、切れ目が
    if x[i] - temp >= threshold: 
      #切ったものが閾値を超えていたら
      temp = x[i]
      #細切れは手元にない
      now_cut_num += 1
      #切った回数を記憶
    else:
      pass
      #まだ切らない
        
    if now_cut_num == K:
      break
      #K回切ったら終わり
  if now_cut_num == K and L - temp >= threshold:
    return 1
    #K回切れていて 最後の切れ端も閾値を超える
  else:
    return 0


def binary_search(x):
  #二分探索、解が一直線上にあり、有界
  l = 0
  r = L
  #上限と下限を指定する
  while r - l > 1:
    mid = int((l+r)/2)
    #中点を取って
    if greedy_cut_try(x, mid) == 1:
      l = mid
    else:
      r = mid
    #更新していく

  return l

def main():
  score = binary_search(A)
  print(score)

main()
  • 二分探索の気持ちは、境界を決めましょう、ということ。
    • そして、観測区間を2分することで、解像度を上げましょう、ということ。
  • 境界の片方では、成り立ち、もう片方では、成り立たない、というものを考えるときに使える。
  • 最大、最小、といった考え方は、上限、下限、という考え方と繋がりがある。
  • つまり、そこが、境界となる。よって、二分探索にもってこいである。
  • 似た話では、限界、というのは、境界のことであると言える
  • 生体内に投与できる物質Xの量の限界(最大値)を求めたいとき、こういう二分探索を使うと、費用や時間を節約出来て、良いかもしれない。
    • ただし、その結果を見てから、次を行う、ということをしているので、一気に出来るわけではない。これは弱点かもしれない