概要

生徒の支持状態が変化する中で、どちらかの候補者の支持者が0人になった時点で選挙が決着する問題です。各演説後に支持者数をチェックし、決着がついた演説番号を出力します。

考察

問題の核心は、各演説後の支持者数を効率的に管理することです。素朴なアプローチとして、毎回全ての生徒の支持状態を調べて支持者数を計算すると、各演説で \(O(N)\) 時間かかり、全体で \(O(N \times M)\) 時間となって制約条件（\(N, M \leq 2 \times 10^5\)）では最大 \(4 \times 10^{10}\) 回の操作が必要になり、時間制限に間に合いません。

そこで、支持者数を変数で管理する方法が考えられます。初期状態で支持者数を数え、各演説で生徒の支持状態が変わるたびに、対応する支持者数を更新します。これにより、各演説の処理は \(O(1)\) 時間で済み、全体で \(O(N + M)\) 時間で効率的に処理できます。

アルゴリズム

1. 初期状態の文字列 \(S\) から、高橋君の支持者数 count_t と青木君の支持者数 count_a を数えます。
2. 各演説について:
   • 対象の生徒の現在の支持状態を確認します。
   • 支持状態に応じて、count_t と count_a を更新します（TからAに変われば count_t を1減らし count_a を1増やし、逆も同様）。
   • 支持状態を反転させます（次の演説のための準備）。
   • 更新後の count_t または count_a が0になったら、その時点の演説番号を出力して終了します。
3. 全ての演説が終わっても決着がつかない場合は、-1を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 初期状態の支持者数を数えるのに \(O(N)\)
  • 各演説を処理するのに \(O(M)\)
• 空間計算量: \(O(N)\)
  • 文字列 \(S\) をリストとして保持するため

実装のポイント

• 生徒番号は1-indexedで与えられるので、0-indexedに変換する（idx = r - 1）

• 支持状態の変更と支持者数の更新を同時に行う

• 各演説後に即座に支持者数をチェックし、0になっていたら直ちに結果を出力してプログラムを終了する

• 入力データが空の場合の処理を最初にチェックする（問題の制約では発生しないかもしれませんが、念のため）

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
        
    n, m = map(int, data[0].split())
    s = list(data[1].strip())
    r_list = list(map(int, data[2:2+m]))
    
    count_t = s.count('T')
    count_a = n - count_t
    
    for i, r in enumerate(r_list):
        idx = r - 1
        if s[idx] == 'T':
            count_t -= 1
            count_a += 1
            s[idx] = 'A'
        else:
            count_t += 1
            count_a -= 1
            s[idx] = 'T'
            
        if count_t == 0:
            print(i+1)
            return
        if count_a == 0:
            print(i+1)
            return
            
    print(-1)

if __name__ == "__main__":
    main()

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