アルファベータ枝刈り

アルファベータ枝刈りはミニマックスと同じ答えを出しつつ、結果を変えられない枝を飛ばします。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

例

例 1

入力：
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 個の葉を調べました。

例 2

入力：
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 Java Compiler

Write, compile, run, and debug Java code online in a full-featured browser IDE. Work with multiple files, save your workspace, and share or collaborate in real time - no setup required.

バージョン

プリインストール済みライブラリ

🚀 260,408 合計実行 (5,854 今月)

出力

Javaのコーディングチャレンジで練習

このエディタで実践的な問題を解こう。サンプルテストを実行し、提出してAIコードレビューを受けられます。

すべてのJavaチャレンジ

簡単

Rectangle Perimeter

Compute the perimeter of a rectangle from its sides.

学べること算術戻り値

BeginnerLearning-pathVariables

解答を見る（12 件）

簡単

Distance Between Points

Compute the straight-line distance between two points.

学べること三平方の定理平方根

BeginnerFunctionsLearning-pathmath

解答を見る（7 件）

簡単

Days in a Month

Return how many days a month has, including leap years.

学べること暦の規則補助関数

BeginnerConditionsFunctionsLearning-path

解答を見る（6 件）

簡単

Average of Three

Average three whole numbers.

学べること算術除算

BeginnerLearning-pathVariables

解答を見る（6 件）

簡単

2つのベクトルの内積

2つのベクトルを要素ごとに掛けて合計します。すべてのニューロンの中心となる計算です。

学べることベクトル内積

ニューラルネットワークai機械学習

解答を見る（4 件）

簡単

Largest of Three

Pick the largest of three numbers without a built-in max.

学べること比較条件の組み合わせ

BeginnerConditionsLearning-path

解答を見る（4 件）

簡単

素数判定

数が素数かどうかを判定してください。

学べること割り切れるかの判定ループの最適化

BeginnerLoopsNumbersStudent-beginner

解答を見る（3 件）

簡単

Number Triangle

Build a triangle of increasing numbers.

学べること長くなる行行をまたぐカウンター

BeginnerLearning-pathNested-loopsPatterns

解答を見る（3 件）

簡単

アームストロング数

数が、その各桁の値を桁数乗して合計した値と等しいかどうかを判定します。

学べること桁の取り出し累乗

BeginnerNumbersStudent-beginner

解答を見る（3 件）

簡単

Row Sums

Add up every row of a grid.

学べること 2 次元リスト入れ子のループ

BeginnerGridsLearning-path

解答を見る（3 件）

簡単

Min and Max Together

Find the smallest and largest value in one pass.

学べること 1 回の走査複数の戻り値

ArraysBeginnerFunctionsLearning-path

解答を見る（3 件）

簡単

Count Pairs With a Sum

Count pairs of positions whose values add up to a target.

学べることインデックスの組二重カウントの回避

ArraysBeginnerLearning-pathNested-loops

解答を見る（3 件）

☕ このJavaオンライン実行ツールについて

CodeUtility Java Executorは、ブラウザ上で直接Javaプログラムを記述・実行できるツールです - インストールやJDKの設定、IDEは不要です。安全なサンドボックス上で動作し、実際のJavaランタイムバージョン8、11、17、21、そして最新に対応しています。

このツールは、本物のjavacコンパイラとJavaランタイム環境をクラウドで使用してコードをコンパイル・実行します。そのため、クラスやメソッド、ロジックをローカルとまったく同じ挙動でテストできます。

オブジェクト指向の練習、面接対策、統合前のスニペット検証など、あらゆる用途で CodeUtility Java Executorは高速かつ信頼できる実行環境を提供し、どんなデバイスからでもすぐに本物のJavaコードを実行できます。

単なるコードランナーではありません

同じ実行環境で、複数ファイル対応エディター、分離された実行ターミナル、ランタイム別ライブラリ、永続ワークスペース、共有、リアルタイム共同作業を利用できます。

この実行環境の使い方

ランタイムを選択し、ファイルを開くか作成してコードを記述し、［実行］を選択します。出力はターミナルに表示されます。サインインしたユーザーは、ワークスペースにファイルを保存し、ライブラリをインストールして、共有を通じて共同作業できます。

バージョンを選択して現在のファイルを編集するか、ワークスペース内の別のファイルを開きます。
コードを実行し、求められた場合はターミナルに入力して、保存された実行履歴を確認します。
複数のコードスニペットが必要な作業では、ライブラリ、ワークスペースツール、共有、チャットを利用します。

コーディングを開始する

バージョン実行する前にランタイムを選択します。インストールされたライブラリは、選択した言語バージョンに属します。
「開いているファイル」には、開いていないテキストファイルがリストされます。1 つを選択すると、利用可能なエディタータブで開きます。
「実行」は、プログラムで使用可能なワークスペースを使用してアクティブなファイルを実行します。
Stop は、制限時間前に現在の実行を終了します。
詳細モードでは、ファイルエクスプローラーと移動可能でサイズ変更可能なターミナルを備えた IDE レイアウトが開きます。

ワークスペースとライブラリ

新しいファイルは、選択した親ディレクトリにファイルを作成し、エディタで開きます。
新しいフォルダーは、サポートされているネストの深さまでのディレクトリを作成します。
ファイルをアップロードすると、1 つ以上の安全なファイルがディレクトリに追加されます。
ダウンロードでは、ファイルまたは圧縮されたディレクトリがデバイスに保存されます。
コピーは、ワークスペースファイルまたはディレクトリを複製します。
[名前の変更] を実行すると、ファイル名が変更され、開いているタブと履歴が更新されます。
Move は項目を再配置します。ファイルやディレクトリもドラッグできます。
削除は、確認後に項目を削除し、開いているエディタータブを閉じます。
プリインストールされたライブラリには、このランタイムにすでに含まれているパッケージが表示されます。
Add Lib は、アカウントと選択したランタイム用のプライベートパッケージをインストールします。

