結果

問題 No.1267 Stop and Coin Game
ユーザー norioc
提出日時 2025-03-24 06:49:26
言語 Java
(openjdk 23)
結果
AC  
実行時間 502 ms / 2,000 ms
コード長 2,023 bytes
コンパイル時間 2,365 ms
コンパイル使用メモリ 80,880 KB
実行使用メモリ 75,932 KB
最終ジャッジ日時 2025-03-24 06:49:39
合計ジャッジ時間 12,590 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.HashMap;
import java.util.Scanner;

public class Main {
	static int N;
    static long V;
    static long[] A;
    static HashMap<Long, Boolean> memo = new HashMap<>();

    // 状態 (v, used) を一意のlong値にエンコードする
    static long encode(long v, int used) {
        return (((long) v) << 32) | (used & 0xffffffffL);
    }

    // 再帰関数：残りの値 v と使用済みビットマスク used に対して勝ち手かどうかを判定
    static boolean f(long v, int used) {
        long key = encode(v, used);
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // 勝ち手が見つからない場合は false
        boolean win = false;
        for (int i = 0; i < N; i++) {
            // すでに使われた数字ならスキップ
            if ((used & (1 << i)) != 0) continue;
            // v から A[i] を引けないならスキップ
            if (v - A[i] < 0) continue;

            int nu = used | (1 << i);
            // 相手が負ける状態になるなら、自分は勝ち
            if (!f(v - A[i], nu)) {
                memo.put(key, true);
                return true;
            }
        }
        memo.put(key, win);
        return win;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 入力の読み込み
        N = sc.nextInt();
        V = sc.nextLong();
        A = new long[N];
        long total = 0;
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextLong();
            total += A[i];
        }

        // すべての数値の合計が V 以下なら引き分け
        if (total <= V) {
            System.out.println("Draw");
            return;
        }

        // ゲーム開始時点 (v=V, used=0) の状態から勝ち手を判定
        boolean win = f(V, 0);
        if (win) {
            System.out.println("First");
        } else {
            System.out.println("Second");
        }
    }
}
0