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

## 第10章 データ構造（3）グラフと木 10.4まで

- 任意参加
- ファシリテーター: 大倉

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

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=teruya]

無向グラフ（重みなし）を使ったDPの問題
https://atcoder.jp/contests/abc021/tasks/abc021_c

MOD = 10 ** 9 + 7
n = gets.to_i
start, goal = gets.split.map(&:to_i)
m = gets.to_i
edges = []
m.times { edges << gets.split.map(&:to_i) }
graph = Array.new(n + 1) { Array.new }
edges.each do |from, to|
  graph[from] << to
  graph[to] << from
end

graph.each_with_index do |n, i|
  puts "#{i}の接続先:#{n}"
end
# 0の接続先:[]
# 1の接続先:[2, 3]
# 2の接続先:[1, 4]
# 3の接続先:[1, 4]
# 4の接続先:[2, 3, 5, 6]
# 5の接続先:[4, 7]
# 6の接続先:[4, 7]
# 7の接続先:[5, 6]

# dp[step数][町] に何通りの最短経路があるか
dp = Array.new(n + 1) { Array.new(n + 1, 0) }

# 0 step 目は、スタート地点に 1 通りの最短経路
dp[0][start] = 1

1.upto(n) do |step|
  1.upto(n) do |from|
    graph[from].each do |to|
      dp[step][to] += dp[step - 1][from]
    end
  end
  if dp[step][goal] > 0
    puts dp[step][goal] % MOD
    break
  end
end

無向グラフ（重み付き）を使った問題
https://atcoder.jp/contests/abc070/tasks/abc070_d

#tree 木
INF = 1_000_000_000_000_000
n = gets.to_i
edges = []
(n - 1).times { edges << gets.split.map(&:to_i) }
graph = Array.new(n + 1) { Array.new }
# 無向グラフなので両始点のグラフに入れる
edges.each do |f, t, w|
  graph[f] << [f, t, w]
  graph[t] << [t, f, w]
end

q, k = gets.split.map(&:to_i)
weights = Array.new(n + 1) { INF }
queue = [[k, k, 0]]

until queue.empty?
  from, to, weight = queue.shift
  weights[to] = [weight, weights[to]].min
  graph[to].each do |f, t, w|
    # 逆流しないようにする（両方のグラフに入れているので必ず1つ該当する）
    next if t == from
    queue << [f, t, w + weight]
  end
end

queries = []
q.times { queries << gets.split.map(&:to_i) }

queries.each do |from, to|
  puts weights[from] + weights[to]
end

>[name=okura]

### 10.1 グラフ

単語が難しいのは数学あるある…
現実世界では有向かつ重み付きのグラフが多そう（例えば山を登るルートで一番楽なルートを考えると、登りと下りで大変さが違うので有向、各ルートでも大変さが違うので重み付き）

### 10.2 グラフを用いる定式化の例

将棋のAIでも、評価関数とグラフ探索を組み合わせているんじゃなかったかな。そっちは深層学習のほうが強くて廃れてしまったかもしれないけど…

### 10.3 グラフの実装

Rubyで書いてみるのはやっていないけど、そんなに難しくはなさそう。

`vector<vector<int>>`はRubyだと`[[]]`

### 10.4 重み付きグラフの実装

頂点に対して、「接している頂点の集合」だと重みを表現できないのでEdgeオブジェクトを使うってことなんですね。

### おまけ

https://www.ruby-toolbox.com/categories/graphing
Rubyでグラフを数学的にどうこうするツールはあまりないっぽいけど、C言語とかで実装したやつのほうが速いからそれはそうかも。
https://docs.ruby-lang.org/ja/latest/class/Matrix.html
あるいは`Matrix`を使うのかな。

>[name=tsujita]

- 理解するのに精一杯で書くことがあまりないのですが・・・・
- code 10.2 入力データ1行目が`8 13`でなく`8 12`と気づいたくらいにはちゃんと読みました

## 振り返り

>[name=teruya]

競プロやってる時はグラフを1から書くわけではなくて適当なところからコピってきていじってます😂

>[name=okura]

動的計画法をもうちょっと手に馴染ませたい。

>[name=tsujita]

DPがやっぱり難しいですね・・・・・

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- tsujitaさん
- 読む範囲を決める
- 10.9まで