Go to Qiita Advent Calendar Top
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)

【全探索 4】ストラックアウト　順列

Posted at

今回は paiza の「【全探索 4】ストラックアウト」の問題に挑戦！

順列！！！


問題概要

〇 ストラックアウト

1〜9 の番号が付いた 9 枚のパネルが、以下のように 3×3 の配置で置かれている。

123
456
789

〇 得点ルール

  • 得点は最初 0 点から始まる。
  • パネル i を倒すと、基本点 s_i が加算される。
  • パネル i を倒した結果、新しく「ビンゴ（横・縦・斜めの 3 枚がすべて倒れること）」が完成した場合、ボーナス点 b_i_j が加算される。
    • j = 今回そのパネルで新しく完成したビンゴの数
    • 例えば同時に 2 本のビンゴが完成した場合は b_i_2 が加算され、b_i_1 は加算されない。
  • パネルは一度しか倒せない。

〇 目的

  • 倒す順番を自由に決められるとき、最終的に獲得できる得点の最大値を求める。

〇 入力

  • 1〜9 のパネルの基本点 s_1 … s_9 （3 行に分けて与えられる）。
  • 各パネルごとに「そのパネルを倒したときに発生するビンゴ数ごとのボーナス点」b_i_j が与えられる。
    • パネルごとに関わるライン数が違うので、入力の個数も異なる。
      • 角のパネル → 3 ライン（横・縦・斜め）
      • 辺のパネル → 2 ライン
      • 真ん中のパネル → 4 ライン

〇 出力

  • 獲得可能な最大スコア



入力例:

1 2 3
1 2 3
1 2 3
1 2 3
1 2
1 2 3
1 2
1 2 3 4
1 2
1 2 3
1 2
1 2 3

出力例:

26






✅ OK例：

const readline = require('readline');

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

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

    // === 入力をすべて数値に変換して1次元配列に格納 ===
    const inputs = lines.join(' ').split(' ').map(Number);
    let idx = 0;

    // === 基本スコアの読み込み ===
    const s = Array(9);
    let ans = 0; // 基本スコア合計
    for (let i = 0; i < 9; i++) {
        s[i] = inputs[idx++];
        ans += s[i];
    }

    // === ボーナス点の読み込み ===
    const b = Array.from({ length: 9 }, () => []);
    for (let i = 0; i < 9; i++) {
        let len = i === 4 ? 4 : i % 2 === 0 ? 3 : 2;
        for (let j = 0; j < len; j++) {
            b[i][j] = inputs[idx++];
        }
    }

    // === パネル番号 0~8 ===
    const panels = Array.from({ length: 9 }, (_, i) => i);

    // === 順列生成関数 ===
    function permute(arr, k = 0, result = []) {
        if (k === arr.length - 1) {
            result.push([...arr]); // 完成した順列を保存
        } else {
            for (let i = k; i < arr.length; i++) {
                [arr[k], arr[i]] = [arr[i], arr[k]]; // スワップ
                permute(arr, k + 1, result);
                [arr[k], arr[i]] = [arr[i], arr[k]]; // 戻す（バックトラック）
            }
        }
        return result;
    }

    // すべての順列を取得
    const allPermutations = permute(panels);

    let add = 0; // 最大ボーナス

    // === 順列ごとにシミュレーション ===
    for (const p of allPermutations) {
        const openedPanel = Array(9).fill(false); // パネルを倒したか
        let tmp = 0; // この順列のボーナス合計

        for (let i = 0; i < 9; i++) {
            let line = 0;

            // 倒したパネルが何本のラインを完成させるか判定
            switch (p[i]) {
                case 0:
                    line += openedPanel[1] && openedPanel[2] ? 1 : 0;
                    line += openedPanel[3] && openedPanel[6] ? 1 : 0;
                    line += openedPanel[4] && openedPanel[8] ? 1 : 0;
                    break;
                case 1:
                    line += openedPanel[0] && openedPanel[2] ? 1 : 0;
                    line += openedPanel[4] && openedPanel[7] ? 1 : 0;
                    break;
                case 2:
                    line += openedPanel[0] && openedPanel[1] ? 1 : 0;
                    line += openedPanel[5] && openedPanel[8] ? 1 : 0;
                    line += openedPanel[4] && openedPanel[6] ? 1 : 0;
                    break;
                case 3:
                    line += openedPanel[0] && openedPanel[6] ? 1 : 0;
                    line += openedPanel[4] && openedPanel[5] ? 1 : 0;
                    break;
                case 4:
                    line += openedPanel[0] && openedPanel[8] ? 1 : 0;
                    line += openedPanel[2] && openedPanel[6] ? 1 : 0;
                    line += openedPanel[1] && openedPanel[7] ? 1 : 0;
                    line += openedPanel[3] && openedPanel[5] ? 1 : 0;
                    break;
                case 5:
                    line += openedPanel[2] && openedPanel[8] ? 1 : 0;
                    line += openedPanel[3] && openedPanel[4] ? 1 : 0;
                    break;
                case 6:
                    line += openedPanel[0] && openedPanel[3] ? 1 : 0;
                    line += openedPanel[2] && openedPanel[4] ? 1 : 0;
                    line += openedPanel[7] && openedPanel[8] ? 1 : 0;
                    break;
                case 7:
                    line += openedPanel[1] && openedPanel[4] ? 1 : 0;
                    line += openedPanel[6] && openedPanel[8] ? 1 : 0;
                    break;
                case 8:
                    line += openedPanel[2] && openedPanel[5] ? 1 : 0;
                    line += openedPanel[6] && openedPanel[7] ? 1 : 0;
                    line += openedPanel[0] && openedPanel[4] ? 1 : 0;
                    break;
            }

            // ボーナス加算（line が1以上かつ undefined でない場合）
            if (line > 0 && b[p[i]][line-1] !== undefined) {
                tmp += b[p[i]][line-1];
            }

            openedPanel[p[i]] = true; // パネルを倒したことにする
        }

        add = Math.max(add, tmp); // 最大ボーナスを更新
    }

    // 基本スコア + 最大ボーナス
    console.log(ans + add);
});



