paiza プログラミング

[Ruby]paiza クラス・構造体メニュー スーパースーパースーパーカー (paizaランク A 相当)の解説

super_car

こんにちは！じゃいごテックのあつしです。

今回はpaiza クラス・構造体メニュー からSTEP4: スーパースーパースーパーカーという問題を解説します。

この問題集はクラスの応用的な使い方に関する4個のSTEP問題(B~A級)とFINAL問題(A級)で構成されていて、STEP問題を解いて行けばFINAL問題も解けるはず！となっています。

STEP4: スーパースーパースーパーカー (paizaランク A 相当)を解いてみる

※ paizaレベルアップ問題集 クラス・構造体メニューより

問題

よくクラスの題材を扱う際に、「クラスは車の設計書」といった例が出てきます。
スーパーカー販売店に勤務しながらクラスの勉強をしていた paiza 君はスーパーカーの走る様子をクラスを用いてシミュレーションしてみようと考えました。
ただ車を走らせてもつまらないので、陸を走るスーパーカーに加えて、空を飛べるスーパースーパーカー ・ テレポートできるスーパースーパースーパーカー もシミュレーションに加えた
番号 1 〜 N の N 台のシミュレーションをすることにしました。

それぞれの車について、初めに入っている燃料の量 l と燃費 f が定まっており、加えて、車種に応じて次のような機能を持ちます。

  • スーパーカー
    • run
      燃料を 1 消費し、 f (km) 走る。
      燃料が 0 の場合は何も起こらない。
  • スーパースーパーカー
    • run
      燃料を 1 消費し、 f (km) 走る。
      燃料が 0 の場合は何も起こらない。
    • fly
      燃料を 5 消費し、 f^2 (km) 飛行する。
      燃料が 5 未満の場合は run を行う。
  • スーパースーパースーパーカー
    • run
      燃料を 1 消費し、 f (km) 走る。
      燃料が 0 の場合は何も起こらない。
    • fly
      燃料を 5 消費し、 2 * f^2 (km) 飛行する。
      燃料が 5 未満の場合は run を行う。
    • teleport
      燃料を f^2 消費し、 f^4 (km) 移動する。
      燃料が f^2 未満の場合は fly を行う。

シミュレートする車の台数 N と機能を使う回数 K , N 台の車の車種と機能を使った車の番号と使った機能が与えられるので、全てのシミュレーションが終わった後の、各車ごとの総移動距離を求めてください。

入力される値

N K
k_1 l_1 f_1
...
k_N l_N f_N
n_1 func_1
...
n_K func_K

  • 1 行目では、シミュレートする車の台数 N と機能を使う回数 K が半角スペース区切りで与えられます。
  • 続く N 行のうち i 行目(1 ≦ i ≦ N)では、 i 番の車の種類 k_i , 初めに入っている燃料 l_i , 燃費 f_i が半角スペース区切りで与えられます。
  • 続く K 行では、車の番号 n_i と、使用するその車の機能 func_i が時系列順に与えられます。

入力値最終行の末尾に改行が１つ入ります。

期待する出力

全てのシミュレーションを終えたときの i 番の車の総移動距離 len_i を以下の形式で全ての車について出力してください。

len_1
...
len_N

条件

  • 与えられる値は全て整数
  • 1 ≦ N , K ≦ 10^5
  • k_i (1 ≦ i ≦ N) は "supercar","supersupercar","supersupersupercar" のいずれか
  • 1 ≦ l_i ≦ 10^5 , 1 ≦ f_i ≦ 100(1 ≦ i ≦ N)
  • 1 ≦ n_i ≦ N (1 ≦ i ≦ K)
  • func_i (1 ≦ i ≦ K) は "run" , "fly" , "teleport" のいずれか
  • 未定義の機能が呼び出されることはないことが保証されている
入力例1
3 6
supercar 1 1
supersupercar 10 10
supersupersupercar 100 5
1 run
2 run
2 fly
3 run
3 fly
3 teleport
出力例1
1
110
680
入力例2
5 10
supersupercar 1102 67
supersupercar 63296 25
supersupersupercar 47388 32
supersupercar 30968 68
supersupercar 53668 78
2 run
3 teleport
1 fly
2 run
4 run
5 fly
5 run
2 fly
4 run
1 fly
出力例2
8978
675
1048576
136
6162
攻略ポイント

