paiza プログラミング

[Ruby]paiza スキルチェック過去問題セット 神経衰弱 (paizaランク B 相当)の解説

paiza解説 神経衰弱

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

今回はpaizaレベルアップ問題集から神経衰弱という問題を解説していきたいと思います。こちらは過去にスキルチェックで実際に出題されていた問題らしいです!

難易度は 1575±14 で、B級としては割と簡単な問題だと思います。ただ、二次元配列に慣れていなければ難しく感じるかもしれません。

神経衰弱 (paizaランク B 相当)を解いてみる

※ paiza レベルアップ問題集 スキルチェック過去問題セットより

問題

神経衰弱と呼ばれるトランプゲームのシミュレーションをしましょう。
今回は数字が書かれたトランプのみを考え、ジョーカーは考えません。

まず、トランプを縦 H 枚、横 W 枚の長方形の形に並べた状態でスタートします。
H × W 枚のトランプには 1 〜 13 の数字のうちどれか1つが書かれています。
また、同じ数字が書かれたトランプが複数あります。

プレイヤーが N 人おり、それぞれ 1 〜 N で番号付けられています。
ゲームが始まると、1番の人から、このような手順でプレイしていきます。

  • 並べられたトランプから2枚のトランプを選び、めくります。
  • めくった2枚のトランプに異なる数字が書かれていれば、次のプレイヤーの手番となります。同じ数字であれば、次の操作をおこないます。
  • まず、2枚のトランプはめくったプレーヤーのものとなり、取り除かれます。
  • トランプがすべて取り除かれた場合、ゲームは終了となります。
  • トランプが残っている場合、同じプレーヤーがまた最初の手順に戻り、トランプをめくります。ここで、N 番のプレイヤーの次のプレイヤーは 1 番のプレイヤーであるとします。ゲームの初期状態におけるトランプの配置と、ゲームが終わるまでに捲られたトランプに関する時系列順の記録が与えられます。
    その記録を用いて、各プレイヤーが取り除いたトランプの枚数を求めてください。

入力される値

入力は以下のフォーマットで与えられます。

H W N
t_{1,1} t_{1,2} ... t_{1,W}
t_{2,1} t_{2,2} ... t_{2,W}
...
t_{H,1} t_{H,2} ... t_{H,W}
L
a_1 b_1 A_1 B_1
a_2 b_2 A_2 B_2
...
a_L b_L A_L B_L

1行目には3つの整数 H, W, Nが入力されます。
H と W はそれぞれ並べられたトランプの縦方向の枚数と横方向の枚数で、N はプレイヤーの数を表します。

続く H 行には、配置されたトランプに書かれた数字が入力されます。
t_{i,j} は i 行 j 列に置かれたトランプに書かれた数字を表します。

次の行には、記録の長さ L が与えられます。

続く L 行には、捲られたトランプの記録が時系列順で与えられます。
これは、a_i 行 b_i 列のトランプと A_i 行 B_i 列のトランプが捲られたことを表します。

入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。

期待する出力

i 行目には i 番目のプレイヤーが取り除いたトランプの枚数を出力してください。
各行の最後は改行し、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

  • 1 ≦ H, W ≦ 13
  • H × W は52以下の2の倍数
  • 2 ≦ N ≦ 10
  • t_{i,j} は 1, ... ,13 のいずれか
  • 並べられたトランプの中に、同じ数字が書かれたトランプは2枚または4枚ある
  • 1 ≦ L ≦ 200
  • 1 ≦ a_i, A_i ≦ H
  • 1 ≦ b_i, B_i ≦ W
  • a_i 行 b_i 列および A_i 行 B_i 列のトランプは取り除かれていない
  • (a_i, b_i) ≠ (A_i, B_i)
入力例1
2 3 2
1 2 3
2 1 3
5
1 1 2 1
1 1 1 2
1 1 2 2
1 3 2 3
1 2 2 1
出力例1
6
0
入力例2
2 5 3
5 8 8 6 3
3 6 3 3 5
8
1 4 2 2
1 3 2 1
2 4 2 3
1 3 1 5
2 5 1 1
2 1 1 2
1 5 2 1
1 2 1 3
出力例2
6
2
2
攻略ポイント

