paiza プログラミング

[Ruby]paiza クラス・構造体メニュー ロボットの暴走 (paizaランク A 相当)の解説

robot

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

今回はpaiza クラス・構造体メニュー の最終問題、ロボットの暴走を解説します。
クラス・構造体メニューのFINAL問題ということで、STEP問題に出てきたテクニックを駆使して解く問題となっています。

FINAL: ロボットの暴走 (paizaランク A 相当)を解いてみる

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

問題

ロボットの暴走問題_図

paiza 株式会社では、物品の管理のために上の図のような座標系の広さが無限大のマスの工場 で 番号 1 〜 N が割り当てられた N 台のロボットを運用していました。ところがある日、全てのロボットが暴走してしまいました。各ロボットは性能ごとにレベル分けされており、次の通り移動距離が決まっています。

Lv1 : 特定の方角に 1 マス進む
Lv2 : 特定の方角に 2 マス進む
Lv3 : 特定の方角に 5 マス進む
Lv4 : 特定の方角に 10 マス進む

また、工場のマスのうち 10 マスには工具箱が置かれており、移動後にそのマスにロボットがぴったり止まっていた場合、そのロボットのレベルが 1 上がってしまいます（最大レベルは 4)。
レベル l のロボットの初期位置が工具箱の置かれているマスであったとしても、そのロボットのレベルは l で始まることに気をつけてください。

幸い、初めにロボットがいる範囲や工具箱の置かれているマス、各ロボットの位置とレベル、また、どのロボットがどのような順番でどの方角に移動するかの情報はわかっているので、ロボットの移動が K 回終わったときの各ロボットの位置とレベルを推定してください。

入力される値

H W N K
lx_1 ly_1
...
lx_10 ly_10
x_1 y_1 l_1
...
x_N y_N l_N
r_1 d_1
...
r_K d_K
  • 1 行目では ロボットの初期位置の y , x 座標の上限についての整数 H , W , ロボットの数 N , ロボットの移動回数 K が半角スペース区切りで与えられます。
  • 続く 10 行のうち i 行目では、i 個目の工具箱が置かれたマスの x , y 座標 x_i , y_i が与えられます。(1 ≦ i ≦ 10)
  • 続く N 行のうち i 行目では、 番号 i のロボットの初期位置の x 座標 x_i , y 座標 y_i , レベル l_i が半角スペース区切りで与えられます。
  • 続く K 行のうち i 行目では、 i 回目の移動を行ったロボットの番号 r_i と移動の方角 d_i が与えられます。

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

期待する出力

i 番のロボットの最終的な位置 x_i , y_i とレベル l_i を i 行目に出力してください。

x_1 y_1 l_1
...
x_N y_N l_N

条件

  • 5 ≦ H , W , N , K ≦ 10^5
  • 0 ≦ lx_i < W , 0 ≦ ly_i < H (1 ≦ i ≦ 10)
  • 0 ≦ x_i < W , 0 ≦ y_i < H , 1 ≦ l_i ≦ 4 (1 ≦ i ≦ N)
  • 0 ≦ r_i ≦ N-1
  • d_i は "N" , "S" , "E" , "W" のいずれか (1 ≦ i ≦ K) で、それぞれ 北・南・東・西 へ移動したことを表す。
入力例1
5 5 3 3
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 1 1
2 2 1
2 3 1
1 W
1 E
3 S
出力例1
3 1 2
2 2 1
2 4 1
攻略ポイント

ポイント

    • ロボットのクラスを定義する
      • 移動方向と移動距離の制御
      • レベルアップ処理
    • 工場のクラスを定義する
      • 工具ボックスの配置を管理する
      • 配置されているロボットを動かす

参考記事

クラス

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

標準入力・標準出力

問題を解く流れ

複雑そうな問題は、入出力例を見ながら情報を整理してみましょう。

ロボットの暴走_図1

  • 工場に工具箱とロボットを配置する
  • ロボットを動かす
    • ロボット1が西に進む（Lv1なので1コマ）
      • 工具箱があるのでLv2になる
    • ロボット1が東に進む（Lv2なので2コマ）
    • ロボット3が南に進む（Lv1なので1コマ）
  • ロボット１から３までの現在位置とレベルを出力する。

情報が整理出来たら問題を解いていきます。

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

INPUT1 = <<~"EOS"
  5 5 3 3
  0 0
  0 1
  0 2
  0 3
  0 4
  1 0
  1 1
  1 2
  1 3
  1 4
  2 1 1
  2 2 1
  2 3 1
  1 W
  1 E
  3 S
