結果

問題 No.1770 N言っちゃダメゲーム (6)
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:20:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,134 bytes
コンパイル時間 737 ms
コンパイル使用メモリ 77,256 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-14 13:21:43
合計ジャッジ時間 5,634 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// num_good_options[s]: プレイヤーが合計 s を受け取った際、
//                      次に相手を負けさせることができる自分の「良い手」の数。
// first_good_option[s]: num_good_options[s] == 1 の場合、その唯一の「良い手」となる整数の値。
std::vector<int> num_good_options;
std::vector<int> first_good_option;
int N_val, K_val;

// プレイヤーが状態 (current_sum, prev_move_by_opponent) を受け取った場合に負けるかどうかを判定する関数。
// prev_move_by_opponent は、相手が current_sum を作るために加算した数。
bool does_player_lose(int current_sum, int prev_move_by_opponent) {
    // current_sum >= N_val の場合は既に前のプレイヤーがN以上を宣言して負けている。
    // この関数は current_sum < N_val の状況で呼ばれることを想定。

    int N_opts = num_good_options[current_sum];
    int F_opt = first_good_option[current_sum];

    if (N_opts == 0) {
        return true; // プレイヤーには有効な「良い手」がないため負ける。
    }
    if (N_opts == 1 && F_opt == prev_move_by_opponent) {
        // プレイヤーには「良い手」が一つだけあるが、それが相手が直前に使った手なので禁止されている。よって負ける。
        return true; 
    }
    // 上記以外の場合、プレイヤーは有効な「良い手」を選べるので勝つ（負けない）。
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> N_val >> K_val;

    num_good_options.resize(N_val);
    first_good_option.resize(N_val);

    // s を N_val - 1 から 0 まで降順に計算
    // s: 現在のプレイヤーが受け取った合計値
    for (int s = N_val - 1; s >= 0; --s) {
        int current_s_num_good_options = 0;
        int current_s_first_good_option = 0; 

        // 現在のプレイヤーが取りうる手 k_try (1 から K_val まで) を試す
        for (int k_try = 1; k_try <= K_val; ++k_try) {
            if (s + k_try >= N_val) {
                // この手 k_try を選ぶと、合計が N_val 以上になり、現在のプレイヤーが負ける。
                // これは「良い手」ではない。
                // k_try は昇順なので、これ以上大きな k_try も同様。ループを打ち切る。
                break; 
            }

            // 現在のプレイヤーが k_try を選んだ場合、相手は合計 (s + k_try) を受け取り、
            // その合計を作った手は k_try となる。
            // 現在のプレイヤーがこの手 k_try で勝つのは、相手が状態 (s + k_try, k_try) で負ける場合。
            if (does_player_lose(s + k_try, k_try)) {
                current_s_num_good_options++;
                if (current_s_num_good_options == 1) {
                    current_s_first_good_option = k_try;
                }
                if (current_s_num_good_options == 2) {
                    // 「良い手」が2つ見つかれば十分。
                    // (相手がどちらか一方の手を禁止しても、もう一方が使えるため)
                    break; 
                }
            }
        }
        num_good_options[s] = current_s_num_good_options;
        // num_good_options[s]が0の場合、first_good_option[s]は初期値0のまま。
        // num_good_options[s]が2以上の場合、first_good_option[s]は最初に見つかった「良い手」。
        // does_player_lose関数内では、num_good_optionsが1の場合のみfirst_good_optionの値が重要になるので、これで問題ない。
        if (current_s_num_good_options > 0) { // current_s_num_good_optionsが0の時に初期値0以外が入らないように
             first_good_option[s] = current_s_first_good_option;
        } else {
             first_good_option[s] = 0; // 念のため
        }
    }

    std::vector<int> winning_first_moves;
    // あなた(最初のプレイヤー)は合計0からスタート。相手の「直前の手」は存在しないので0(ダミー値)とする。
    // あなたは x (1 から K_val) を宣言する。相手は状態 (x, x) を受け取る。
    // あなたが勝つのは、相手が状態 (x, x) で負けるような x が存在する場合。
    for (int x = 1; x <= K_val; ++x) {
        if (x >= N_val) { 
            // あなたが宣言する数 x が N_val 以上なら、あなた自身の負け。
            break;
        }
        if (does_player_lose(x, x)) {
            winning_first_moves.push_back(x);
        }
    }

    if (winning_first_moves.empty()) {
        std::cout << 0 << "\n";
    } else {
        // winning_first_moves は自動的に昇順になる (x を1から昇順に試しているため)
        for (size_t i = 0; i < winning_first_moves.size(); ++i) {
            std::cout << winning_first_moves[i] << "\n";
        }
    }

    return 0;
}
0