ポイント

  • 二次元配列のデータを扱う
    • 標準入力から h * w の二次元配列を受け取る
    • 二次元配列にアクセスする
  • 特殊な条件の実装
    • カードを当てたら再度チャレンジできる
    • 場のカードが無くなったらゲーム終了

参考記事

問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。INPUT1 が与えられた時に OUTPUT1 を出力すれば正解と言うことになります。
きちんと受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  2 3 2
  1 2 3
  2 1 3
  5
  1 1 2 1
  1 1 1 2
  1 1 2 2
  1 3 2 3
  1 2 2 1
EOS
OUTPUT1 = <<~"EOS"
  6
  0
EOS

INPUT2 = <<~"EOS"
  2 5 3
  5 8 8 6 3
  3 6 3 3 5
  8
  1 4 2 2
  1 3 2 1
  2 4 2 3
  1 3 1 5
  2 5 1 1
  2 1 1 2
  1 5 2 1
  1 2 1 3
EOS
OUTPUT2 = <<~"EOS"
  6
  2
  2
EOS

# 動作確認用コード
p INPUT1
p OUTPUT1
p INPUT2
p OUTPUT2
# > "2 3 2\n1 2 3\n2 1 3\n5\n1 1 2 1\n1 1 1 2\n1 1 2 2\n1 3 2 3\n1 2 2 1\n"
# > "6\n0\n"
# > "2 5 3\n5 8 8 6 3\n3 6 3 3 5\n8\n1 4 2 2\n1 3 2 1\n2 4 2 3\n1 3 1 5\n2 5 1 1\n2 1 1 2\n1 5 2 1\n1 2 1 3\n"
# > "6\n2\n2\n"

続いて問題を解くメソッド( solve メソッドとします)を変数の下に定義します。

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

入力された文字列を改行で分割して各変数に代入します。

  • 1行目を半角スペースで分割して要素を h (縦の枚数), w (横の枚数), n (参加人数) に代入
  • 続くh 行を cards (カードの配置) に代入
  • 次の行を l (ログの件数)に代入
  • 続く l 行を game_log(カードを選択した記録) に代入
def solve(input_lines)
  # 改行区切りの配列に変換する
  input_lines = input_lines.split("\n")
  # h: 縦枚数, w: 横枚数, n: 参加人数 を代入する
  h, w, n = input_lines.shift.split.map(&:to_i)
  # 続く 縦: h 枚 x 横: w 枚のトランプ配置情報を cards に代入する
  cards = input_lines.shift(h).map do |line|
    line.split.map(&:to_i)
  end
  # l: ゲームの記録数 を代入する
  l = input_lines.shift.to_i
  # 続く l 行のゲーム記録を game_log に代入する
  game_log = input_lines.shift(l).map do |line|
    line.split.map(&:to_i)
  end

  # 動作確認用コード
  [h, w, n, cards, game_log]
end

pp solve(INPUT1)
# > [2,
# > 3,
# > 2,
# > [[1, 2, 3], [2, 1, 3]],
# > [[1, 1, 2, 1], [1, 1, 1, 2], [1, 1, 2, 2], [1, 3, 2, 3], [1, 2, 2, 1]]]

出力データが多い場合は pp メソッドで表示するとイイ感じに改行を入れてくれます。

各変数 h, w, n, cards, game_log にデータが正しく受け取れていれば、solve メソッドに神経衰弱の処理を追加します。

cards へのアクセスを楽にするために、 game_log の各要素を −1 しています。

