【全探索 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);//パネル自体を倒した点数＋ビンゴの加算点数