概要

各照明の初期状態とスイッチを押す回数が与えられ、最終的な状態を求める問題です。スイッチを押すと照明の状態が反転します。

考察

各照明について、スイッチを押す回数 \(K_i\) が奇数の場合、状態は初期状態から反転します。偶数の場合、状態は初期状態と同じままです。これは、スイッチを1回押すと状態が反転し、2回押すと元に戻るという性質から導かれます。つまり、\(K_i\) を2で割った余りに注目することで、最終状態を効率的に判定できます。

アルゴリズム

1. 各照明について、初期状態が “Yes” なら1、”No” なら0として数値で表現します。
2. スイッチを押す回数 \(K_i\) が奇数か偶数かを判定します。
3. \(K_i\) が奇数の場合、初期状態を反転させ（1なら0に、0なら1に）、偶数の場合は初期状態をそのまま採用します。
4. 最終状態を “Yes” または “No” に変換して出力します。

計算量

• 時間計算量: \(O(N)\) 各照明に対する処理は定数時間で行えるため、入力サイズ \(N\) に比例します。
• 空間計算量: \(O(N)\) 結果を格納するためのリストのサイズが \(N\) です。

実装のポイント

• 初期状態を文字列から数値（0または1）に変換することで、状態の反転を簡単に行えます。

• 剰余演算（% 2）を用いて、スイッチを押す回数の偶奇を判定します。

• 状態の反転は 1 - initial_state という式で簡単に表現できます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    results = []
    for i in range(1, n + 1):
        parts = data[i].split()
        s = parts[0]
        k = int(parts[1])
        
        initial_state = 1 if s == "Yes" else 0
        total_flips = k
        final_state = initial_state
        
        if total_flips % 2 == 1:
            final_state = 1 - initial_state
            
        results.append("Yes" if final_state == 1 else "No")
    
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。