EOS
OUTPUT1 = <<~"EOS"
  3 1 2
  2 2 1
  2 4 1
EOS

# 確認用コード
pp INPUT1
# > "5 5 3 3\n" +
# > "0 0\n" +
# > "0 1\n" +
# > "0 2\n" +
# > "0 3\n" +
# > "0 4\n" +
# > "1 0\n" +
# > "1 1\n" +
# > "1 2\n" +
# > "1 3\n" +
# > "1 4\n" +
# > "2 1 1\n" +
# > "2 2 1\n" +
# > "2 3 1\n" +
# > "1 W\n" +
# > "1 E\n" +
# > "3 S\n"
p OUTPUT1
# > "3 1 2\n2 2 1\n2 4 1\n"

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

まず、Robotクラスを定義します。

Robotクラス

  • 定数
    • X移動方向 VX = {"N" => 0, "S" => 0, "E" => 1, "W" => -1}
    • Y移動方向 VY = {"N" => -1, "S" => 1, "E" => 0, "W" => 0}
    • 移動量設定 MOBILITY = [1, 2, 5, 10]
  • インスタンス変数
    • X座標 @x : Integer
    • Y座標 @y : Integer
    • レベル @lv : Integer
    • 移動量  @mobility : Integer
  • initializeメソッド
    • initialize(x, y, lv)
      • @x を x で初期化する
      • @y を y で初期化する
      • @lv を lv で初期化する
      • @mobility を MOBILITY[@lv - 1] で初期化する
        （lv1: 1, lv2: 2, lv3: 5, lv4: 10）
  • インスタンスメソッド
    • info
      • 配列 [@x, @y, @lv] を返す
    • move(direction)
      • direction が "N" なら @y から @mobility を引く（-y方向に移動）
      • direction が "S" なら  @y に @mobility を足す（+y方向に移動）
      • direction が "E" なら  @x に @mobility を足す（+x方向に移動）
      • direction が "W" なら @x から @mobility を引く（-x方向に移動）
    • lvup
      • lv4なら何もしない
      • @lv を +1 する
      • @mobility を MOBILITY[@lv - 1] で更新する
        （lv1: 1, lv2: 2, lv3: 5, lv4: 10）
class Robot
  VX = { "N" => 0, "S" => 0, "E" => 1, "W" => -1 }
  VY = { "N" => -1, "S" => 1, "E" => 0, "W" => 0 }
  MOBILITY = [1, 2, 5, 10]

  def initialize(x, y, lv)
    @x = x
    @y = y
    @lv = lv
    @mobility = MOBILITY[lv - 1]
  end

  def info
    [@x, @y, @lv]
  end

  def move(direction)
    @x += VX[direction] * @mobility
    @y += VY[direction] * @mobility
  end

  def lvup
    return if @lv == 4
    @lv += 1
    @mobility = MOBILITY[@lv - 1]
  end
end

# 確認用コード
robo = Robot.new(0, 0, 1)
p robo
# N で -y 方向に移動するか
robo.move("N")
p robo.info
# > [0, -1, 1]

# S で +y 方向に移動するか
robo.move("S")
p robo.info
# > [0, 0, 1]

# E で +x 方向に移動するか
robo.move("E")
p robo.info
# > [1, 0, 1]

# W で -x 方向に移動するか
robo.move("W")
p robo.info
# > [0, 0, 1]

# lv2
robo.lvup
p robo
# > #<Robot:0x00007fffbc4ce230 @x=0, @y=0, @lv=2, @mobility=2>

# lv3
robo.lvup
p robo
# > #<Robot:0x00007fffbe19e4f0 @x=0, @y=0, @lv=3, @mobility=5>

# lv4
robo.lvup
p robo
# > #<Robot:0x00007ffff50b1bf0 @x=0, @y=0, @lv=4, @mobility=10>

# lv カンスト
robo.lvup
p robo
# > #<Robot:0x00007ffff4a09ca8 @x=0, @y=0, @lv=4, @mobility=10>

つぎに、Factoryクラスを定義します。

Factoryクラス

  • インスタンス変数
    • 工具箱の座標 @boxes : Array
    • ロボットのリスト @robots : Array（外部からの参照可）
  • initializeメソッド
    • initialize(boxes, robots)
      • @boxes を boxes で初期化する
      • @robots を robots で初期化する
  • インスタンスメソッド
    • info
      • 配列 [@x, @y, @lv] を返す
    • move_robot(robot_no, direction)
      • robot_no で指定されたロボットを direction 方向へ移動する
      • 移動した位置に工具箱があればそのロボットの lvup メソッドを実行する
