LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Haru_K0720(Haru_K)

みんなでしりとり

Posted at

今回は paiza の「みんなでしりとり」の問題に挑戦！

生存をフラグ管理するところがポイントだった！


⚙ 問題概要

〇 状況: N 人でしりとりを行う。順番は 1 → 2 → … → N → 1 → …。

〇 ルール:

  • 発言は単語リスト K 個の中から選ぶ
  • 最初の人以外は、直前の発言の最後の文字と同じ文字で始める
  • 既に使われた単語は使えない
  • "z" で終わる単語は使えない

〇 脱落:

  • 発言がルールに違反するとその人は脱落
  • 脱落者を飛ばしてしりとりを継続
  • 脱落者の次の人はルール2を無視してよい

〇 入力:

  • 1行目: N K M
  • 次の K 行: 単語リスト
  • 次の M 行: 発言ログ

〇 出力:

  • 生き残った人数 N’
  • 生き残ったプレイヤーの番号（1-indexed、小さい順）



入力例:

3 6 7
a
aloha
app
az
paiza
warp
app
paiza
a
aloha
az
warp
paiza

出力例:

1
3






✅OK例：

const rl = require("readline").createInterface({ input: process.stdin });
const lines = [];

rl.on("line", (input) => lines.push(input));

rl.on("close", () => {
  const [N, K, M] = lines[0].split(' ').map(Number);

  // 単語リスト
  const words = new Set();
  for (let i = 1; i <= K; i++) {
    words.add(lines[i]);
  }

  // 生存フラグ
  const alive = Array(N).fill(true);

  let lastChar = ''; // 直前の人の発言の最後の文字
  let player = 0;
  const usedWords = new Set(); // 既出単語

  for (let i = 0; i < M; i++) {
    // 残っている人が出てくるまで進める
    while (!alive[player]) {
      player = (player + 1) % N;
    }

    const word = lines[K + 1 + i];

    const violateRule1 = !words.has(word);                        // ルール1
    const violateRule2 = lastChar !== '' && lastChar !== word[0]; // ルール2
    const violateRule3 = usedWords.has(word);                     // ルール3
    const violateRule4 = word[word.length - 1] === "z";           // ルール4

    if (violateRule1 || violateRule2 || violateRule3 || violateRule4) {
      alive[player] = false; // 脱落
      lastChar = ""; // リセット
    } else {
      usedWords.add(word); // 既出リストに追加
      lastChar = word[word.length - 1];
    }

    player = (player + 1) % N; // 順番を進める
  }

  // 生き残り人数をカウント
  const aliveCount = alive.filter((x) => x).length; // aliveリストの true だけカウント
  console.log(aliveCount);

  // 生き残っている人の番号を出力（1-indexed）
  alive.forEach((isAlive, idx) => {
    if (isAlive) console.log(idx + 1);
  });
});




1️⃣ 入力処理部分

const rl = require("readline").createInterface({ input: process.stdin });
const lines = [];

rl.on("line", (input) => lines.push(input));
  • readline モジュールを使って標準入力からデータを1行ずつ取得。
  • 入力された行をすべて lines 配列に格納。

rl.on("close", () => {
  const [N, K, M] = lines[0].split(' ').map(Number);
  • 1行目から人数 N、単語リストの数 K、発言回数 M を取得。
  • split(' ') で分割し、map(Number) で数値型に変換。



2️⃣ 単語リストをセットに格納

  const words = new Set();
  for (let i = 1; i <= K; i++) {
    words.add(lines[i]);
  }
  • 単語リスト d_1, d_2, ..., d_K を Set に格納。
  • Set にすることで、単語の存在チェック (has) が高速にできるようになる



3️⃣ 生存フラグと変数の初期化

  const alive = Array(N).fill(true);

  let lastChar = ''; // 直前の人の発言の最後の文字
  let player = 0;
  const usedWords = new Set(); // 既出単語

  • alive 配列で各プレイヤーの生存状態を管理。
    → 初期値は全員 true（生存）。

  • lastChar は直前の単語の最後の文字を保持。

  • player は現在発言するプレイヤーのインデックス（0〜N-1）。

  • usedWords は既に使われた単語を記録する 集合(Set)。



4️⃣ 発言処理ループ

  for (let i = 0; i < M; i++) {
    while (!alive[player]) { // 残っている人が出てくるまで進める
      player = (player + 1) % N;
    }

    const word = lines[K + 1 + i];
  • M 回の発言を順に処理。
  • while (!alive[player]) で、脱落したプレイヤーをスキップ。
  • lines[K + 1 + i] で i 回目の発言 s_i を取得。



5️⃣ ルール違反判定

    const violateRule1 = !words.has(word);                        // ルール1
    const violateRule2 = lastChar !== '' && lastChar !== word[0]; // ルール2
    const violateRule3 = usedWords.has(word);                     // ルール3
    const violateRule4 = word[word.length - 1] === "z";           // ルール4

  • ルール1: 単語リストに存在するか？

  • ルール2: 前の単語の最後の文字と一致しているか？
    → 最初の人の場合は lastChar === '' なのでスキップ。

  • ルール3: 既に使われた単語か？

  • ルール4: 単語が "z" で終わっていないか？



6️⃣ ルール違反時の処理

    if (violateRule1 || violateRule2 || violateRule3 || violateRule4) {
      alive[player] = false; // 脱落
      lastChar = ""; // リセット
    } else {
      usedWords.add(word); // 既出リストに追加
      lastChar = word[word.length - 1];
    }

    player = (player + 1) % N; // 順番を進める
  • もしどれかのルールに違反したら：
    • プレイヤーを脱落させる (alive[player] = false)。
    • 次のプレイヤーがルール2に縛られないように lastChar をリセット。
  • 違反しなければ：
    • 単語を usedWords に追加。
    • lastChar を更新。
  • 最後にプレイヤー番号を順に進める。



7️⃣ 結果出力

  const aliveCount = alive.filter((x) => x).length;
  console.log(aliveCount);

  alive.forEach((isAlive, idx) => {
    if (isAlive) console.log(idx + 1);
  });
  • aliveCount で生き残った人数をカウント。
  • filter((x) => x) は true の要素だけ取り出すテクニック。
  • 生き残っているプレイヤーの番号（1-indexed）を出力。






📝まとめ


🔹データ構造の活用
  • 単語リストや使用済み単語は Set で管理 → 存在チェックや重複チェックが高速
  • 生存フラグは配列で管理 → 脱落者を簡単にスキップ可能

🔹 順番管理

  • 脱落者をスキップするために while (!alive[player]) を使用
  • 順番は (player + 1) % N で循環

🔹 ルール判定

  • 各ルールを個別に変数にしてチェック
  • 違反がある場合は脱落フラグを立て、必要に応じて lastChar をリセット

🔹 文字列操作の注意

  • 文字の取得: word[0]（頭文字）、word[word.length - 1]（最後の文字）

🔹 結果の出力

  • 生存者の人数を filter で数える
  • 生存者番号は 1-indexed で出力

🔹 ポイント

  • 脱落者が出ても次の人はスムーズに処理できるように順番と lastChar の管理が重要

  • Set を使うことでルール1・3のチェックが has でO(1) にできる




僕の失敗談(´;ω;｀)と解決法🐈

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?