pay
C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder
問題概要
給料が次のように決まる。
- 部下がいるとき、１＋（直接の部下たちの給料の）最大値＋最小値
- 部下がいないとき、１
直接の部下は複数いることもあるが、直接の上司はちょうど１人しかいない。社長（全社員の上司）の給料を求めよ。
解き方
（直接の）上司・部下の関係になってる２人の間に辺を張ればグラフになります（社長を根にした木になります）。あとは、問題文のとおりに各社員（頂点）の給料を計算すればよいです。具体的には、ある社員の給料を決定するときはその社員を部分的な社長(?)と考えます。つまり、その社員の上司たちの存在は考えなくていいです。また、１番に給料が決定する社員は木の葉にあたる社員たちです。
以上のことから、再帰を使って書けば簡単になりそうです。ちょっと考えると、ループを使っても書けるようです（解説スライドを参照）。
解答例
文法について
rubyの文法についてのメモです。
@g=Array.new(n){[]}Array.new(n){0}でサイズがnで各要素が0の配列になる。[]は空配列を返す。@はrec内からgを使えるようにするために必要。
(n-1).times do |i|(n-1).times doでn-1回のループをするが、|i|を書くとループごとに0からインクリメントされる。
@g[b-1]<< i+1- vectorにpushする感じ。
def rec i- 関数の括弧は省略できる。
@g[i].each do |j|ary.each do |j|で配列から要素を取ってきてjに入れてループする。
s.max+s.min+1ary.maxで配列内の最大値を返す。
puts rec 0putsは改行までする。
おわりに
ループの書き方が色々ありますね。
参考
たくさん
