結果

問題 No.3342 AAB Game
コンテスト
ユーザー 回転
提出日時 2025-11-14 17:12:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 2,847 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 79,484 KB
最終ジャッジ日時 2025-11-14 17:12:38
合計ジャッジ時間 6,456 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

# generated by AI
import sys
from typing import List  # <-- 変更点(1)：List をインポート

def solve(s: str) -> int:
    """
    事前計算された遷移行列を用いて、文字列sに対するNim値を計算する。
    """
    
    # --------------- C++コードから移植された定数 ----------------
    DIM = 3
    COL = 2
    
    # matAs[col][i][j] は、状態iから状態jへの遷移（文字col）を表す
    # C++コードの matAs[COL][DIM][DIM] に対応
    matAs = [
        # c = '0' (A)
        [
            [0, 1, 0],
            [1, 0, 0],
            [-2, 2, 1]
        ],
        # c = '1' (B)
        [
            [0, 0, 1],
            [-2, 1, 2],
            [1, 0, 0]
        ]
    ]
    
    # C++コードの vecP[DIM] に対応
    vecP = [0, 0, 1]
    # --------------------------------------------------------------

    # dpベクトル（状態ベクトル）の初期化
    dp = [0] * DIM
    dp[0] = 1
    
    # C++の apply 関数に相当する行列ベクトル積
    # 変更点(2)： list[int] -> List[int] に変更
    def apply_matrix(x: List[int], col: int) -> List[int]:
        """
        現在の状態ベクトル x に、文字 col に対応する遷移行列を掛ける。
        z = x * M (xは行ベクトル)
        z[j] = sum(x[i] * M[i][j] for i)
        """
        z = [0] * DIM
        M = matAs[col]
        
        for j in range(DIM):
            for i in range(DIM):
                z[j] += x[i] * M[i][j]
        return z

    # 文字列sを左から読み込み、状態を更新していく
    for char_code in s:
        col = int(char_code) # '0' または '1'
        dp = apply_matrix(dp, col)

    # 最終的な状態ベクトル dp と 終端ベクトル vecP の内積を計算
    res = 0
    for i in range(DIM):
        res += dp[i] * vecP[i]
        
    return res

def main():
    """
    メインの実行部分
    """
    # sys.stdin.readline を使うと高速
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return  # 入力が空の場合
            
        n = int(n_str.strip())
        s = sys.stdin.readline().strip()
        
        if len(s) != n:
            # 必要に応じてエラーハンドリング
            pass

        # 'A'を'0'に、'B'を'1'に変換
        s_numeric = s.replace('A', '0').replace('B', '1')
        
        # solve関数を呼び出してNim値（Grundy数）を計算
        nim_value = solve(s_numeric)
        
        # Nim値が0なら後手必勝(Bob)、0以外なら先手必勝(Alice)
        if nim_value != 0:
            print("Alice")
        else:
            print("Bob")

    except EOFError:
        pass
    except Exception as e:
        print(f"An error occurred: {e}", file=sys.stderr)

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