paiza プログラミング

[Ruby]paiza スキルチェック過去問題セット みんなでしりとり (paizaランク B 相当)の解説

paiza解説 みんなでしりとり

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

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

難易度は 2058±18 で、B級としては平均的な難易度の問題だと思います。

みんなでしりとり (paizaランク B 相当) を解いてみる

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

問題

あなたは友達たちと N 人でしりとりを行うことにしました。
1 人目、 2 人目、...、 N 人目、 1 人目、2 人目、... という順序で発言をします。

ここで、それぞれの人は、次に挙げる 4 つのしりとりのルールを守って発言をする必要があります。

  1. 発言は、単語リストにある K 個の単語のうちのいずれかの単語でなければならない。
  2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
  3. 今までに発言された単語を発言してはならない。
  4. 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 つ入ります。

入力値最終行の末尾に改行が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級問題からは複雑な条件分岐などが出てきますが、問題を細かく分割して実装すれば大丈夫!

 

 



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


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






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







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







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







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


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

© 2024 じゃいごテック