① 入力を数値に変換

const inputs = lines.join(' ').split(' ').map(Number);
let idx = 0;

  • lines.join(' ') → 配列 lines のすべての行を1つの文字列に結合

  • .split(' ') → 空白で分割して1次元配列にする

  • .map(Number) → 文字列を数値に変換

  • idx → 配列を順番に読み込むときの「位置」を管理する変数



② 基本スコアの読み込み

const s = Array(9);
let ans = 0; // 基本スコア合計
for (let i = 0; i < 9; i++) {
    s[i] = inputs[idx++];
    ans += s[i];
}
  • s 配列に 9つの基本スコア を格納
  • ans にすべての基本スコアを合計
  • inputs[idx++] → idx 番目の数値を取り出し、idx を1増やす
    （次の数字を読む準備）

💡ポイント：基本スコアは「パネル1枚ごとの得点」



③ ボーナス点の読み込み

const b = Array.from({ length: 9 }, () => []);
for (let i = 0; i < 9; i++) {
    let len = i === 4 ? 4 : i % 2 === 0 ? 3 : 2;
    for (let j = 0; j < len; j++) {
        b[i][j] = inputs[idx++];
    }
}
  • b は ボーナス点の2次元配列
  • パネルごとにボーナス点の数は違う
    • 例：中央のパネル（i=4）は最大4ラインに関わるので長さ4
      他は2〜3ライン
  • len → そのパネルが持つボーナス点の数
  • b[i][j] = inputs[idx++] → ボーナス点を格納

💡ポイント：これは「パネルを倒す順番によって得られる追加点」



④ パネル番号の用意

const panels = Array.from({ length: 9 }, (_, i) => i);

    panels = [0,1,2,3,4,5,6,7,8]

    0〜8 の パネル番号 を作る

    これを使って「どの順番でパネルを倒すか」の順列を作ります。

⑤ 順列を作る関数

function permute(arr, k = 0, result = []) {
    if (k === arr.length - 1) {
        result.push([...arr]); // 完成した順列を保存
    } else {
        for (let i = k; i < arr.length; i++) {
            [arr[k], arr[i]] = [arr[i], arr[k]]; // スワップ
            permute(arr, k + 1, result);
            [arr[k], arr[i]] = [arr[i], arr[k]]; // 戻す（バックトラック）
        }
    }
    return result;
}
  • 配列 arr の すべての順列（並び替え） を生成する再帰関数
  • k → 何番目の位置を決めるか
  • スワップして順列を作り、再帰で次の位置を決定
  • 最後にバックトラック（元に戻す）
  • result に完成した順列を追加 (スプレッド構文でコピーして保存)

💡ポイント：これで「全ての倒す順番」を網羅的に試せる。

🔍もう少し詳しく↓

配列 arr は「パネル番号のリスト」。

この問題では arr = [0,1,2,3,4,5,6,7,8] で、9 枚のパネルを どの順番で倒すか を表す。

permute 関数は、この配列のすべての並べ替え（順列）を作る。

📌 例えば簡単化して「3 枚だけのパネル」と考えて arr = [0,1,2] とすると、倒す順番の候補は：

[0,1,2]
[0,2,1]
[1,0,2]
[1,2,0]
[2,0,1]
[2,1,0]

の 6 通りになる。

🔍 再帰の流れ（k が「何番目の位置を決めるか」）

permute(arr, k, result) のイメージはこう：

  • k=0 → 「1番目に倒すパネル」を決める段階
  • k=1 → 「2番目に倒すパネル」を決める段階
  • k=2 → 「3番目に倒すパネル」を決める段階
    最後まで決まったら result に保存

