# 問題解決力を鍛える！アルゴリズムとデータ構造
## 第6章

- 6.3〜を読む
- 任意参加
- ファシリテーター: teruya

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所

>[name=chen]

const N = 8
const h = [10,5,12,35,67,88,23,42]
const s = [2,1,3,5,3,4,1,6]
let t = [0,0,0,0,0,0,0,0]

let left = 0
let right = 100

while(right - left > 1){
  let mid = (left + right) / 2
  let ok = true
  for(let i = 0 ; i < N ; i++){
    // そもそもmidが初期高度より低かったらfalse
    if(mid < h[i]) ok = false
    else t[i] = Math.round((mid - h[i]) / s[i])
  }
  
  console.log('t = ' + t + ', mid = ' + mid)
  t.sort(function (a, b) { return a - b })
  
  for(let i = 0 ; i < N ; i++){
    // 時間切れ発生
    if(t[i] < i) ok = false
  }
  
  if(ok) right = Math.round(mid)
  else left = Math.round(mid)
}

console.log("right = " + right)
console.log("left = " + left)


// "t = 20,45,13,3,0,0,27,1, mid = 50"
// "t = 33,70,21,8,3,20,52,6, mid = 75"
// "t = 39,83,25,11,7,33,65,8, mid = 87.5"
// "t = 42,89,27,12,9,2,71,9, mid = 94"
// "t = 41,86,26,11,8,1,68,8, mid = 91"
// "t = 40,85,26,11,8,0,67,8, mid = 89.5"
// "t = 40,84,26,11,7,0,66,8, mid = 89"
// "right = 89"
// "left = 88"

>[name=teruya]

https://atcoder.jp/contests/abc023/tasks/abc023_d

# 全体でO(NlogN)
def can_score?(score, height_and_speeds)
  # O(N)
  left_times = height_and_speeds.map do |height, speed|
                 # 例えばscore(20点)を取りたい時、height（5m）なら、rest_height(15m上昇してもセーフ)となる
                 rest_height = score - height
                 # speed(6)の時、2秒後は17mなのでセーフ、3秒後は23mなのでアウト
                 # なので rest_height(15) / speed(6) = 2 を返す
                 rest_height / speed
               end

  # O(NlogN)、ここがボトルネックのオーダー数
  # scoreを獲得するためのleft_timeが少ない順（余裕がない順）にソート
  left_times.sort!
  puts "score: #{score} を取るためには、それぞれ何秒後までに風船を割れば良いか？↓"
  p left_times

  # O(N)
  # 実際に先頭から順に風船を割っていき、left_timeを超えてしまった風船が1つでもあればfalse
  can_score = true
  left_times.each_with_index do |left_time, order|
    can_score = false if left_time < order
  end

  puts "score: #{score} を取ることができるか？ #{can_score}"
  puts
  can_score
end

M = 1_000_000_000 * 100_000
n = gets.to_i
# 風船の高さと上昇するスピード
# [[5, 6], [12, 4], [14, 7], [21, 2]]
height_and_speeds = []
n.times { height_and_speeds << gets.split.map(&:to_i) }

# 二分探索はO(logM)
# 全体でO(NlogNlogM) 100_000 * 15 * 40 みたいなイメージ
least_score = (0..M).bsearch { |score| can_score?(score, height_and_speeds) }

puts least_score

>[name=tsujita]

left = 20
right = 36

while (right - left) > 1 do
  mid = left + (right - left) / 2
  puts "Is the age less than #{mid} ? (yes / no)"
  answer = gets.chomp

  if answer == 'yes'
    right = mid
  else
    left = mid
  end
end

puts "The age is #{left} !"

## 振り返り

>[name=chen]

うんん...どれの風船か先に打たれる判定が難しいですね :thinking_face:

>[name=teruya]

`Array#bsearch`便利すぎる

さりげなく使ったけど今日は`Range#bsearch`を使いました

>[name=tsujita]

動的計画法で鍛えられてました

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- 大倉さん
- 読む範囲を決める
- 第７章　貪欲法