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)

「ある数でつくられた数列」を解くために:part4　💡ヒープ

Posted at

今回は paiza の「「ある数でつくられた数列」を解くために:part4」の問題に挑戦！
js にはヒープが標準で無いらしく、クラスで再現してみた！

問題概要

  • 入力として
    • 3つの素数 P1, P2, P3
    • 自然数 k
      が与えられる
  • 「数列」を次のルールで作る
    • 初項は 1
    • 1 に P1, P2, P3 を 何回でも掛けてよい
    • どの素数を 使わなくてもよい
  • そうして作れる すべての数を
    • 重複を除いて
    • 小さい順に並べた数列
      と考える
  • その数列の k 番目に小さい数 を出力する


入力例:

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 = heap.pop(); // インスタンスメソッド呼び出し → 最小値取得

        // current に 3つの素数を掛ける
        for (const p of [P1, P2, P3]) {
            const next = current * p;

            // まだ生成されていなければ追加
            if (!seen.has(next)) {
                seen.add(next);
                heap.push(next);
            }
        }
    }

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

🔍コードの流れ

  • 標準入力の準備
    • readline を使って入力を1行ずつ lines 配列に保存する
    • 入力が終わったら close イベントで処理開始
  • 入力の読み取り
    • 1行目から P1, P2, P3, k を取得
    • 3つの素数と「何番目を求めるか」を決定
  • 最小ヒープ（MinHeap）の定義
    • 常に「一番小さい数」を取り出せるデータ構造
    • push：値を追加
    • pop：最小値を取り出す
    • 内部で配列を使い、順序を保つ
  • 初期化
    • ヒープに 1 を追加（数列の最初の要素）
    • Set に 1 を登録（重複防止用）
    • current を用意
  • k 回ループ
    • ヒープから最小値を取り出す → current
    • current に対して
      • P1, P2, P3 を掛ける
    • まだ出ていない値だけを
      • Set に登録
      • ヒープに追加
  • 結果の出力
    • k 回目に取り出した current を出力
    • これが「数列の k 番目に小さい数」






💡ヒープとは？

👉 「常に一番小さい（または大きい）値をすぐ取り出せる箱」

  • 配列の一種
  • ただし 並び方に特別なルールがある
  • ソート済み配列とは違う

最小ヒープ（Min Heap）

今回使っているヒープの種類

  • 親の値 ≤ 子の値
  • 一番小さい値は 必ず先頭（index 0）
 1
/ \
2 3
/ \
4 5

配列としては：

[1, 2, 3, 4, 5]

※ 見た目は配列、意味は木構造


① まずこの問題での「ヒープの役割」

この問題でやりたいことは：

  • P1, P2, P3 を掛けてできる数の中から
  • 常に「次に小さい数」から順番に取り出したい

つまり：

  • 「全部作ってからソート」 ❌（爆発する）
  • 小さい順に1個ずつ取り出したい ⭕

👉 ここで ヒープ（優先度付きキュー） が必要になる。


② ヒープとは（このコード限定の定義）

このコードにおける 最小ヒープ は：

「一番小さい値が必ず heap[0] にある配列」

だけを保証するデータ構造。

重要なのは👇

  • 完全ソートはしていない
  • 先頭だけ最小であればOK


③ コードの流れ × ヒープの中身

ここから コードを1行ずつ追いながら 見ていく

🔹 STEP 1：初期化

const heap = new MinHeap();
const seen = new Set();
heap.push(1);
seen.add(1);

ヒープの状態

[1]
  • 最初の数は必ず 1
  • 当然これが最小

🔹 STEP 2：k 回ループ

for (let i = 0; i < k; i++) {
    current = heap.pop();

ここで起きていること

  1. heap[0]（一番小さい数）を取り出す
  2. ヒープから削除する
  3. 次に小さい数が先頭に来るよう並び替える

👉 「次に処理すべき最小の数」を確定させる

例：最初の pop

ヒープ：

[1]

current = 1;



🔹 STEP 3：取り出した数から次を生成

for (const p of [P1, P2, P3]) {
    const next = current * p;

意味:

「今いちばん小さい数 current から、次に来る候補を作る」

例えば：

current = 1
P1=2, P2=3, P3=5

生成される候補：

2, 3, 5



🔹 STEP 4：ヒープに突っ込む

if (!seen.has(next)) {
    seen.add(next);
    heap.push(next);
}

ここでのヒープ操作
① push(next)

this.heap.push(next);
this._bubbleUp(...)

👉 「とりあえず末尾に入れてから」
👉 「小さければ上に上げる」

例：2, 3, 5 を入れた後

ヒープ（形はどうでもいい）：

[2, 3, 5]

保証されているのは👇

  • heap[0] === 2
  • 他は順不同


🔹 STEP 5：次のループへ

次の i でまたこれ👇

current = heap.pop();

今度は

current = 2

ヒープには

[3, 5]

が残る。


🔹 STEP 6：また増やす

2 * P1, 2 * P2, 2 * P3

例：

4, 6, 10

ヒープに追加すると（seenで重複除外）：

[3, 4, 5, 6, 10]

※ 配列の順番は違ってもOK
※ 先頭が最小であることだけが重要


④ ヒープの「正体」を一言で言うと

このコードにおけるヒープは：

「次に使う最小の数を、常に O(1) で取り出せる箱」

その代わり：

  • 追加・削除のたびに、
    _bubbleUp / _bubbleDown で
    最小条件だけを回復している



コード ヒープ的な意味
heap.push(x) 候補を箱に入れる
_bubbleUp 小さければ前に出す
heap.pop() 今いちばん小さい数を確定
_bubbleDown 次の最小を先頭に出す
heap[0] 常に最小値






📝まとめ

ポイント

  • 全部作ってからソートはしない
    • 数が指数的に増えるため非現実的
  • 必要なのは
    👉 「次に一番小さい数」を1つずつ確定すること
  • そのために
    • 最小ヒープ（優先度付きキュー）
    • Set（重複排除）
      を組み合わせて使う
  • ヒープとは
    👉 「常に最小（最大）を素早く取り出せるデータ構造」
  • ヒープは配列で実装できるが
    👉 意味的には木構造
  • pop() は
    • 配列の shift() ではない
    • 「最小値を確定させる操作」
  • _bubbleUp / _bubbleDown は
    • ヒープ条件（親 ≤ 子）を保つための調整
  • Set は
    • 正しさ（重複排除）
    • 計算量削減
      の両方に必須
  • この問題の本質は：
    「数を全部作る」のではなく、「必要な分だけ、小さい順に作る」

解法の方針（アルゴリズム）

  • 最小ヒープを用意する
    • 常に「一番小さい数」を取り出せる
  • Set を用意する
    • 同じ数を二度入れないため
  • 初期状態として
    • ヒープに 1 を入れる
    • Set に 1 を登録
  • k 回繰り返す
    • ヒープから 最小値を取り出す（これが current）
    • current × P1, P2, P3 を計算
    • まだ出ていない数だけ
      • Set に登録
      • ヒープに追加
  • k 回目に取り出した current が答え
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?