概要

\(N\) 人の生徒がそれぞれ高橋君か青木君を支持しており、\(M\) 回の演説で指定された生徒の支持が反転します。いずれかの候補者の支持者が \(0\) 人になった時点を求める問題です。

考察

この問題で重要なのは、各演説のたびに 支持者数の増減を追跡 すればよいという点です。

各生徒が具体的に誰を支持しているかの「詳細な状態」も管理する必要がありますが、当選確定の判定自体は 高橋君の支持者数（\(T\) の数）と青木君の支持者数（\(A\) の数）のどちらかが \(0\) になったか だけで判断できます。

• 演説で生徒 \(R_i\) の支持が反転するので、その生徒が現在 T なら A に変わり、\(T\) の人数が \(1\) 減って \(A\) の人数が \(1\) 増えます。逆も同様です。
• 各演説後に \(T\) の人数または \(A\) の人数が \(0\) かどうかをチェックするだけで済みます。

素朴に毎回文字列全体を走査して T と A の数を数え直すと \(O(NM)\) になりますが、カウンタを差分更新する方法なら各演説を \(O(1)\) で処理できます。

アルゴリズム

1. 初期化: 文字列 \(S\) から各生徒の支持状態を配列に格納し、T の個数 t_count と A の個数 a_count を数える。
2. 演説の処理 (\(i = 1, 2, \ldots, M\)):
   • 生徒 \(R_i\) の現在の支持を確認する。
   • T → A に変える場合: t_count を \(1\) 減らし、a_count を \(1\) 増やす。
   • A → T に変える場合: a_count を \(1\) 減らし、t_count を \(1\) 増やす。
   • 配列上の支持状態も反転させる（次回以降の判定のため）。
   • t_count == 0 または a_count == 0 なら、\(i\) を出力して終了。
3. \(M\) 回すべて終了しても条件を満たさなければ \(-1\) を出力。

具体例

\(N=3\), \(S =\) TAT（\(T\)が2人、\(A\)が1人）で、演説が生徒 \(1\), 生徒 \(3\) の順に行われる場合：

2回目の演説後に t_count == 0 となるので、答えは 2 です。

計算量

• 時間計算量: \(O(N + M)\)
  • 初期化で \(S\) を走査するのに \(O(N)\)、各演説の処理は \(O(1)\) なので全体で \(O(M)\)。
• 空間計算量: \(O(N)\)
  • 各生徒の現在の支持状態を保持する配列に \(O(N)\)。

実装のポイント

• 差分更新: 毎回全体を数え直すのではなく、変化分だけカウンタを更新することで \(O(1)\) で処理する。

• 入力の高速化: Python では sys.stdin.buffer.read() でまとめて読み込むことで、大量の入力を効率的に処理できる。

• 1-indexed → 0-indexed: 問題の生徒番号は \(1\) 始まりだが、配列は \(0\) 始まりなので R_i - 1 でアクセスする。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = input_data[idx].decode(); idx += 1
    
    support = list(S)
    t_count = S.count('T')
    a_count = N - t_count
    
    for i in range(M):
        r = int(input_data[idx]) - 1; idx += 1
        if support[r] == 'T':
            support[r] = 'A'
            t_count -= 1
            a_count += 1
        else:
            support[r] = 'T'
            t_count += 1
            a_count -= 1
        
        if t_count == 0 or a_count == 0:
            print(i + 1)
            return
    
    print(-1)

main()

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