【全探索 4】ストラックアウト (paizaランク B 相当)

考え方

パネルの枚数が 9 枚なので、全てのパネルを倒す順番の順列
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 8, 7]
[0, 1, 2, 3, 4, 5, 7, 6, 8]
...
について、ビンゴで獲得できる得点を計算し、その最大値を求める。
この処理でおこなわれるループの回数は 1 ~ 9 の値の並べ方の数と一致するので 9! となる。

順列を列挙するには、JavaSdcriptは用意されている関数がないので、再帰関数を定義する。

paiza.ioだとタイムアウトするが、スキルアップ問題集の解答は通る。

解答例(C++の場合参考)

next_permutation という順列を列挙する再帰関数を定義。
do {
//今回の順列でパネルを倒していき、得点計算、最大値更新
} while(next_permutation(panels));
で実行。
コードをみやすくするために三項演算子を利用。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//順列を列挙する再帰関数を定義
/* 
  一度next_permutation(arr)を実行すると、一つ次の順列arrを生成し、trueを返す。
  最後の順列arrを与えると、順列を全て生成し終わりと判定し、falseを返す。
*/
function next_permutation(arr) {
  for (let i = arr.length - 2; i >= 0; i--) {
    if (arr[i] < arr[i + 1]) {
      for (let j = arr.length - 1; j > i; j--) {
        if (arr[j] > arr[i]) {
          [arr[i], arr[j]] = [arr[j], arr[i]];
          const len = (arr.length - (i + 1)) >> 1;
          for (let k = 0; k < len; k++) {
            [arr[i + 1 + k], arr[arr.length - 1 - k]] = [arr[arr.length - 1 - k], arr[i + 1 + k]];
          }
          return true;
        }
      }
    }
  }
  return false;
}

//メイン
const s = lines.slice(0, 3).join(" ").split(" ").map(Number);
const b = lines.slice(3).map(line => line.split(" ").map(Number));
const panels = Array(9).fill().map((v, i) => v = i);//パネル

let [ans, add] = [0, 0];//ans求める合計、addビンゴの加算点数
ans += s.reduce((a, b) => a + b);//合計にパネルを倒した全得点を加える

do {
  const opened_panel = Array(9).fill(false);//倒したパネル判定
  let tmp = 0;//今回のパネルの倒し方のパターンのビンゴ加算合計点
  for (let i = 0; i < 9; i++) { //今回のパネルパターンを順番に見ていく
    let line = 0;//パネルを倒した時のビンゴ数
    switch (panels[i]) { //倒すパネル
      case 0://倒した番号-1
        line += (opened_panel[1] && opened_panel[2] ? 1 : 0);//1,2も倒していたら横にビンゴしてビンゴ数を+1
        line += (opened_panel[3] && opened_panel[6] ? 1 : 0);
        line += (opened_panel[4] && opened_panel[8] ? 1 : 0);
        break;

      case 1:
        line += (opened_panel[0] && opened_panel[2] ? 1 : 0);
        line += (opened_panel[4] && opened_panel[7] ? 1 : 0);
        break;

      case 2:
        line += (opened_panel[0] && opened_panel[1] ? 1 : 0);
        line += (opened_panel[5] && opened_panel[8] ? 1 : 0);
        line += (opened_panel[4] && opened_panel[6] ? 1 : 0);
        break;

      case 3:
        line += (opened_panel[0] && opened_panel[6] ? 1 : 0);
        line += (opened_panel[4] && opened_panel[5] ? 1 : 0);
        break;

      case 4:
        line += (opened_panel[0] && opened_panel[8] ? 1 : 0);
        line += (opened_panel[2] && opened_panel[6] ? 1 : 0);
        line += (opened_panel[1] && opened_panel[7] ? 1 : 0);
        line += (opened_panel[3] && opened_panel[5] ? 1 : 0);
        break;

      case 5:
        line += (opened_panel[2] && opened_panel[8] ? 1 : 0);
        line += (opened_panel[3] && opened_panel[4] ? 1 : 0);
        break;

      case 6:
        line += (opened_panel[0] && opened_panel[3] ? 1 : 0);
        line += (opened_panel[2] && opened_panel[4] ? 1 : 0);
        line += (opened_panel[7] && opened_panel[8] ? 1 : 0);
        break;

      case 7:
        line += (opened_panel[1] && opened_panel[4] ? 1 : 0);
        line += (opened_panel[6] && opened_panel[8] ? 1 : 0);
        break;

      case 8:
        line += (opened_panel[2] && opened_panel[5] ? 1 : 0);
        line += (opened_panel[6] && opened_panel[7] ? 1 : 0);
        line += (opened_panel[0] && opened_panel[4] ? 1 : 0);
        break;
    }
    if (0 < line) { //ビンゴしたら
      tmp += b[panels[i]][line - 1];//ビンゴの加算b[倒したパネル][同時ビンゴ数]
    }
    opened_panel[panels[i]] = true;//パネル倒した記録
  } //for
  add = Math.max(add, tmp);//ビンゴ加算最大値更新
  
} while (next_permutation(panels));//順列の列挙まだあるなら(return true)ループ。順列全列挙が終わったら(return false)ループ終了。

console.log(ans + add);//パネル自体を倒した点数＋ビンゴの加算点数