ポイント

  • SuperCarクラスを定義する
    • runメソッドを定義
  • SuperCarクラスを継承したSuperSuperCarクラスを定義する
    • flyメソッドを定義
  • SuperSuperCarクラスを継承したSuperSuperSuperCarクラスを定義する
    • flyメソッドをオーバーライドする
    • teleportメソッドを定義

参考記事

クラス

メソッドの定義と呼び出し

標準入力・標準出力

問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  3 6
  supercar 1 1
  supersupercar 10 10
  supersupersupercar 100 5
  1 run
  2 run
  2 fly
  3 run
  3 fly
  3 teleport
EOS
OUTPUT1 = <<~"EOS"
  1
  110
  680
EOS

INPUT2 = <<~"EOS"
  5 10
  supersupercar 1102 67
  supersupercar 63296 25
  supersupersupercar 47388 32
  supersupercar 30968 68
  supersupercar 53668 78
  2 run
  3 teleport
  1 fly
  2 run
  4 run
  5 fly
  5 run
  2 fly
  4 run
  1 fly
EOS
OUTPUT2 = <<~"EOS"
  8978
  675
  1048576
  136
  6162
EOS

pp INPUT1
# > "3 6\n" +
# > "supercar 1 1\n" +
# > "supersupercar 10 10\n" +
# > "supersupersupercar 100 5\n" +
# > "1 run\n" +
# > "2 run\n" +
# > "2 fly\n" +
# > "3 run\n" +
# > "3 fly\n" +
# > "3 teleport\n"
p OUTPUT1
# > "1\n110\n680\n"
pp INPUT2
# > "5 10\n" +
# > "supersupercar 1102 67\n" +
# > "supersupercar 63296 25\n" +
# > "supersupersupercar 47388 32\n" +
# > "supersupercar 30968 68\n" +
# > "supersupercar 53668 78\n" +
# > "2 run\n" +
# > "3 teleport\n" +
# > "1 fly\n" +
# > "2 run\n" +
# > "4 run\n" +
# > "5 fly\n" +
# > "5 run\n" +
# > "2 fly\n" +
# > "4 run\n" +
# > "1 fly\n"
p OUTPUT2
# > "8978\n675\n1048576\n136\n6162\n"

続いてSuperCarクラス・SuperSuperCarクラス・SuperSuperSuperCarクラスと問題を解くsolveメソッドを変数の下に定義します。

まず、SuperCarクラス・SuperSuperCarクラス・SuperSuperSuperCarクラスを定義します。

SuperCarクラス

  • インスタンス変数
    • 燃料 @fuel : Integer
    • 燃費 @gas_mileage : Integer
    • 走行距離 @mileage : Integer（外部から参照可）
  • initializeメソッド
    • initialize(fuel, gas_mileage)
      • @fuel を fuel で初期化する
      • @gas_mileage を gas_mileage で初期化する
      • @mileage を 0 で初期化する
  • インスタンスメソッド
    • run
      • @fuelが0なら何もしない
      • @fuelが1以上なら
        • @fuel から 1 を引く
        • @mileage に @gas_mileage を加える

SuperSuperCarクラス（SuperCarクラスを継承）

  • インスタンスメソッド
    • fly
      • @fuelが5未満なら
        • runメソッドを実行する
      • @fuelが5以上なら
        • @fuel から 5 引く
        • @mileage に @gas_mileage ** 2 を加える

SuperSuperSuperCarクラス（SuperSuperCarクラスを継承）

  • インスタンスメソッド
    • fly
      • @fuelが5未満なら
        • runメソッドを実行する
      • @fuelが5以上なら
        • @fuel から 5 を引く
        • @mileage に 2 * @gas_mileage ** 2 を加える
    • teleport
      • @fuelが@gas_mileage ** 2未満なら
        • flyメソッドを実行する
      • @fuelが @gas_mileage ** 2 以上なら
        • @fuel から @gas_mileage ** 2 を引く
        • @mileage に @gas_mileage ** 4 を加える
class SuperCar
  attr_reader :mileage

  def initialize(fuel, gas_mileage)
    @fuel = fuel
    @gas_mileage = gas_mileage
    @mileage = 0
  end

  def run
    return if @fuel == 0
    @fuel -= 1
    @mileage += @gas_mileage
  end
end

