概要

生徒の支持が変化する中で、候補者のどちらかの支持者が0人になったタイミングを求めるシミュレーション問題です。

考察

この問題は、生徒の支持状況を逐次更新しながら、高橋君と青木君の支持者数を管理していく必要があります。

素朴な方法として、毎回すべての生徒を見て支持者数を再計算する方法がありますが、これは各演説ごとに \(O(N)\) の計算が必要になり、全体で \(O(NM)\) となり、制約が \(N, M \leq 2 \times 10^5\) なので最大で \(4 \times 10^{10}\) の計算回数となり、時間内に収まりません（TLE）。

そこで、各生徒が現在どちらの候補者を支持しているかを記録し、演説ごとにその生徒の支持先を反転させると同時に、高橋君と青木君の支持者数をインクリメント／デクリメントすることで、定数時間で更新できるようにします。

さらに、各演説のたびにどちらかの支持者が0人になったかを確認すれば、シミュレーションが途中で終わるべきかどうか判断できます。

アルゴリズム

1. 初期状態で高橋君と青木君の支持者数をカウントする。
2. 各生徒の現在の支持者を記録する配列を用意する（True: 高橋君、False: 青木君など）。
3. 各演説について以下を行う：
   • 指定された生徒の支持先を反転させる。
   • 反転に伴い、対応する候補者の支持者数を更新する（支持を失った方は減らし、増えた方は増やす）。
   • 更新後にどちらかの候補者の支持者数が0人になっていれば、その演説番号を出力して終了。
4. すべての演説が終わっても支持者が残っている場合は -1 を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  （初期カウントに \(O(N)\)、各演説処理に \(O(1)\) × \(M\) 回）
• 空間計算量: \(O(N)\)
  （支持状況を保持する配列）

実装のポイント

• 生徒番号は1-indexedで与えられるので、内部処理では0-indexedに変換する必要がある（R[i] - 1）。

• 支持者数の変化は常に1人分だけなので、+=1, -=1 で正確に追跡可能。

• 当選が確定したら即座に return してプログラムを終了すること。

  ソースコード

import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    S = data[2]
    R = list(map(int, data[3:3+M]))
    
    # カウント初期化
    taka = S.count('T')
    aoki = S.count('A')
    
    # 各生徒の現在の支持者を管理する配列（True: Taka, False: Aoki）
    support = [True if c == 'T' else False for c in S]
    
    for i in range(M):
        r = R[i] - 1  # 0-indexedに変換
        
        if support[r]:  # 現在 高橋君を支持している
            taka -= 1
            aoki += 1
            support[r] = False
        else:  # 現在 青木君を支持している
            aoki -= 1
            taka += 1
            support[r] = True
        
        # 演説後にどちらかの支持者が0人になったかチェック
        if taka == 0 or aoki == 0:
            print(i + 1)
            return
    
    # すべての演説が終わった後も両方に支持者がいる場合
    print(-1)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。