読者です 読者をやめる 読者になる 読者になる

po

pay

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder

チーターの本に似た問題が載ってます。*1

問題概要

給料が次のように決まる。

  • 部下がいるとき、1+(直接の部下たちの給料の)最大値+最小値
  • 部下がいないとき、1

直接の部下は複数いることもあるが、直接の上司はちょうど1人しかいない。社長(全社員の上司)の給料を求めよ。

解き方

(直接の)上司・部下の関係になってる2人の間に辺を張ればグラフになります(社長を根にした木になります)。あとは、問題文のとおりに各社員(頂点)の給料を計算すればよいです。具体的には、ある社員の給料を決定するときはその社員を部分的な社長(?)と考えます。つまり、その社員の上司たちの存在は考えなくていいです。また、1番に給料が決定する社員は木の葉にあたる社員たちです。

以上のことから、再帰を使って書けば簡単になりそうです。ちょっと考えると、ループを使っても書けるようです(解説スライドを参照)。

解答例

ABC 026-C 高橋君の給料

文法について

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+1
    • ary.maxで配列内の最大値を返す。
  • puts rec 0
    • putsは改行までする。

おわりに

ループの書き方が色々ありますね。

参考

たくさん

*1:この本はめっちゃ簡単なところから始まるので良いです。ただ、Topcoderの使い方がむずすぎます。