概要

各演説で指定された生徒の支持が T と A の間で反転するので、支持者数を逐次更新し、どちらかの支持者数が \(0\) になった最初の演説番号を求めます。

考察

重要なのは「各演説で変わるのは たった1人 の支持だけ」という点です。
つまり、演説のたびに全員の支持を数え直す必要はありません。

• 素朴な方法：演説ごとに文字列 \(S\) 全体を見て T の数と A の数を数える
  すると \(1\) 回の確認に \(O(N)\)、全体で \(O(NM)\) となり、最大で \(2\times 10^5 \times 2\times 10^5\) と非常に大きく TLE になります。
• 改善の方向性：
  最初に T の人数 \(t\_cnt\) と A の人数 \(a\_cnt\) を数えておき、演説で生徒 \(R_i\) の支持が反転した分だけ（\(+1\) / \(-1\)）を更新する。

例えば、ある時点で \(t\_cnt=3, a\_cnt=2\) のときに T の生徒が反転すると
\(t\_cnt\) は \(2\)、\(a\_cnt\) は \(3\) に変わります。
このように「変更された1人分」だけ更新すれば十分で、各演説を \(O(1)\) で処理できます。

また、当選確定のチェックは「各演説の直後にのみ」なので、初期状態では \(0\) 人チェックをしない点に注意します（ただし制約で初期は両方 \(1\) 人以上）。

アルゴリズム

1. 文字列 \(S\) から初期の T の人数 \(t\_cnt\) を数える。\(a\_cnt = N - t\_cnt\) とする。
2. 演説 \(i=1..M\) について順に処理する：
   • 指定された生徒 \(r=R_i\)（\(0\)-indexed に直す）の現在の支持を確認する。
   • もし T なら A に反転し、\(t\_cnt--, a\_cnt++\)。
   • もし A なら T に反転し、\(a\_cnt--, t\_cnt++\)。
   • 更新後、\(t\_cnt==0\) または \(a\_cnt==0\) なら、その時点で当選確定なので \(i\) を出力して終了。
3. 最後までどちらも \(0\) にならなければ -1 を出力する。

計算量

• 時間計算量: \(O(N + M)\)（初期カウントが \(O(N)\)、各演説は \(O(1)\)）
• 空間計算量: \(O(N)\)（支持状態 \(S\) を保持）

実装のポイント

• 各演説で「その生徒が今どちらを支持しているか」が必要なので、\(S\) 自体も反転して更新します（これがないと複数回指定されるケースで破綻します）。

• Python では高速化のために sys.stdin.buffer.read() で一括入力し、bytearray を使って T/A を直接書き換えると安定して高速です。

• 出力は当選確定した瞬間に即座に終了する（以降の演説は行われない）ことを忘れないようにします。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    M = int(data[1])
    S = bytearray(data[2])

    T = ord('T')
    A = ord('A')

    t_cnt = S.count(T)
    a_cnt = N - t_cnt

    for i in range(M):
        r = int(data[3 + i]) - 1
        if S[r] == T:
            S[r] = A
            t_cnt -= 1
            a_cnt += 1
        else:
            S[r] = T
            a_cnt -= 1
            t_cnt += 1

        if t_cnt == 0 or a_cnt == 0:
            sys.stdout.write(str(i + 1))
            return

    sys.stdout.write("-1")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。