🔍 実際の流れ（arr=[0,1,2] の場合）

k=0  arr=[0,1,2]
  i=0 → swap(0,0) arr=[0,1,2] → 再帰 k=1
    k=1
      i=1 → swap(1,1) arr=[0,1,2] → 再帰 k=2
        完成 → [0,1,2]
      i=2 → swap(1,2) arr=[0,2,1] → 再帰 k=2
        完成 → [0,2,1]
  i=1 → swap(0,1) arr=[1,0,2] → 再帰 k=1
    k=1
      i=1 → swap(1,1) arr=[1,0,2] → 再帰 k=2
        完成 → [1,0,2]
      i=2 → swap(1,2) arr=[1,2,0] → 再帰 k=2
        完成 → [1,2,0]
  i=2 → swap(0,2) arr=[2,1,0] → 再帰 k=1
    k=1
      i=1 → swap(1,1) arr=[2,1,0] → 再帰 k=2
        完成 → [2,1,0]
      i=2 → swap(1,2) arr=[2,0,1] → 再帰 k=2
        完成 → [2,0,1]

👉 この結果、6 通りの順列ができあがる。

🔍 この問題の場合の意味

この「完成した順列」はつまり：

  • [0,1,2,…,8] → 「パネル0 → パネル1 → パネル2 → … → パネル8 の順に倒す」
  • [2,5,8,…] → 「パネル2 → パネル5 → パネル8 → … の順に倒す」

のように「全ての倒す順番の候補」を表す。
この順番ごとにシミュレーションして得点を計算し、最大値を取るのがゴール。

🔍 まとめると：

  • arr = パネルの集合（[0..8]）
  • k = 今どの位置のパネルを決めているか
  • 順列生成は「全ての倒す順番」を作るために必要
  • 例として [0,1,2] なら「3 枚のパネルを倒す順番の全パターン」を生成する



⑥ 順列の取得

const allPermutations = permute(panels);

  • panels のすべての順列を作成

  • 長さ9の配列なので、9! = 362,880 通り


⑦ 最大ボーナスを計算

let add = 0; // 最大ボーナス
  • add に順列ごとのボーナスの最大値を格納する



⑧ 順列ごとのシミュレーション

for (const p of allPermutations) {
    const openedPanel = Array(9).fill(false); // パネルを倒したか
    let tmp = 0; // この順列のボーナス合計

  • openedPanel[i] = true なら「パネル i はすでに倒した」

  • tmp にその順列の ボーナス合計 を保存


⑨ 各パネルで完成するラインを判定

for (let i = 0; i < 9; i++) {
    let line = 0;

    switch (p[i]) {
        case 0:
            line += openedPanel[1] && openedPanel[2] ? 1 : 0;
            line += openedPanel[3] && openedPanel[6] ? 1 : 0;
            line += openedPanel[4] && openedPanel[8] ? 1 : 0;
            break;
        ...
    }
  • p[i] → 現在倒すパネル番号
  • line → 今回倒すことで 完成するラインの数
  • 例えばパネル0を倒すと、もしパネル1と2を倒していたら横1ライン完成 → line += 1
  • 他にも縦や斜めのラインが完成する場合を加算

💡 ポイント：ここで「ボーナス点が発生するか」を判定している。



⑩ ボーナス点を加算

if (line > 0 && b[p[i]][line-1] !== undefined) {
    tmp += b[p[i]][line-1];
}

  • line > 0 → 何かラインが完成したとき

  • b[p[i]][line-1] → 完成したライン数に対応するボーナス点を加算

  • tmp に累積



⑪ パネルを倒したことにする

openedPanel[p[i]] = true;

  • この順列で パネル p[i] を倒したこと を記録

  • 次のループでライン判定に使う。


⑫ 最大ボーナスの更新

add = Math.max(add, tmp);

  • 現在の順列でのボーナス tmp と add を比較

  • 最大値を保存


⑬ 最終的な得点を出力

console.log(ans + add);

  • 基本スコア ans と最大ボーナス add を合計

  • これが 最高得点






📝 まとめ

  • 入力をまとめて1次元配列に変換 → idx で順番に取り出す
  • 2次元配列でなくても、パネルやボーナス点は1次元配列で管理できる
  • 順列（並び替え）の再帰生成
  • 各順列ごとにシミュレーションして、ボーナス点を計算
  • openedPanel 配列で「倒したパネル」を管理
  • switch 文でライン完成を判定
  • ボーナス点を加算し、最大値を保持
  • 最後に基本スコア + 最大ボーナスを出力

💡 覚えておきたいポイント
  • Array.from({length:n}, ...) で配列を作る
  • 再帰で順列を作る仕組み
  • 配列を参照して「状態管理」をする（ここでは openedPanel）
  • switch 文や条件演算子でケースごとの処理
  • 最後に全体の最大値を比較して保持する




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

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?