結果

問題 No.1770 N言っちゃダメゲーム (6)
ユーザー lam6er
提出日時 2025-04-09 21:02:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,738 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,036 KB
実行使用メモリ 124,044 KB
最終ジャッジ日時 2025-04-09 21:04:00
合計ジャッジ時間 5,702 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    N, K = map(int, sys.stdin.readline().split())

    # Precompute for x in [0 ... N], whether (x, f) is a losing position.
    # We use a memoization approach but due to large N and K, this will not work for actual large cases.
    # This code is a theoretical approach and may not handle all cases efficiently.

    max_x = N
    F = [set() for _ in range(max_x + 1)]  # F[x] = set of f's where (x, f) is a losing position.

    for x in range(max_x, -1, -1):
        for f in range(0, K + 1):
            allowed_ds = []
            for d in range(1, K + 1):
                if d == f:
                    continue
                if x + d >= N:
                    continue
                allowed_ds.append(d)
            # Check if all allowed_ds lead to (x + d, d) being a winning position for opponent.
            # i.e., if for all d in allowed_ds, d is NOT in F[x + d]
            all_lead_to_win = True
            for d in allowed_ds:
                next_x = x + d
                if next_x >= N:
                    continue  # Opponent can't make this move, so skip
                if d in F[next_x]:
                    all_lead_to_win = False
                    break
            if all_lead_to_win:
                F[x].add(f)

    # Collect possible initial moves
    result = []
    for d in range(1, K + 1):
        if d >= N:
            continue  # invalid move, since adding d to 0 gives d >=N
        # Check if (d, d) is a losing position for Grant.
        if d in F[d]:
            result.append(d)

    if result:
        result.sort()
        for num in result:
            print(num)
    else:
        print(0)

if __name__ == '__main__':
    main()
0