結果
| 問題 |
No.3112 Decrement or Mod Game
|
| コンテスト | |
| ユーザー |
 aaaaaaaaaaa
|
| 提出日時 | 2025-04-19 11:21:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,807 bytes |
| コンパイル時間 | 974 ms |
| コンパイル使用メモリ | 84,912 KB |
| 実行使用メモリ | 814,592 KB |
| 最終ジャッジ日時 | 2025-04-19 11:22:02 |
| 合計ジャッジ時間 | 4,521 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | MLE * 1 -- * 64 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
// Memoization table: map key is pair<a, b>, value is pair<Alice_wins, Bob_wins> from state (a, b).
// Note: The state (a, b) is canonicalized such that a >= b inside the recursive function where it's the turn of the player with the larger number's turn's equivalent.
// However, the recursive calls themselves might not maintain this order, so memoization key should be pair<a,b> directly.
map<pair<long long, long long>, pair<bool, bool>> memo;
// Function to check if the player whose turn it is wins from state (a, b)
// is_alice_turn: true if it's Alice's turn, false if it's Bob's turn
// Returns true if the current player wins, false otherwise.
bool can_win(long long a, long long b, bool is_alice_turn) {
// Base cases: If a number is 0, the player whose number is 0 has lost.
// The player whose turn it is cannot make a move if their number is 0 (game already ended).
// So, if it's Alice's turn and a is 0, she lost on a previous turn.
// If it's Bob's turn and b is 0, he lost on a previous turn.
// Conversely, if it's Alice's turn and b is 0, Bob lost on a previous turn, so Alice wins.
// If it's Bob's turn and a is 0, Alice lost on a previous turn, so Bob wins.
if (a == 0) {
return !is_alice_turn; // If a=0, Alice lost. If it was Alice's turn, she loses. If it was Bob's turn, Bob wins.
}
if (b == 0) {
return is_alice_turn; // If b=0, Bob lost. If it was Alice's turn, she wins. If it was Bob's turn, he loses.
}
// Canonicalize state for memoization: always store (max, min)
pair<long long, long long> state = {a, b};
if (a < b) swap(state.first, state.second);
// Check memoization table
if (memo.count(state)) {
if (a >= b) { // Original state was a >= b
if (is_alice_turn) return memo[state].first;
else return memo[state].second;
} else { // Original state was a < b
if (is_alice_turn) return memo[state].second; // If Alice had smaller number (b), result corresponds to Bob having larger number (state.first) in canonical state.
else return memo[state].first; // If Bob had smaller number (a), result corresponds to Alice having larger number (state.first) in canonical state.
}
}
bool current_player_wins;
if (is_alice_turn) {
// Alice's turn (a, b)
// Alice wins if any of her moves lead to a state where Bob loses.
// Move 1: Decrease a
// If a-1 becomes 0, Alice wins immediately.
// Otherwise, check if Bob loses from (a-1, b).
if (a > 0 && (a - 1 == 0 || !can_win(a - 1, b, !is_alice_turn))) {
current_player_wins = true;
} else {
// Move 2: Modulo a % b (if a >= b)
if (a >= b) {
// If a % b becomes 0, Alice wins immediately.
// Otherwise, check if Bob loses from (a % b, b).
if (a % b == 0 || !can_win(a % b, b, !is_alice_turn)) {
current_player_wins = true;
} else {
// Neither immediate win nor modulo move leads to Bob losing.
// Consider special decrease move patterns based on a/b quotient.
long long q = a / b;
if (q == 1) { // b <= a < 2b. Alice can reach (b, b) by decreasing.
// If Bob loses from (b, b), Alice wins.
current_player_wins = !can_win(b, b, !is_alice_turn);
} else { // a >= 2b. Alice can "fast-forward" decreases.
// If Bob loses from (a%b + b, b), Alice wins.
current_player_wins = !can_win(a % b + b, b, !is_alice_turn);
}
}
} else {
// a < b, modulo not possible. Alice can only decrease.
// Check if Bob loses from (a-1, b). This was already covered by the first 'if' block.
// If we reached here, it means decreasing to a-1 did not lead to immediate win or Bob losing.
current_player_wins = false; // No winning move found
}
}
} else {
// Bob's turn (a, b)
// Bob wins if any of his moves lead to a state where Alice loses.
// Move 1: Decrease b
// If b-1 becomes 0, Bob wins immediately.
// Otherwise, check if Alice loses from (a, b-1).
if (b > 0 && (b - 1 == 0 || !can_win(a, b - 1, !is_alice_turn))) {
current_player_wins = true;
} else {
// Move 2: Modulo b % a (if b >= a)
if (b >= a) {
// If b % a becomes 0, Bob wins immediately.
// Otherwise, check if Alice loses from (a, b % a).
if (b % a == 0 || !can_win(a, b % a, !is_alice_turn)) {
current_player_wins = true;
} else {
// Neither immediate win nor modulo move leads to Alice losing.
// Consider special decrease move patterns based on b/a quotient.
long long q = b / a;
if (q == 1) { // a <= b < 2a. Bob can reach (a, a) by decreasing.
// If Alice loses from (a, a), Bob wins.
current_player_wins = !can_win(a, a, !is_alice_turn);
} else { // b >= 2a. Bob can "fast-forward" decreases.
// If Alice loses from (a, b%a + a), Bob wins.
current_player_wins = !can_win(a, b % a + a, !is_alice_turn);
}
}
} else {
// b < a, modulo not possible. Bob can only decrease.
// Check if Alice loses from (a, b-1). This was already covered by the first 'if' block.
// If we reached here, it means decreasing to b-1 did not lead to immediate win or Alice losing.
current_player_wins = false; // No winning move found
}
}
}
// Store and return result
if (a >= b) {
if (is_alice_turn) memo[state].first = current_player_wins;
else memo[state].second = current_player_wins;
} else { // a < b
if (is_alice_turn) memo[state].second = current_player_wins;
else memo[state].first = current_player_wins;
}
return current_player_wins;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long A, B;
cin >> A >> B;
// Alice goes first
if (can_win(A, B, true)) {
cout << "Alice" << endl;
} else {
cout << "Bob" << endl;
}
return 0;
}