結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー りすりす/TwoSquirrels
提出日時 2025-11-11 03:30:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,199 bytes
コンパイル時間 1,627 ms
コンパイル使用メモリ 138,888 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-11-13 21:15:56
合計ジャッジ時間 7,472 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1 -- * 1
other -- * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

// モンテカルロ法 by Gemini 2.5 Pro

#include <iostream>
#include <vector>
#include <string>
#include <random> // 乱数生成のため
#include <map>   // 結果の集計のため
#include <algorithm> // for_each など (デバッグ用)

using namespace std;

// 乱数生成器
random_device rd;
mt19937 gen(rd());

// プレイヤー
enum Player { ALICE, BOB };

// ゲーム結果
enum Result { ALICE_WIN, BOB_WIN, DRAW };

/**
 * @brief 1回のゲームシミュレーション (ヒューリスティック導入版)
 * @param N 頂点数
 * @param adj グラフの隣接リスト
 * @return ゲーム結果
 */
Result simulate_game(int N, const vector<vector<int>>& adj) {
    int current_v = 1; // スタートは頂点1
    Player current_player = ALICE;
    
    // 最大手数を 2*N に設定。
    int max_steps = 2 * N; 
    
    for (int steps = 0; steps < max_steps; ++steps) {
        
        // 現在の頂点から移動可能な先のリスト
        const vector<int>& neighbors = adj[current_v];
        
        if (neighbors.empty()) {
            // 移動先がない場合、現在のプレイヤーの負け
            return (current_player == ALICE) ? BOB_WIN : ALICE_WIN;
        }
        
        // --- ヒューリスティックによる選択 ---
        
        vector<int> winning_moves; // 1. (即勝利)
        vector<int> safe_moves;    // 2. (即敗北回避)
        
        for (int next_v : neighbors) {
            // 1. next_v が行き止まり（出次数 0）か？
            if (adj[next_v].empty()) {
                winning_moves.push_back(next_v);
            }

            // 2. next_v に行くと、相手が即勝利 (行き止まり) に行けるか？
            bool leads_to_loss = false;
            for (int w : adj[next_v]) { // next_v のさらに先
                if (adj[w].empty()) { // w が行き止まり
                    leads_to_loss = true;
                    break;
                }
            }
            if (!leads_to_loss) {
                safe_moves.push_back(next_v);
            }
        }
        
        int next_node;
        
        // 優先度 1: 必勝手があるか？
        if (!winning_moves.empty()) {
            // 必勝手の中からランダムに選ぶ
            uniform_int_distribution<> dis(0, winning_moves.size() - 1);
            next_node = winning_moves[dis(gen)];
        }
        // 優先度 2: 安全な手（即敗北しない手）があるか？
        else if (!safe_moves.empty()) {
            // 安全な手の中からランダムに選ぶ
            uniform_int_distribution<> dis(0, safe_moves.size() - 1);
            next_node = safe_moves[dis(gen)];
        }
        // 優先度 3: どう動いても負け or 通常のランダム
        else {
            // (safe_movesが空) = (neighbors全てがleads_to_loss)
            // 諦めて、元の候補からランダムに選ぶ
            uniform_int_distribution<> dis(0, neighbors.size() - 1);
            next_node = neighbors[dis(gen)];
        }

        current_v = next_node; // 選んだ頂点に移動
        
        // プレイヤー交代
        current_player = (current_player == ALICE) ? BOB : ALICE;
    }
    
    // 最大手数を超えた場合は「引き分け」と判定
    return DRAW;
}

int main() {
    int N, M;
    cin >> N >> M;
    
    // Nが0や負の場合のゼロ除算を避ける
    if (N <= 0) N = 1; 

    // 隣接リストでグラフを表現 (1-indexedで扱う)
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    
    // シミュレーション回数 (要求仕様)
    // オーバーフロー防止のため long long を使用
    const long long NUM_SIMULATIONS = 50000000LL / N; 
    
    map<Result, long long> results_count; // 回数が大きくなる可能性があるので long long
    results_count[ALICE_WIN] = 0;
    results_count[BOB_WIN] = 0;
    results_count[DRAW] = 0;
    
    // 指定回数シミュレーションを実行
    for (long long i = 0; i < NUM_SIMULATIONS; ++i) {
        Result res = simulate_game(N, adj);
        results_count[res]++;
    }
    
    // --- 結果の推定 ---
    
    // デバッグ用に各回数を cerr (標準エラー出力) に表示
    cerr << "--- Simulation Results ---" << endl;
    cerr << "Total Simulations: " << NUM_SIMULATIONS << endl;
    cerr << "Alice Wins: " << results_count[ALICE_WIN] << endl;
    cerr << "Bob Wins:   " << results_count[BOB_WIN] << endl;
    cerr << "Draws:      " << results_count[DRAW] << endl;
    cerr << "--------------------------" << endl;

    // 最も多く観測された結果を cout (標準出力) に出力する
    if (results_count[ALICE_WIN] >= results_count[BOB_WIN] && 
        results_count[ALICE_WIN] >= results_count[DRAW]) {
        cout << "Alice" << endl;
    } else if (results_count[BOB_WIN] >= results_count[ALICE_WIN] && 
               results_count[BOB_WIN] >= results_count[DRAW]) {
        cout << "Bob" << endl;
    } else {
        cout << "Draw" << endl;
    }
    
    return 0;
}
0