概要

各照明について、初期状態とスイッチを押す回数から最終的な ON/OFF を求める問題です。スイッチを押す回数の偶奇だけに注目すれば答えが決まります。

考察

重要な気づき：スイッチの偶奇だけが重要

スイッチを 1 回押すと状態が反転します。もう 1 回押すと元に戻ります。つまり：

• 偶数回押す → 状態は元のまま（反転が打ち消し合う）
• 奇数回押す → 状態は 1 回だけ反転した結果と同じ

具体例で確認しましょう。初期状態が ON の照明について：

押す回数 \(K\)	状態の変化	最終状態
1	ON → OFF	OFF
2	ON → OFF → ON	ON
3	ON → OFF → ON → OFF	OFF
4	ON → OFF → ON → OFF → ON	ON

このように、偶数回なら初期状態と同じ、奇数回なら初期状態の反転になります。

素朴なアプローチではなぜ TLE になるか

\(K_i\) は最大 \(10^9\) にもなります。スイッチを実際に \(K_i\) 回シミュレーションすると、1 つの照明だけで \(10^9\) 回の操作が必要になり、到底間に合いません。

解決策

上記の気づきから、\(K_i\) の値そのものではなく \(K_i \mod 2\)（偶数か奇数か）だけを見れば、\(O(1)\) で各照明の最終状態を判定できます。

アルゴリズム

各照明 \(i\) について以下を行います：

1. 初期状態 \(S_i\) とスイッチを押す回数 \(K_i\) を読み取る。
2. \(K_i\) が偶数なら、状態は変わらないのでそのまま \(S_i\) を出力する。
3. \(K_i\) が奇数なら、状態が反転するので、\(S_i\) が Yes なら No を、No なら Yes を出力する。

計算量

• 時間計算量: \(O(N)\) — 各照明について \(O(1)\) の判定を \(N\) 回行う
• 空間計算量: \(O(1)\) — 各照明の情報を都度処理するだけで、まとめて保持する必要がない

実装のポイント

• 入力は split() で文字列 \(S_i\) と整数 \(K_i\) を分けて読み取ります。\(K_i\) は文字列として読まれるので int() への変換を忘れないようにしましょう。

• \(K_i\) が最大 \(10^9\) ですが、Python の整数は任意精度なのでオーバーフローの心配はありません。

• 偶奇の判定は k % 2 == 0 で簡潔に書けます。

  ソースコード

N = int(input())
for _ in range(N):
    s, k = input().split()
    k = int(k)
    if k % 2 == 0:
        print(s)
    else:
        print("No" if s == "Yes" else "Yes")

---

この解説は claude4.6opus-thinking によって生成されました。