class SuperSuperCar < SuperCar
  def fly
    if @fuel < 5
      return run
    end
    @fuel -= 5
    @mileage += @gas_mileage ** 2
  end
end

class SuperSuperSuperCar < SuperSuperCar
  def fly
    if @fuel < 5
      return run
    end
    @fuel -= 5
    @mileage += 2 * @gas_mileage ** 2
  end

  def teleport
    if @fuel < @gas_mileage ** 2
      return fly
    end
    @fuel -= @gas_mileage ** 2
    @mileage += @gas_mileage ** 4
  end
end

# SuperCar の確認
scar = SuperCar.new(1, 10)
p scar.run
# > 10

# 燃料なし
p scar.run
# > nil

p scar.mileage
# > 10
puts

#SuperSuperCar の確認
sscar = SuperSuperCar.new(6, 10)
p sscar.fly
# > 100
p sscar.fly
# > 110
p sscar.fly
# > nil
p sscar.mileage
# > 110
puts

#SuperSuperSuperCar の確認
ssscar = SuperSuperSuperCar.new(106, 10)
p ssscar.teleport
# > 10000
p ssscar.teleport
# > 10200
p ssscar.teleport
# > 10210
p ssscar.teleport
# > nil
p ssscar.mileage
# > 10210

クラスの動作が良さそうなら、確認用コードを削除してSuperSuperSuperCarクラスの下にsolveメソッドを記述していきます。

まず、入力データを受け取る処理を書きます。

def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k = input_lines.shift.split.map(&:to_i)
  cars = input_lines.shift(n).map do |car_params|
    car_type, *params = car_params.split
    params.map!(&:to_i)
    [car_type, *params]
  end
  requests = input_lines.shift(k).map do |drive_params|
    car_no, drive_type = drive_params.split
    [car_no.to_i, drive_type]
  end

  # 確認用コード
  [cars, requests]
end

# 確認用コード
pp solve(INPUT1)
# > [[["supercar", 1, 1],
# >   ["supersupercar", 10, 10],
# >   ["supersupersupercar", 100, 5]],
# >  [[1, "run"], [2, "run"], [2, "fly"], [3, "run"], [3, "fly"], [3, "teleport"]]]
pp solve(INPUT2)
# > [[["supersupercar", 1102, 67],
# >   ["supersupercar", 63296, 25],
# >   ["supersupersupercar", 47388, 32],
# >   ["supersupercar", 30968, 68],
# >   ["supersupercar", 53668, 78]],
# >  [[2, "run"],
# >   [3, "teleport"],
# >   [1, "fly"],
# >   [2, "run"],
# >   [4, "run"],
# >   [5, "fly"],
# >   [5, "run"],
# >   [2, "fly"],
# >   [4, "run"],
# >   [1, "fly"]]]

データが正しく受け取れていれば、solve メソッドに処理を追加していきます。

  • 配列carsの先頭から順にインスタンス化した配列で上書きします。
  • 配列requestsの値に従って指定されたcarsのメソッドを実行します。
  • 実行後、配列carsのmileage を配列をresultに格納します。
def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k = input_lines.shift.split.map(&:to_i)
  cars = input_lines.shift(n).map do |car_params|
    car_type, *params = car_params.split
    params.map!(&:to_i)
    [car_type, *params]
  end
  requests = input_lines.shift(k).map do |drive_params|
    car_no, drive_type = drive_params.split
    [car_no.to_i, drive_type]
  end

  # cars をインスタンス化して上書き
  cars.map! do |car_type, fuel, gas_mileage|
    case car_type
    when "supercar"
      SuperCar.new(fuel, gas_mileage)
    when "supersupercar"
      SuperSuperCar.new(fuel, gas_mileage)
    when "supersupersupercar"
      SuperSuperSuperCar.new(fuel, gas_mileage)
    end
  end

  # requests に従って cars を進める
  requests.each do |car_no, drive_type|
    cars[car_no - 1].public_send(drive_type)
  end

  # cars の 各要素の mileage を配列 result に格納する
  result = cars.map { |car| car.mileage }

  result
end

# 確認用コード
pp solve(INPUT1)
# > [1, 110, 680]
p solve(INPUT1) == OUTPUT1
# > false
pp solve(INPUT2)
# > [8978, 675, 1048576, 136, 6162]
p solve(INPUT2) == OUTPUT2
# > false

