# 問題解決力を鍛える！アルゴリズムとデータ構造 ## 第5章 - 任意参加 - ファシリテーター: ### 話す・書く順番決めルーレット in Ruby ```ruby ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" } ``` in JavaScript ```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] #### 5.3.1 緩和 >緩和処理の順序のポイント：頂点 u から頂点 v へと遷移する辺に関する緩和処理を成立させるためには，dp[u] の値が確定していることが必要です． 緩和処理は、この章の重点だと思います。 緩和処理をすれば大きな問題が小さい問題になっていて処理しやすくなる気がします。→ プログラミングの原則かな？w #### 5.4 動的計画法の例(1)：ナップサック問題 > 今回のナップサック問題でも，0, 1, ..., i－1 番目の品物からいくつか選んだ後に，i 番目の品物を「選ぶ」「選ばない」という２通りの選択肢があります．このような，「各段階においていくつかの選択肢が存在する」という状況... パッと見ると解き方はよくわからなくてどうすればよいのか思いつかないけど... 「選ぶ」と「選ばない」の二つ選択肢に解析したら解決策が出てきます。 #### 5.5 動的計画法の例 (2)：編集距離 > 編集距離を求める動的計画法：dp[i][j]←S の最初の i 文字分と，T の最初の j 文字分との間の編集距離 最初、これはちょっと難しいなと思っていますが、 変更／削除／挿入で対応すれば、すぐ理解できることになりました。 なるほと！という感じでした。 #### 5.6　動的計画法の例 (3)：区間分割の仕方を最適化 解析方法は理解できるけどコストの計算法がちょっとわからないですね．．．:thinking_face: >[name=okura] ### 5.1 動的計画法とは https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95 メモ化と部分問題への分割の組み合わせで、メモリ空間を犠牲に時間を短縮するのが動的計画法、と理解した。あとは最小と最小を組み合わせたら最小になる的な。 ```javascript= const input = [2,9,4,5,1,6,10] const dp = [] input.forEach((item, index) => { if(index === 0) { dp.push(0) } else if(index === 1) { dp.push(Math.abs(input[index - 1] - item)) } else{ dp.push(Math.min(dp[index - 1] + Math.abs(input[index - 1] - item), dp[index - 2] + Math.abs(input[index - 2] - item))) } }) console.log(dp[input.length - 1]) ``` >[name=teruya] >[name=tsujita] ```ruby= heights = [2, 9, 4, 5, 1, 6, 10] dp = Array.new(7) dp[0] = 0 (1..6).each do |i| if i == 1 dp[1] = (heights[0] - heights[1]).abs else one_step_cost = dp[i - 1] + (heights[i - 1] - heights[i]).abs two_step_cost = dp[i - 2] + (heights[i - 2] - heights[i]).abs dp[i] = [one_step_cost, two_step_cost].min end end puts dp ``` https://atcoder.jp/contests/dp/tasks/dp_a - 動的計画法（DP） ## 振り返り > [name=chen] 読みすぎたwwww が、ペアプロが楽しくて面白かったです。 > [name=okura] 「直前のメモ化の結果を参照する」のが肝なのかなあと思った。 今回の問題だと、`dp`配列は実は3要素で大丈夫だったりするのかな？（そしてメモリ消費量を減らせる？） https://ruby-jp.slack.com/archives/CLRQR3CCB/p1672116927584239 `min`より三項演算子のほうが速い ```ruby= pp RubyVM::InstructionSequence.compile("[1,2].min").disasm pp RubyVM::InstructionSequence.compile("1 > 2 ? 1 : 2").disasm require 'benchmark/ips' a = [1, 2] Benchmark.ips do |x| x.report(:min) { a.min } x.report(:trinary) { 1 < 2 ? 1 : 2 } x.compare! end ``` >[name=teruya] 初めてDPやった時は、これ考えた人天才すぎでは……………と思いました >[name=tsujita] ペアプロ楽しかったです ## 終了後ファシリテーターがやること - 次回のファシリテーターを決める - tsujita - 読む範囲を決める - 5.3と5.4