こんにちは！じゃいごテックのあつしです。
今回はpaizaレベルアップ問題集からみんなでしりとりという問題を解説していきたいと思います。こちらは過去にスキルチェックで実際に出題されていた問題らしいです！
難易度は 2058±18 で、B級としては平均的な難易度の問題だと思います。
みんなでしりとり (paizaランク B 相当) を解いてみる
※ paiza レベルアップ問題集 スキルチェック過去問題セットより
問題
あなたは友達たちと N 人でしりとりを行うことにしました。
1 人目、 2 人目、...、 N 人目、 1 人目、2 人目、... という順序で発言をします。
ここで、それぞれの人は、次に挙げる 4 つのしりとりのルールを守って発言をする必要があります。
- 発言は、単語リストにある K 個の単語のうちのいずれかの単語でなければならない。
- 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
- 今までに発言された単語を発言してはならない。
- z で終わる単語を発言してはならない。
ここで、発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
そして、その人を抜いて引き続きしりとりを続けていきます。このとき、後続の人は、ルール 2 を守る必要はありません。N 人がしりとりを行ったログが M 行分与えられます。
このとき、M 回の発言が終わった後、しりとりから脱落せずに残っている人のリストを表示するプログラムを書いてください。
入力される値
入力は以下のフォーマットで与えられます。
N K M
d_1
d_2
...
d_K
s_1
s_2
...
s_M
- 1 行目にしりとりをする人数を表す整数 N、単語リストに乗っている単語の数を表す整数 K、しりとりで行われた発言の数を表す整数 M がこの順にスペース区切りで与えられます。
- 続く K 行のうちの i 行目 (1 ≦ i ≦ K) には、単語リストに乗っている i 番目の単語を表す文字列 d_i が与えられます。
- 続く M 行のうちの j 行目 (1 ≦ j ≦ M) には、しりとりで行われた j 番目の発言を表す文字列 s_j が与えられます。
- 入力は合計で K + M + 1 行となり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
最終的にしりとりから脱落せずに残っている人の番号を以下の形式で出力してください。
N'
a_1
a_2
...
a_N'
期待する出力は N' + 1 行からなります。
1 行目には、最終的にしりとりから脱落せずに残っている人の人数を表す整数 N' を出力してください。
続く N' 行のうち、i 行目 (1 ≦ i ≦ N') には、最終的にしりとりから脱落せずに残っている人の番号のうち、小さい方から i 番目のものを出力してください。
N' + 1 行目の出力の最後に改行を入れ、余計な文字、空行を含んではいけません。
条件
すべてのテストケースにおいて、以下の条件をみたします。
- 1 ≦ N ≦ 10
- 1 ≦ K ≦ 1,000
- 1 ≦ M ≦ 1,000
各 i, i' (1 ≦ i, i' ≦ K) について
- 1 ≦ (d_i の長さ) ≦ 10
- i ≠ i' なら d_i ≠ d_i'
各 j (1 ≦ j ≦ M) について
- 1 ≦ (s_j の長さ) ≦ 10
少なくとも 1 人はしりとりから脱落しないことが保証されている
入力例1
3 6 7
a
aloha
app
az
paiza
warp
app
paiza
a
aloha
az
warp
paiza
出力例1
1
3
入力例2
4 4 4
abacus
banana
candy
yankee
banana
candies
candies
yankee
出力例2
2
1
4
攻略ポイント
ポイント
- データ構造のキューを利用する
- 回答者のループ処理
- 脱落者の処理
- 回答のルールを状況で切り替える
- 初回は単語リストから選択すればどの単語でも良い
- 脱落者が出た後は、単語リストから選択して既出でなければ良い
参考記事
問題を解く流れ
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。INPUT1 が与えられた時に OUTPUT1 を出力すれば正解と言うことになります。
きちんと受け取れていれば確認用コードは削除します。
INPUT1 = <<~"EOS" 3 6 7 a aloha app az paiza warp app paiza a aloha az warp paiza EOS OUTPUT1 = <<~"EOS" 1 3 EOS INPUT2 = <<~"EOS" 4 4 4 abacus banana candy yankee banana candies candies yankee EOS OUTPUT2 = <<~"EOS" 2 1 4 EOS # 確認用コード p INPUT1 p OUTPUT1 p INPUT2 p OUTPUT2 # > "3 6 7\na\naloha\napp\naz\npaiza\nwarp\napp\npaiza\na\naloha\naz\nwarp\npaiza\n" # > "1\n3\n" # > "4 4 4\nabacus\nbanana\ncandy\nyankee\nbanana\ncandies\ncandies\nyankee\n" # > "2\n1\n4\n"
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
入力された文字列を改行で分割して各変数に代入します。
- 1行目を半角スペースで分割して要素を n (参加人数), k (使える単語数), m (ログの件数) に代入
- 続く
k行を words (使える単語リスト) に代入 - 続く
m行を game_log(しりとりのログ) に代入
def solve(input_lines)
input_lines = input_lines.split("\n")
n, k, m = input_lines.shift.split.map(&:to_i)
words = input_lines.shift(k)
game_log = input_lines.shift(m)
# 動作確認用
[n, words, game_log]
end
p solve(INPUT1)
# > [3, ["a", "aloha", "app", "az", "paiza", "warp"], ["app", "paiza", "a", "aloha", "az", "warp", "paiza"]]
各変数 n, words, game_log にデータが正しく受け取れていれば、solve メソッドにしりとりの処理を追加します。
（処理中に動作確認用コードを入れてみました。）
def solve(input_lines)
input_lines = input_lines.split("\n")
n, k, m = input_lines.shift.split.map(&:to_i)
words = input_lines.shift(k)
game_log = input_lines.shift(m)
# 参加者のリストを作成
players = (1..n).to_a
# 前の回答を空文字で初期化
last_word = ""
#️ しりとりのログで繰り返し処理を行う
game_log.each do |word|
# players の先頭から回答者を取り出す
respondent = players.shift
# 【動作確認用コード】
puts <<~"EOS"
******************************
回答可能な単語リスト: #{words}
前の単語: #{last_word}
参加者 #{respondent} の回答は #{word}
EOS
# 【しりとりルール】
# 単語リストにある単語を使うこと
# first_word 以外は前の単語の末尾を先頭に持つ単語を使うこと
# 既出単語を使わないこと
# "z" で終わらないこと
if words.include?(word) && (last_word.empty? || last_word[-1] == word[0]) && word[-1] != "z"
# 【word がルール判定で true だった場合】
# 次は前の単語の末尾を先頭に持つ単語を使うルールを適用
last_word = word
# 答えた単語を回答可能な単語リストから除外する
words.delete(word)
# 現在の回答者を参加者の最後尾に追加する
players << respondent
# 【動作確認用コード】
puts "判定 OK"
else
# 【word がルール判定で false だった場合】
# 次の回答は前の単語の末尾で始まらなくても良い
last_word = ""
# 【動作確認用コード】
puts "判定 NG 参加者 #{respondent} 脱落"
end
end
# 動作確認用
players
end
p solve(INPUT1)
# > ******************************
# > 回答可能な単語リスト: ["a", "aloha", "app", "az", "paiza", "warp"]
# > 前の単語:
# > 参加者 1 の回答は app
# > 判定 OK
# > ******************************
# > 回答可能な単語リスト: ["a", "aloha", "az", "paiza", "warp"]
# > 前の単語: app
# > 参加者 2 の回答は paiza
# > 判定 OK
# > ******************************
# > 回答可能な単語リスト: ["a", "aloha", "az", "warp"]
# > 前の単語: paiza
# > 参加者 3 の回答は a
# > 判定 OK
# > ******************************
# > 回答可能な単語リスト: ["aloha", "az", "warp"]
# > 前の単語: a
# > 参加者 1 の回答は aloha
# > 判定 OK
# > ******************************
# > 回答可能な単語リスト: ["az", "warp"]
# > 前の単語: aloha
# > 参加者 2 の回答は az
# > 判定 NG 参加者 2 脱落
# > ******************************
# > 回答可能な単語リスト: ["az", "warp"]
# > 前の単語:
# > 参加者 3 の回答は warp
# > 判定 OK
# > ******************************
# > 回答可能な単語リスト: ["az"]
# > 前の単語: warp
# > 参加者 1 の回答は paiza
# > 判定 NG 参加者 1 脱落
# > [3]
結果表示を見ると正しく処理されていることがわかりますね。
最後に出力された配列が最後まで残った参加者のリストとなりますので、確認用コードをコメントアウトし、残った人数と番号順に参加者を出力するように変更します。
def solve(input_lines)
input_lines = input_lines.split("\n")
n, k, m = input_lines.shift.split.map(&:to_i)
words = input_lines.shift(k)
game_log = input_lines.shift(m)
# 参加者のリストを作成
players = (1..n).to_a
# 前の回答を初期化
last_word = ""
#️ しりとりのログで繰り返し処理を行う
game_log.each do |word|
# players の先頭から回答者を取り出す
respondent = players.shift
# 【動作確認用コード】
# puts <<~"EOS"
# ******************************
# 回答可能な単語リスト: #{words}
# 前の単語: #{last_word}
# 参加者 #{respondent} の回答は #{word}
# EOS
# 【しりとりルール】
# 単語リストにある単語を使うこと
# first_word 以外は前の単語の末尾を先頭に持つ単語を使うこと
# 既出単語を使わないこと
# "z" で終わらないこと
if words.include?(word) && (last_word.empty? || last_word[-1] == word[0]) && word[-1] != "z"
# 【word がルール判定で true だった場合】
# 次は前の単語の末尾を先頭に持つ単語を使うルールを適用
last_word = word
# 答えた単語を回答可能な単語リストから除外する
words.delete(word)
# 現在の回答者を参加者の最後尾に追加する
players << respondent
# 【動作確認用コード】
# puts "判定 OK"
else
# 【word がルール判定で false だった場合】
# 次の回答は前の単語の末尾で始まらなくても良い
last_word = ""
# 【動作確認用コード】
# puts "判定 NG 参加者 #{respondent} 脱落"
end
end
# 残った人数と残ったメンバーを番号順に出力
[players.length].concat(players.sort).join("\n") << "\n"
end
p solve(INPUT1)
p solve(INPUT1) == OUTPUT1
puts solve(INPUT1)
# > "1\n3\n"
# > true
# > 1
# > 3
確認用コードを削除して、標準入力からのデータ受け取りに変更と動作確認をしたら提出します。
（STDIN.read の 入力終了は Ctrl+D 又は Ctrl+Z)
解答コード
def solve(input_lines)
input_lines = input_lines.split("\n")
n, k, m = input_lines.shift.split.map(&:to_i)
words = input_lines.shift(k)
game_log = input_lines.shift(m)
# 参加者のリストを作成
players = (1..n).to_a
# 前の回答を初期化
last_word = ""
#️ しりとりのログで繰り返し処理を行う
game_log.each do |word|
# players の先頭から回答者を取り出す
respondent = players.shift
# 【しりとりルール】
# 単語リストにある単語を使うこと
# first_word 以外は前の単語の末尾を先頭に持つ単語を使うこと
# 既出単語を使わないこと
# "z" で終わらないこと
if words.include?(word) && (last_word.empty? || last_word[-1] == word[0]) && word[-1] != "z"
# 【word がルール判定で true だった場合】
# 次は前の単語の末尾を先頭に持つ単語を使うルールを適用
last_word = word
# 答えた単語を回答可能な単語リストから除外する
words.delete(word)
# 現在の回答者を参加者の最後尾に追加する
players << respondent
else
# 【word がルール判定で false だった場合】
# 次の回答は前の単語の末尾で始まらなくても良い
last_word = ""
end
end
# 残った人数と残ったメンバーを番号順に改行区切りで出力
[players.length].concat(players.sort).join("\n") << "\n"
end
puts solve(STDIN.read)
今回のまとめ
回答者のループと脱落者の処理を、キュー構造で実装しました。また、直前の単語 last_word に入っているデータを判別することによって、初回と脱落者が出た直後のルールを実装しました。
B級問題からは複雑な条件分岐などが出てきますが、問題を細かく分割して実装すれば大丈夫！