class Factory
  attr_reader :robots

  def initialize(boxes, robots)
    @boxes = boxes
    @robots = robots
  end

  def move_robot(robot_no, direction)
    robot = @robots[robot_no - 1]
    robot.move(direction)

    if @boxes.include?(robot.info[0..1])
      robot.lvup
    end
  end
end

# 入力例1 を手動で確認
boxes = [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4],
         [1, 0], [1, 1], [1, 2], [1, 3], [1, 4]]
robots = [Robot.new(2, 1, 1),
          Robot.new(2, 2, 1),
          Robot.new(2, 3, 1)]
factory = Factory.new(boxes, robots)

# robots[1 - 1] を "W" に移動
factory.move_robot(1, "W")
factory.robots.each { |robo| p robo }
# > #<Robot:0x00007fffc72b9688 @x=1, @y=1, @lv=2, @mobility=2>
# > #<Robot:0x00007fffc72b9660 @x=2, @y=2, @lv=1, @mobility=1>
# > #<Robot:0x00007fffc72b9610 @x=2, @y=3, @lv=1, @mobility=1>

# robots[1 - 1] を "E" に移動
factory.move_robot(1, "E")
factory.robots.each { |robo| p robo }
# > #<Robot:0x00007fffc7bdd1d8 @x=3, @y=1, @lv=2, @mobility=2>
# > #<Robot:0x00007fffc7bdd1b0 @x=2, @y=2, @lv=1, @mobility=1>
# > #<Robot:0x00007fffc7bdd138 @x=2, @y=3, @lv=1, @mobility=1>

# robots[3 - 1] を "S" に移動
factory.move_robot(3, "S")
factory.robots.each { |robo| p robo }
# > #<Robot:0x00007fffe6f2c630 @x=3, @y=1, @lv=2, @mobility=2>
# > #<Robot:0x00007fffe6f2c5e0 @x=2, @y=2, @lv=1, @mobility=1>
# > #<Robot:0x00007fffe6f2c590 @x=2, @y=4, @lv=1, @mobility=1>

# 移動終了時の状態を出力
factory.robots.each { |robo| p robo.info }
# > [3, 1, 2]
# > [2, 2, 1]
# > [2, 4, 1]

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

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

def solve(input_lines)
  # 入力データ受け取り
  toolbox = 10
  input_lines = input_lines.split("\n")
  h, w, n, k = input_lines.shift.split.map(&:to_i)
  boxes = input_lines.shift(toolbox).map do |coordinate|
    coordinate.split.map(&:to_i)
  end
  robots = input_lines.shift(n).map do |robot_params|
    x, y, lv = robot_params.split.map(&:to_i)
  end
  requests = input_lines.shift(k).map do |request_params|
    robot_no, direction = request_params.split
    [robot_no.to_i, direction]
  end

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

# 確認用コード
pp solve(INPUT1)
# > [[[0, 0],
# >   [0, 1],
# >   [0, 2],
# >   [0, 3],
# >   [0, 4],
# >   [1, 0],
# >   [1, 1],
# >   [1, 2],
# >   [1, 3],
# >   [1, 4]],
# >  [[2, 1, 1], [2, 2, 1], [2, 3, 1]],
# >  [[1, "W"], [1, "E"], [3, "S"]]]

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

  • 配列robotsの先頭から順にインスタンス化した配列で上書きします。
  • boxes, robots を引数に与えて Factoryクラスのインスタンスfactoryを生成します。
  • 配列requestsの値に従って指定されたロボットをmove_robotメソッドで移動します。
  • 移動終了後、factory.robotsの先頭から順にinfoメソッドを実行した結果をresultに格納します。
def solve(input_lines)
  # 入力データ受け取り
  toolbox = 10
  input_lines = input_lines.split("\n")
  h, w, n, k = input_lines.shift.split.map(&:to_i)
  boxes = input_lines.shift(toolbox).map do |coordinate|
    coordinate.split.map(&:to_i)
  end
  robots = input_lines.shift(n).map do |robot_params|
    x, y, lv = robot_params.split.map(&:to_i)
  end
  requests = input_lines.shift(k).map do |request_params|
    robot_no, direction = request_params.split
    [robot_no.to_i, direction]
  end

  # robots をインスタンス化して上書き
  robots.map! { |x, y, lv| Robot.new(x, y, lv) }
  # Factory クラスのインスタンス factory を生成
  factory = Factory.new(boxes, robots)

  # requests に従ってロボットを移動させる
  requests.each do |robot_no, direction|
    factory.move_robot(robot_no, direction)
  end

  # factory.robots の先頭から順に infoメソッドを実行した結果の配列を result に格納
  result = factory.robots.map { |robot| robot.info }

  # 確認用コード
  result
