ある数でつくられた数列

今回は paiza の「ある数でつくられた数列」の問題に挑戦！

問題概要

• 3つの 素数 P1, P2, P3 が与えられる
• 1 を出発点として、それらの素数を 何回でも（0回でも）掛けて 作れる数を考える
• そうして作れる すべての数を小さい順に並べた数列を作る
• その数列の k 番目（1始まり）の値を出力する

入力例:

2 3 5 7

出力例:

8

✅OK例：

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

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

rl.on('close', () => {
    const [P1, P2, P3, k] = lines[0].split(' ').map(Number);

    // 最小ヒープ（Min Heap）クラス
    class MinHeap {
        constructor() {
            // ヒープ本体（配列で管理）
            this.heap = [];
        }

        // 値をヒープに追加する
        push(value) {
            // 末尾に追加
            this.heap.push(value);
            // ヒープ条件を保つため上に移動
            this._bubbleUp(this.heap.length - 1);
        }

        // 最小値を取り出す
        pop() {
            // 先頭が常に最小値
            const min = this.heap[0];

            // 末尾の要素を取得
            const last = this.heap.pop(); // 配列（Array）の pop メソッド

            // 要素が残っている場合のみ再調整
            if (this.heap.length > 0) {
                // 末尾の要素を先頭に置く
                this.heap[0] = last;
                // 下に落としてヒープ条件を回復
                this._bubbleDown(0);
            }

            return min;
        }

        // 下から上へ要素を移動
        // 親より小さければ交換する
        _bubbleUp(index) {
            while (index > 0) {
                // 親ノードのインデックス
                const parent = Math.floor((index - 1) / 2);

                // 親の方が小さければOK
                if (this.heap[parent] <= this.heap[index]) break;

                // 親と子を交換
                [this.heap[parent], this.heap[index]] =
                    [this.heap[index], this.heap[parent]];

                // 親の位置へ移動
                index = parent;
            }
        }

        // 上から下へ要素を移動
        // 子より大きければ交換する
        _bubbleDown(index) {
            const length = this.heap.length;

            while (true) {
                let smallest = index;

                // 左右の子ノードの位置
                const left = index * 2 + 1;
                const right = index * 2 + 2;

                // 左の子と比較
                if (left < length && this.heap[left] < this.heap[smallest]) {
                    smallest = left;
                }

                // 右の子と比較
                if (right < length && this.heap[right] < this.heap[smallest]) {
                    smallest = right;
                }

                // 自分が最小なら終了
                if (smallest === index) break;

                // 小さい方の子と交換
                [this.heap[index], this.heap[smallest]] =
                    [this.heap[smallest], this.heap[index]];

                // 交換先からさらにチェック
                index = smallest;
            }
        }
    }


    // 数列生成処理

    // 最小ヒープを用意
    const heap = new MinHeap();

    // 重複防止用セット
    const seen = new Set();

    // 数列の最初の要素は 1
    heap.push(1);
    seen.add(1);

    let current = 1;


    // k 回、最小値を取り出す
    for (let i = 0; i < k; i++) {
        // current に 3つの素数を掛ける
        for (const p of [P1, P2, P3]) {
            const next = current * p;

            // まだ生成されていなければ追加
            if (!seen.has(next)) {
                seen.add(next);
                heap.push(next);
            }
        }
        
        // 現時点で一番小さい数の更新
        current = heap.pop(); 
    }

    // k番目の数を出力
    console.log(current);
});

🔍コードの流れ

① 入力を受け取る

• P1, P2, P3, k を 1 行から読み取る
• 3つの素数と「何番目を出力するか」が決まる

② 最小ヒープ（MinHeap）クラスを定義

• 常に一番小さい値をすぐ取り出せるデータ構造
• 内部で配列を使って管理
• 主な役割
  • push()：値を追加して小さい順を保つ
  • pop()：最小値を取り出して削除する
  • _bubbleUp() / _bubbleDown()：順序を保つための内部処理

③ 数列生成の準備

• heap：候補となる数を入れておく最小ヒープ
• seen：すでに作った数を記録する（重複防止）
• 数列のスタートは 1
  • heap.push(1)
  • seen.add(1)
• current = 1（現在の取り出し対象）

④ k 回繰り返す（ここがメイン）

• 毎回「次に小さい数」を確定させる

ループ1回分でやっていること

• current に P1, P2, P3 を掛けた値を作る
• まだ出ていない数だけ
  • seen に登録
  • heap に追加
• heap.pop() で
  • 現時点で一番小さい数を取り出す
  • それを current に更新

これで「小さい順に数列を1つずつ確定」していく

⑤ k 番目の数を出力

• ループ終了時の current が数列の k 番目
• console.log(current) で出力

📝まとめ

「最小値 × 3つの素数 → 新しい候補をヒープに入れ、ヒープから最小を取り出す」
を k 回繰り返すプログラム。

heap: 候補箱（小さい順に並ぶ）
seen: もう作った？チェック表

1 → 2,5,7 → 次に小さいのは 2
2 → 4,10,14 → 次に小さいのは 4
4 → 8,20,28 → 次に小さいのは 5
5 → 10,25,35 → 次に小さいのは 7
7 → 14,35,49 → 次に小さいのは 8
...