アルファベータ枝刈りはミニマックスと同じ答えを出しつつ、結果を変えられない枝を飛ばします。2 つの境界を追跡します。alpha は MAX が既に確保している最善の点数、beta は MIN が既に確保している最善の点数です。
ゲーム木は完全木です。すべての内部ノードは branching 個の子を持ち、すべての葉は同じ深さにあります。leaves は葉の点数を左から右へ並べたものです。根は MAX ノードで、階層は MAX、MIN、MAX、… と交互に続きます。
alpha = -∞、beta = +∞ から始めて、子を左から右へ探索します。
- MAX ノードでは、各子のあとに best = max(best, value)、続いて alpha = max(alpha, best)。
- MIN ノードでは、各子のあとに best = min(best, value)、続いて beta = min(beta, best)。
- alpha ≥ beta になった時点で、そのノードの残りの子を飛ばします。
alpha_beta(leaves, branching) を実装してください。
入力
leaves: 左から右への葉の点数。長さは branching のべき乗です。
branching: 内部ノードあたりの子の数。
出力
[value, evaluated] を返します。根のミニマックス値と、評価した葉の数です。
制約
2 ≤ branching ≤ 5、leaves の長さ = branching^depth (1 ≤ depth ≤ 8)、葉は最大 10,000 個
-1,000 ≤ 各葉 ≤ 1,000
例
入力：
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
期待される出力：
[3, 7]解説
1 つ目の MIN ノードは 3, 12, 8 を見て 3 を返すので alpha = 3。2 つ目の MIN ノードは 2 を見て beta = 2 ≤ alpha となり、4 と 6 は飛ばされます。3 つ目は 14, 5, 2 を見て 2 を返します。根の値は max(3, 2, 2) = 3 で、9 個中 7 個の葉を調べました。
入力：
leaves = [5, 6, 7, 4]
branching = 2
期待される出力：
[5, 4]解説
左の MIN ノードは 5 と 6 を評価して 5 を返すので alpha = 5。右の MIN ノードは 7 (beta = 7)、続いて 4 (beta = 4 ≤ 5) を評価します。4 個すべての葉が評価され、値は 5 です。
参考資料
-
例 1 未実行入力：
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2] branching = 3期待される出力：[3, 7]あなたの出力 -
例 2 未実行入力：
leaves = [5, 6, 7, 4] branching = 2期待される出力：[5, 4]あなたの出力
提出時に非公開テスト4件も実行されます。 失敗したテストがあれば、そのテストが表示されます。チャレンジを解くとすべて見られます。
Online JavaScript Runner
Write, run, and debug JavaScript or Node.js online in a full-featured browser IDE. Work with multiple files and packages, save your workspace, and collaborate in real time.
⚡ この JavaScript（Node.js）オンライン実行ツールについて
CodeUtility JavaScript Executor は、ブラウザ上で最新の JavaScript コードを、 セットアップ不要ですぐに実行できるツールです。実際の Node.js 環境でサンドボックス化されたコンテナ内にて安全に実行し、 16、18、20 の各バージョンに対応しています。
Node.js のスニペットのテスト、ES6+ 構文の確認、ループ・関数・配列・Promise・async/await といった JavaScript の基本概念の学習に最適です。
アルゴリズムの検証や小さなスクリプトのデバッグ、実行時ロジックの試行にも使えます。ローカルに Node をインストールせずに済むので、 学習者、バックエンド開発者、ブラウザだけで素早く JavaScript を実行したい方にぴったりです。
同じ実行環境で、複数ファイル対応エディター、分離された実行ターミナル、ランタイム別ライブラリ、永続ワークスペース、共有、リアルタイム共同作業を利用できます。
この実行環境の使い方
ランタイムを選択し、ファイルを開くか作成してコードを記述し、［実行］を選択します。出力はターミナルに表示されます。サインインしたユーザーは、ワークスペースにファイルを保存し、ライブラリをインストールして、共有を通じて共同作業できます。
- バージョンを選択して現在のファイルを編集するか、ワークスペース内の別のファイルを開きます。
- コードを実行し、求められた場合はターミナルに入力して、保存された実行履歴を確認します。
- 複数のコードスニペットが必要な作業では、ライブラリ、ワークスペースツール、共有、チャットを利用します。
💡 初心者向け Node.js 基本ガイド
1. 変数と定数の宣言
let または const はブロックスコープの変数用です。const は定数に使います。
let x = 10;
const PI = 3.14;
let name = "Alice";
let isActive = true;2. 条件分岐（if / switch）
制御フローには if、else if、else、switch を使います。
let x = 2;
if (x === 1) {
console.log("1");
} else if (x === 2) {
console.log("2");
} else {
console.log("その他");
}
switch (x) {
case 1:
console.log("1");
break;
case 2:
console.log("2");
break;
default:
console.log("その他");
}3. ループ
データの反復処理には for、while、forEach を使います。
for (let i = 0; i < 3; i++) {
console.log(i);
}
let n = 3;
while (n > 0) {
console.log(n);
n--;
}4. 配列
配列は順序付きの値のリストを保持します。インデックスでアクセスします。
let fruits = ["apple", "banana", "cherry"];
console.log(fruits[0]);
console.log(fruits.length);5. 配列操作
push、pop、slice、reverse などのメソッドを使います。
fruits.push("kiwi");
fruits.pop();
console.log(fruits.slice(0, 2));
console.log(fruits.reverse());
let squares = [1, 2, 3, 4, 5].map(x => x * x);
console.log(squares);6. コンソール入出力
出力には console.log を、入力には readline モジュールを使います。
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question("お名前は？ ", name => {
console.log(`こんにちは、${name}`);
rl.close();
});7. 関数
関数は宣言または関数式で定義できます。モダンな JavaScript ではアロー関数がよく使われます。
function greet(name) {
return `こんにちは、${name}`;
}
const add = (a, b) => a + b;
console.log(greet("Alice"));
console.log(add(2, 3));8. オブジェクト（マップ）
オブジェクトはキーと値の組を保持します。辞書やマップに似ています。
let person = { name: "Bob", age: 25 };
console.log(person.name);
console.log(person["age"]);
// ES6 の Map
const map = new Map();
map.set("a", 1);
console.log(map.get("a"));9. 例外処理
try、catch、finally を使って安全にエラー処理します。
try {
throw new Error("問題が発生しました");
} catch (e) {
console.log(e.message);
} finally {
console.log("必要なら後処理");
}10. ファイル入出力
Node.js の fs モジュールでファイルの読み書きを行います。
const fs = require("fs");
fs.writeFileSync("test.txt", "Hello File");
const data = fs.readFileSync("test.txt", "utf8");
console.log(data);11. 文字列操作
trim()、toUpperCase()、replace()、split() などを使います。
let text = " Hello World ";
console.log(text.trim());
console.log(text.toUpperCase());
console.log(text.replace("Hello", "Hi"));
console.log(text.split(" "));12. クラスとオブジェクト
ES6+ は class 構文で OOP をサポートします。
class Person {
constructor(name) {
this.name = name;
}
greet() {
return `こんにちは、私は ${this.name} です`;
}
}
const p = new Person("Alice");
console.log(p.greet());13. 参照
JavaScript のオブジェクトや配列は参照で渡されます。
function update(arr) {
arr.push("changed");
}
let data = ["original"];
update(data);
console.log(data); // ["original", "changed"] になる