ターミナルとサポート

実行履歴により、前と次の保存された出力が開きます。
出力をコピーすると、現在の端末テキストがコピーされます。
出力をクリアすると、確認後に保存されている実行出力がすべて削除されます。
Explain ではアクティブなコードを要約します。
[最近] では、最近の説明と結果が開きます。
設定により、フォント、テーマ、表示されるツールバーボタンが変更されます。

共有とコラボレーション

共有は、現在のファイル、ディレクトリ、またはワークスペース全体をスナップショットまたはライブワークスペースとして公開します。リンクへのアクセスと変更を保存できるユーザーを制御します。
ログには、共有ワークスペースに保存されたコラボレーターのアクションが記録されます。
チャットを共有すると、サインインした参加者はメッセージを送信したり、メンバーにメンションしたり、コードブロックを共有したり、オンラインまたは入力中のメンバーを確認したりできます。
ライブコラボレーションでは、コラボレーターのカーソルと保存されたファイルの更新が表示されます。表示専用ユーザーは、最新バージョンをロードすることも、一時的な編集を保存することもできます。

割り当てと制限

実行時間は、サーバーの実行ごとに 20 秒に制限されます。より早く終了したい場合は、「停止」を使用します。
ワークスペースストレージでは、サインインしているユーザーのワークスペースと言語ごとに、ファイル 100 個、ディレクトリ 100 個、合計 10 MiB が許可されます。
ファイルとフォルダーは、ファイルごとに 1 MiB、ネストされたディレクトリレベルは 5 に制限されます。コードによって生成されたファイルは、同じクォータに従います。
プライベートライブラリは、アカウントおよびランタイムごとにインストールされるパッケージが 10 個に制限されています。
共有スナップショットには、ファイルあたり 1 MiB、合計 2 MiB まで、最大 100 個のファイルを含めることができます。
共有の招待は、共有ごとに最大 25 人をサポートし、アクセス権と保存権限は個別に管理されます。
チャットの共有では、メッセージあたり 2,000 文字、共有あたり 10,000 メッセージが許可されます。
クォータの強制は、コードの実行中にも適用されます。ファイル数、サイズ、ストレージ、またはネストの制限を超える書き込みは安全に拒否されます。

知っておくと便利 信頼できるコードのみを実行し、パッケージをインストールしてください。実行は分離され制限されていますが、プログラムは強制クォータまで書き込み可能なワークスペース内のファイルを変更できます。

💡 上のエディタで試せるJavaの基本とサンプル

1. 変数と定数の宣言

Javaでは各変数の型を宣言する必要があります。定数にはfinalを使います。

int age = 30;
double pi = 3.14159;
char grade = 'A';
String name = "Alice";
boolean isActive = true;

// 定数
final int MAX_USERS = 100;
final String COMPANY = "CodeUtility";

2. 条件分岐（if / switch）

制御フローにはif、else if、switchを使います。

int x = 2;
if (x == 1) {
    System.out.println("1");
} else if (x == 2) {
    System.out.println("2");
} else {
    System.out.println("その他");
}

switch (x) {
    case 1:
        System.out.println("1");
        break;
    case 2:
        System.out.println("2");
        break;
    default:
        System.out.println("その他");
}

3. ループ

繰り返しにはfor、while、do-whileを使います。

for (int i = 0; i < 3; i++) {
    System.out.println(i);
}

int n = 3;
while (n > 0) {
    System.out.println(n);
    n--;
}

4. 配列

配列は同じ型の要素を固定長で保持します。

int[] numbers = {10, 20, 30};
System.out.println(numbers[1]);

5. ArrayListの操作

ArrayListは可変長のリストに使います。

import java.util.ArrayList;

ArrayList<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.remove(Integer.valueOf(2));

for (int num : nums) {
    System.out.print(num + " ");
}

6. コンソール入出力

入力にはScanner、出力にはSystem.outを使います。

import java.util.Scanner;

Scanner scanner = new Scanner(System.in);
System.out.print("お名前を入力してください: ");
String name = scanner.nextLine();
System.out.println("こんにちは、" + name);

7. メソッド

戻り値の型と引数を指定してメソッドを定義します。

public static int add(int a, int b) {
    return a + b;
}

System.out.println(add(3, 4));

8. HashMap

HashMapはキーと値のペアを格納するために使います。

import java.util.HashMap;

HashMap<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
System.out.println(ages.get("Alice"));

9. 例外処理

実行時例外はtryとcatchで処理します。

try {
    throw new Exception("問題が発生しました");
} catch (Exception e) {
    System.out.println(e.getMessage());
}

10. ファイル入出力

ファイル操作にはjava.nio.fileのFilesとPathsを使います。

import java.nio.file.*;
import java.io.IOException;

Files.writeString(Paths.get("file.txt"), "こんにちは、ファイル");
String content = Files.readString(Paths.get("file.txt"));
System.out.println(content);

11. 文字列操作

Javaの文字列はlength()、substring()、contains()など多くのメソッドをサポートします。

String text = "Hello World";
System.out.println(text.length());
System.out.println(text.substring(0, 5));
System.out.println(text.contains("World"));

12. クラスとオブジェクト

Javaはクラスとインスタンスを用いたオブジェクト指向プログラミングをサポートします。

class Person {
    String name;
    Person(String name) {
        this.name = name;
    }
    void greet() {
        System.out.println("こんにちは、私は " + name);
    }
}

Person p = new Person("Alice");
p.greet();