def solve(input_lines)
  # 改行区切りの配列に変換する
  input_lines = input_lines.split("\n")
  # h: 縦枚数, w: 横枚数, n: 参加人数 を代入する
  h, w, n = input_lines.shift.split.map(&:to_i)
  # 続く 縦: h 枚 x 横: w 枚のトランプ配置情報を cards に代入する
  cards = input_lines.shift(h).map do |line|
    line.split.map(&:to_i)
  end
  # l: ゲームの記録数 を代入する
  l = input_lines.shift.to_i
  # 続く l 行のゲーム記録の各値を -1 して game_log に代入する
  game_log = input_lines.shift(l).map do |line|
    line.split.map { |idx| idx.to_i - 1 }
  end

  # [参加者No, 取得枚数(0)]で初期化した配列を players に代入する
  players = (1..n).map { |no| [no, 0] }
  # 場のカード枚数初期化
  card_total = h * w

  # game_log 先頭から次々値を取り出して繰り返し処理を行う
  # (h1, w1): カード位置1, (h2, w2): カード位置2
  game_log.each do |h1, w1, h2, w2|
    # players 先頭から no, score を取り出す
    no, score = players.shift

    # 【動作確認用コード】
    puts <<~"EOS"
           ******************************
           player #{no}
           cards[#{h1}][#{w1}]: #{cards[h1][w1]}
           cards[#{h2}][#{w2}]: #{cards[h2][w2]}
         EOS

    # カードの数値が合わなかった場合
    # 又は取得済みの場所を指定した場合はハズレ
    if cards[h1][w1] != cards[h2][w2] || cards[h1][w1] == 0
      # 【動作確認用コード】
      puts "ハズレ"

      # player を players 末尾に追加
      players.push([no, score])
      # 後の処理をスキップして次の人の番
      next
    end

    # 【動作確認用コード】
    puts "アタリ"

    # アタリの処理
    # 再度あたりにならないように捲ったカードを 0 にする
    cards[h1][w1] = 0
    cards[h2][w2] = 0
    # score を +2 する
    score += 2
    # 場のカードを -2 する
    card_total -= 2
    # 再度挑戦できるので player を players 先頭に追加
    players.unshift([no, score])
    # 場のカードが無くなったら終了
    break if card_total == 0
  end

  # プレイヤー番号順の獲得枚数の配列を返す
  players.sort_by { |player| player[0] }.map { |no, score| score }
end

p solve(INPUT1)
# > ******************************
# > player 1
# > cards[0][0]: 1
# > cards[1][0]: 2
# > ハズレ
# > ******************************
# > player 2
# > cards[0][0]: 1
# > cards[0][1]: 2
# > ハズレ
# > ******************************
# > player 1
# > cards[0][0]: 1
# > cards[1][1]: 1
# > アタリ
# > ******************************
# > player 1
# > cards[0][2]: 3
# > cards[1][2]: 3
# > アタリ
# > ******************************
# > player 1
# > cards[0][1]: 2
# > cards[1][0]: 2
# > アタリ
# > [6, 0]

最後に出力された配列が参加者順のカード獲得枚数となりますので、確認用コードをコメントアウトし、参加者順の獲得枚数を出力するように変更します。

def solve(input_lines)
  # 改行区切りの配列に変換する
  input_lines = input_lines.split("\n")
  # h: 縦枚数, w: 横枚数, n: 参加人数 を代入する
  h, w, n = input_lines.shift.split.map(&:to_i)
  # 続く 縦: h 枚 x 横: w 枚のトランプ配置情報を cards に代入する
  cards = input_lines.shift(h).map do |line|
    line.split.map(&:to_i)
  end
  # l: ゲームの記録数 を代入する
  l = input_lines.shift.to_i
  # 続く l 行のゲーム記録の各値を -1 して game_log に代入する
  game_log = input_lines.shift(l).map do |line|
    line.split.map { |idx| idx.to_i - 1 }
  end

  # [参加者No, 取得枚数(0)]で初期化した配列を players に代入する
  players = (1..n).map { |no| [no, 0] }
  # 場のカード枚数初期化
  card_total = h * w

  # game_log 先頭から次々値を取り出して繰り返し処理を行う
  # (h1, w1): カード位置1, (h2, w2): カード位置2
  game_log.each do |h1, w1, h2, w2|
    # players 先頭から no, score を取り出す
    no, score = players.shift

    # 【動作確認用コード】
    # puts <<~"EOS"
    #        ******************************
    #        player #{no}
    #        cards[#{h1}][#{w1}]: #{cards[h1][w1]}
    #        cards[#{h2}][#{w2}]: #{cards[h2][w2]}
    #      EOS

    # カードの数値が合わなかった場合
    # 又は取得済みの場所を指定した場合はハズレ
    if cards[h1][w1] != cards[h2][w2] || cards[h1][w1] == 0
      # 【動作確認用コード】
      # puts "ハズレ"

      # player を players 末尾に追加
      players.push([no, score])
      # 後の処理をスキップして次の人の番
      next
    end

    # 【動作確認用コード】
    # puts "アタリ"

    # アタリの処理
    # 再度あたりにならないように捲ったカードを 0 にする
    cards[h1][w1] = 0
    cards[h2][w2] = 0
    # score を +2 する
    score += 2
    # 場のカードを -2 する
    card_total -= 2
    # 再度挑戦できるので player を players 先頭に追加
    players.unshift([no, score])
    # 場のカードが無くなったら終了
    break if card_total == 0
  end

  # プレイヤー番号順の獲得枚数の配列を返す
  players.sort_by { |player|
    player[0]
  }.map { |no, score| score }.join("\n") << "\n"
end

p solve(INPUT1)
p solve(INPUT1) == OUTPUT1
puts solve(INPUT1)
# > "6\n0\n"
# > true
# > 6
# > 0

確認用コードを削除して、標準入力からのデータ受け取りに変更と動作確認をしたら提出します。
STDIN.read の 入力終了は Ctrl+D 又は Ctrl+Z)

解答コード
def solve(input_lines)
  # 改行区切りの配列に変換する
  input_lines = input_lines.split("\n")
  # h: 縦枚数, w: 横枚数, n: 参加人数 を代入する
  h, w, n = input_lines.shift.split.map(&:to_i)
  # 続く 縦: h 枚 x 横: w 枚のトランプ配置情報を cards に代入する
  cards = input_lines.shift(h).map do |line|
    line.split.map(&:to_i)
  end
  # l: ゲームの記録数 を代入する
  l = input_lines.shift.to_i
  # 続く l 行のゲーム記録の各値を -1 して game_log に代入する
  game_log = input_lines.shift(l).map do |line|
    line.split.map { |idx| idx.to_i - 1 }
  end

  # [参加者No, 取得枚数(0)]で初期化した配列を players に代入する
  players = (1..n).map { |no| [no, 0] }
  # 場のカード枚数初期化
  card_total = h * w

  # game_log 先頭から次々値を取り出して繰り返し処理を行う
  # (h1, w1): カード位置1, (h2, w2): カード位置2
  game_log.each do |h1, w1, h2, w2|
    # players 先頭から no, score を取り出す
    no, score = players.shift

    # カードの数値が合わなかった場合
    # 又は取得済みの場所を指定した場合はハズレ
    if cards[h1][w1] != cards[h2][w2] || cards[h1][w1] == 0
      # player を players 末尾に追加
      players.push([no, score])
      # 後の処理をスキップして次の人の番
      next
    end

    # アタリの処理
    # 再度あたりにならないように捲ったカードを 0 にする
    cards[h1][w1] = 0
    cards[h2][w2] = 0
    # score を +2 する
    score += 2
    # 場のカードを -2 する
    card_total -= 2
    # 再度挑戦できるので player を players 先頭に追加
    players.unshift([no, score])
    # 場のカードが無くなったら終了
    break if card_total == 0
  end

  # プレイヤー番号順の獲得枚数の配列を返す
  players.sort_by { |player|
    player[0]
  }.map { |no, score| score }.join("\n") << "\n"
end

puts solve(STDIN.read)

今回のまとめ

標準入力からの二次元配列データの受け取りと要素へのアクセスを使いました。また、アタリの時は順番待ちの先頭に追加して連続手番のルールを実装しました。

二次元配列を使う機会はとても多いので少しずつ慣れておくと良いと思います!



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


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






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







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







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







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


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

© 2024 じゃいごテック