end

# 確認用コード
p solve(INPUT1)
# > [[3, 1, 2], [2, 2, 1], [2, 4, 1]]
p solve(INPUT1) == OUTPUT1
# > false

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

def solve(input_lines)
  # 入力データ受け取り
  toolbox = 10
  input_lines = input_lines.split("\n")
  h, w, n, k = input_lines.shift.split.map(&:to_i)
  boxes = input_lines.shift(toolbox).map do |coordinate|
    coordinate.split.map(&:to_i)
  end
  robots = input_lines.shift(n).map do |robot_params|
    x, y, lv = robot_params.split.map(&:to_i)
  end
  requests = input_lines.shift(k).map do |request_params|
    robot_no, direction = request_params.split
    [robot_no.to_i, direction]
  end

  # robots をインスタンス化して上書き
  robots.map! { |x, y, lv| Robot.new(x, y, lv) }
  # Factory クラスのインスタンス factory を生成
  factory = Factory.new(boxes, robots)

  # requests に従ってロボットを移動させる
  requests.each do |robot_no, direction|
    factory.move_robot(robot_no, direction)
  end

  # factory.robots の先頭から順に infoメソッドを実行した結果の配列を result に格納
  result = factory.robots.map { |robot| robot.info }

  # ロボットの情報を半角スペースで連結したものを改行で連結して末尾に改行を追加
  result.map { |robot_params| robot_params.join(" ") }.join("\n") << "\n"
end

# 確認用コード
p solve(INPUT1)
# > "3 1 2\n2 2 1\n2 4 1\n"
p solve(INPUT1) == OUTPUT1
# > true

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

解答コード
class Robot
  VX = { "N" => 0, "S" => 0, "E" => 1, "W" => -1 }
  VY = { "N" => -1, "S" => 1, "E" => 0, "W" => 0 }
  MOBILITY = [1, 2, 5, 10]

  def initialize(x, y, lv)
    @x = x
    @y = y
    @lv = lv
    @mobility = MOBILITY[lv - 1]
  end

  def info
    [@x, @y, @lv]
  end

  def move(direction)
    @x += VX[direction] * @mobility
    @y += VY[direction] * @mobility
  end

  def lvup
    return if @lv == 4
    @lv += 1
    @mobility = MOBILITY[@lv - 1]
  end
end

class Factory
  attr_reader :robots

  def initialize(boxes, robots)
    @boxes = boxes
    @robots = robots
  end

  def move_robot(robot_no, direction)
    robot = @robots[robot_no - 1]
    robot.move(direction)

    if @boxes.include?(robot.info[0..1])
      robot.lvup
    end
  end
end

def solve(input_lines)
  # 入力データ受け取り
  toolbox = 10
  input_lines = input_lines.split("\n")
  h, w, n, k = input_lines.shift.split.map(&:to_i)
  boxes = input_lines.shift(toolbox).map do |coordinate|
    coordinate.split.map(&:to_i)
  end
  robots = input_lines.shift(n).map do |robot_params|
    x, y, lv = robot_params.split.map(&:to_i)
  end
  requests = input_lines.shift(k).map do |request_params|
    robot_no, direction = request_params.split
    [robot_no.to_i, direction]
  end

  # robots をインスタンス化して上書き
  robots.map! { |x, y, lv| Robot.new(x, y, lv) }
  # Factory クラスのインスタンス factory を生成
  factory = Factory.new(boxes, robots)

  # requests に従ってロボットを移動させる
  requests.each do |robot_no, direction|
    factory.move_robot(robot_no, direction)
  end

  # factory.robots の先頭から順に infoメソッドを実行した結果の配列を result に格納
  result = factory.robots.map { |robot| robot.info }

  # ロボットの情報を半角スペースで連結したものを改行で連結して末尾に改行を追加
  result.map { |robot_params| robot_params.join(" ") }.join("\n") << "\n"
end

puts solve(STDIN.read)

今回のまとめ

  • 定数を使ってロボットの移動方向を制御しました。
    （二次元配列の座標や迷路系の問題を解くのによく使います）
  • 複数のRobotクラスのインスタンスを管理するFactoryクラスを定義して全体をまとめました。

今回でクラス・構造体メニューの攻略は終了です！お疲れ様でした！


【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 じゃいごテック