概要

各照明について、スイッチを \(K_i\) 回押した後の最終的な状態（ONかOFFか）を求める問題です。

考察

スイッチを1回押すと照明の状態は反転します（ON \(\to\) OFF、または OFF \(\to\) ON）。 ここで、スイッチを2回押した場合を考えてみましょう。 - ONの状態で2回押す：ON \(\to\) OFF \(\to\) ON - OFFの状態で2回押す：OFF \(\to\) ON \(\to\) OFF

このように、スイッチを2回押すと元の状態に戻るという性質があります。 したがって、スイッチを押す回数 \(K_i\) について、以下のことが言えます。 - \(K_i\) が偶数のとき：最終的な状態は初期状態と同じ - \(K_i\) が奇数のとき：最終的な状態は初期状態から反転する

もし問題文の通りに \(K_i\) 回の反転を for ループなどで愚直にシミュレーションしてしまうと、\(K_i\) は最大で \(10^9\) になるため、制限時間に間に合わず TLE（実行時間オーバー）となってしまいます。 しかし、上記のように \(K_i\) の「偶奇（2で割った余り）」に注目すれば、ループを回すことなく一瞬で最終状態を判定できます。

アルゴリズム

各照明 \(i\) について以下の処理を行います。 1. \(K_i\) を 2 で割った余りを求める。 2. 余りが 1（奇数）の場合： - 初期状態 \(S_i\) が Yes なら No を出力結果に追加する。 - 初期状態 \(S_i\) が No なら Yes を出力結果に追加する。 3. 余りが 0（偶数）の場合： - 初期状態 \(S_i\) をそのまま出力結果に追加する。

すべての照明に対する処理が終わったら、結果を改行区切りで出力します。

計算量

• 時間計算量: \(O(N)\)
  • 各照明に対する偶奇の判定と状態の反転は \(O(1)\) で行えます。これを \(N\) 回繰り返すため、全体の時間計算量は \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 入力データの一括読み込みや、出力する結果のリストを保存するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: 入出力のデータ量が多いため（\(N \leq 10^5\)）、Pythonでは標準の input() や print() を複数回呼ぶよりも、sys.stdin.read().split() で一括読み込みし、sys.stdout.write() と join を使って一括出力すると実行時間を大幅に短縮できます。

• 偶奇の判定: K % 2 == 1（奇数）や K % 2 == 0（偶数）で判定できます。より高度な書き方として、ビット演算 K & 1 を使って奇数判定を行うことも可能です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    results = []
    idx = 1
    for _ in range(N):
        S = input_data[idx]
        K = int(input_data[idx+1])
        idx += 2
        
        if K % 2 == 1:
            if S == "Yes":
                results.append("No")
            else:
                results.append("Yes")
        else:
            results.append(S)
            
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。