後は出力形式を整えれば完成です。
p solve(INPUT1) == OUTPUT1 -> true を確認するために、配列resultを改行で連結して末尾に改行を加えます。

def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k = input_lines.shift.split.map(&:to_i)
  cars = input_lines.shift(n).map do |car_params|
    car_type, *params = car_params.split
    params.map!(&:to_i)
    [car_type, *params]
  end
  requests = input_lines.shift(k).map do |drive_params|
    car_no, drive_type = drive_params.split
    [car_no.to_i, drive_type]
  end

  # cars をインスタンス化して上書き
  cars.map! do |car_type, fuel, gas_mileage|
    case car_type
    when "supercar"
      SuperCar.new(fuel, gas_mileage)
    when "supersupercar"
      SuperSuperCar.new(fuel, gas_mileage)
    when "supersupersupercar"
      SuperSuperSuperCar.new(fuel, gas_mileage)
    end
  end

  # requests に従って cars を進める
  requests.each do |car_no, drive_type|
    cars[car_no - 1].public_send(drive_type)
  end

  # cars の 各要素の mileage を配列 result に格納する
  result = cars.map { |car| car.mileage }

  # 要素を改行で連結し末尾に改行を加える
  result.join("\n") << "\n"
end

# 確認用コード
pp solve(INPUT1)
# > "1\n" + "110\n" + "680\n"
p solve(INPUT1) == OUTPUT1
# > true
pp solve(INPUT2)
# > "8978\n" + "675\n" + "1048576\n" + "136\n" + "6162\n"
p solve(INPUT2) == OUTPUT2
# > true

入出力例での動作確認が出来ましたので、標準入力からのデータ受け取りに変更して、手動で動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)

解答コード
class SuperCar
  attr_reader :mileage

  def initialize(fuel, gas_mileage)
    @fuel = fuel
    @gas_mileage = gas_mileage
    @mileage = 0
  end

  def run
    return if @fuel == 0
    @fuel -= 1
    @mileage += @gas_mileage
  end
end

class SuperSuperCar < SuperCar
  def fly
    if @fuel < 5
      return run
    end
    @fuel -= 5
    @mileage += @gas_mileage ** 2
  end
end

class SuperSuperSuperCar < SuperSuperCar
  def fly
    if @fuel < 5
      return run
    end
    @fuel -= 5
    @mileage += 2 * @gas_mileage ** 2
  end

  def teleport
    if @fuel < @gas_mileage ** 2
      return fly
    end
    @fuel -= @gas_mileage ** 2
    @mileage += @gas_mileage ** 4
  end
end

def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k = input_lines.shift.split.map(&:to_i)
  cars = input_lines.shift(n).map do |car_params|
    car_type, *params = car_params.split
    params.map!(&:to_i)
    [car_type, *params]
  end
  requests = input_lines.shift(k).map do |drive_params|
    car_no, drive_type = drive_params.split
    [car_no.to_i, drive_type]
  end

  # cars をインスタンス化して上書き
  cars.map! do |car_type, fuel, gas_mileage|
    case car_type
    when "supercar"
      SuperCar.new(fuel, gas_mileage)
    when "supersupercar"
      SuperSuperCar.new(fuel, gas_mileage)
    when "supersupersupercar"
      SuperSuperSuperCar.new(fuel, gas_mileage)
    end
  end

  # requests に従って cars を進める
  requests.each do |car_no, drive_type|
    cars[car_no - 1].public_send(drive_type)
  end

  # cars の 各要素の mileage を配列 result に格納する
  result = cars.map { |car| car.mileage }

  # 要素を改行で連結し末尾に改行を加える
  result.join("\n") << "\n"
end

puts solve(STDIN.read)

今回のまとめ

クラスの継承とオーバーライドを使って問題を解きました。

  • スーパークラスの特性を流用してサブクラスの差分を定義すると記述量が少なくて済む
  • スーパークラスのインスタンスメソッドをオーバーライドすることによって同じメソッド名でも異なった処理ができる（ポリモーフィズム）

今回は継承とオーバーライドの復習問題でした！


【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。





通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。


プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。


プログラミングコンテストチャレンジブック第2版 問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者～中級者向けに書かれているので解説が非常に丁寧です。


最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋 直大 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤 弘毅 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング

-paiza, プログラミング
-, , , ,

© 2024 じゃいごテック