// モンテカルロ法 by Gemini 2.5 Pro #include #include #include #include // 乱数生成のため #include // 結果の集計のため #include // 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>& 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& neighbors = adj[current_v]; if (neighbors.empty()) { // 移動先がない場合、現在のプレイヤーの負け return (current_player == ALICE) ? BOB_WIN : ALICE_WIN; } // --- ヒューリスティックによる選択 --- vector winning_moves; // 1. (即勝利) vector 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> 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 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; }