こんにちは！じゃいごテックのあつしです。
今回は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 列のトランプが捲られたことを表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。
期待する出力
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)
今回のまとめ
標準入力からの二次元配列データの受け取りと要素へのアクセスを使いました。また、アタリの時は順番待ちの先頭に追加して連続手番のルールを実装しました。
二次元配列を使う機会はとても多いので少しずつ慣れておくと良いと思います！
