天井システム

今回は paiza の「天井システム」の問題に挑戦！

🧩 問題概要

• 図鑑番号 1 ～ N のモンスターは レア
• 図鑑番号 N+1 ～ M のモンスターは コモン
• ガチャを T 回 引いた結果として
• 整数列 A₁, A₂, ..., A_T が与えられる
  • A_i は i 回目に出たモンスターの図鑑番号
• 判定したいこと：
  • K 回連続でレアモンスターが 1 回も出ていない区間が存在するか
• 出力ルール：
  • K 回連続でコモンモンスターだけが出ている区間があれば → "No"
  • どの K 回連続区間にも、少なくとも 1 回はレアが出ていれば → "Yes"

入力例:

5 7 5 3
2 3 7 2 6

出力例:

Yes

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [N, M, T, K] = lines[0].split(' ').map(Number);
    const A = lines[1].split(' ').map(Number);
    
    let ans = 'Yes';
    
    for (let i = 0; i <= T - K; i++) { // 始点を全探索
        let rare = false; // K回の間にレアが出ていればtrue
    
        for (let j = 0; j < K; j++) { // 始点からK回分チェック
            if (A[i + j] <= N) {
                rare = true;
                break; // レアが出たらこれ以上見る必要なし
            }
        }
    
        if (!rare) { // K回連続でレアが出ていない
            ans = 'No';
            break; // No が確定したら終了
        }
    }
    
    console.log(ans);
});

🔍コードの流れ

• 標準入力から
  • N, M, T, K を読み取る
  • ガチャ結果 A[0] ～ A[T-1] を配列として受け取る
• 答えを一旦 'Yes' にしておく
  （条件に引っかかったら 'No' に変える方針）

判定処理

• ガチャ結果の 始点 i を 0 ～ T-K まで全探索する
  →「K回連続」の区間をすべて調べるため
• 各始点ごとに
  • rare = false を用意
    （この K 回の中でレアが出たかどうかのフラグ）
• 始点 i から K回分 ガチャ結果を見る
  • A[i + j] <= N ならレアモンスター
    • rare = true にする
    • これ以上見る必要がないので break
• K回見終わったあと
  • rare === false のままなら
    → K回連続でレアが出ていない
    • ans = 'No'
    • もう答えは確定なので break

出力

• 最終的な ans を出力

📝まとめ

• 「K 回連続」という条件を満たすために、
  • 長さ K の連続した区間をすべて調べる
• そのために、
  • 始点 i = 0 ～ T-K を全探索する
• 各区間ごとに、
  • 「この K 回の中にレアが 1 回でも出たか？」を調べる
  • フラグ（rare）で管理する
• もし、レアが 1 回も出ていない区間が見つかったら、
  • 条件違反 → 即 No