概要

青木君の行動列は固定なので、各ターンまでに高橋君が何回アタックできれば青木君のエネルギーを \(0\) 以下にできるかを判定します。
各ターンを前から見て、初めて勝利可能になるターンを出力します。

考察

まず、ターン \(i\) までを考えます。

• \(c_i\)：青木君が最初の \(i\) ターンでチャージした回数
• \(q_i\)：高橋君が一度もアタックしなかった場合の、ターン \(i\) 終了後の青木君のエネルギー

とします。

青木君のエネルギーは、青木君自身の行動だけを見ると、

• チャージなら \(+1\)
• アタックなら \(-1\)

なので、コード中では q としてこの値を更新しています。

高橋君がターン \(i\) までに \(x\) 回アタックしたとすると、青木君のエネルギーはさらに \(x\) 減るので、

\[ q_i - x \]

になります。

したがって、青木君のエネルギーを \(0\) 以下にするには、

\[ x \geq q_i \]

回のアタックが必要です。

特に、もし \(q_i \leq 0\) なら、高橋君が一度もアタックしなくても青木君のエネルギーは \(0\) 以下になります。
この場合、高橋君はずっとチャージしていればエネルギーは必ず \(1\) 以上なので、そのターンで勝利できます。

---

次に、\(q_i > 0\) の場合を考えます。

このとき、高橋君は少なくとも \(q_i\) 回アタックする必要があります。
余分にアタックしても高橋君のエネルギーが減るだけなので、ちょうど \(q_i\) 回アタックできるかを考えれば十分です。

高橋君がすべてのターンでチャージした場合を基準にします。

• 青木君がチャージするターン：高橋君は \(+1\)
• 青木君がアタックするターン：高橋君は \(+1\) して同時に \(-1\) されるので、差し引き \(0\)

よって、ターン \(i\) 終了後の高橋君のエネルギーは

\[ H + c_i \]

です。

ここで、高橋君があるターンで「チャージ」ではなく「アタック」を選ぶと、

• チャージなら \(+1\)
• アタックなら \(-1\)

なので、基準と比べて \(2\) 減ります。

したがって、高橋君が \(x\) 回アタックした後のエネルギーは

\[ H + c_i - 2x \]

です。

勝利するには高橋君のエネルギーが \(1\) 以上必要なので、\(x = q_i\) として

\[ H + c_i - 2q_i \geq 1 \]

つまり

\[ 2q_i \leq H - 1 + c_i \]

が必要です。

また、\(i\) ターンの間にアタックできる回数は最大でも \(i\) 回なので、

\[ q_i \leq i \]

も必要です。

よって、ターン \(i\) で勝利可能な条件は次のどちらかです。

\[ q_i \leq 0 \]

または

\[ q_i \leq i \quad \text{かつ} \quad 2q_i \leq H - 1 + c_i \]

です。

素朴に高橋君の全行動を探索すると \(2^T\) 通りになり不可能です。
また、エネルギーを状態に持つ DP も、\(H,A,T\) が非常に大きいため現実的ではありません。
この問題では「必要なアタック回数」と「高橋君が可能なアタック回数」を数式で比較することで、各ターンを \(O(1)\) で判定できます。

アルゴリズム

1. c = 0 とする。これはここまでの青木君のチャージ回数。
2. q = A とする。これは高橋君がアタックしなかった場合の青木君のエネルギー。
3. 各ターン \(i = 1,2,\dots,T\) について、青木君の行動を反映する。
   • C なら、c += 1, q += 1
   • A なら、q -= 1
4. 次の条件を満たすなら、ターン \(i\) で高橋君は勝利可能。
   • q <= 0
   • または q <= i かつ 2*q <= H - 1 + c
5. 初めて条件を満たしたターン番号を出力する。
6. 最後まで条件を満たさなければ -1 を出力する。

コード中の判定

if q <= 0 or (q <= i and (q << 1) <= hm1 + c):

は、上の条件をそのまま実装したものです。
q << 1 は 2 * q と同じ意味です。

計算量

• 時間計算量: \(O(T)\)
• 空間計算量: \(O(T)\)
  ただし、入力文字列 \(S\) を除いた追加の使用メモリは \(O(1)\) です。

実装のポイント

• S を bytes として読み込んでいるため、文字 'C' との比較ではなく ASCII コード 67 と比較しています。

  • 67 は 'C' の ASCII コードです。

• T は入力として与えられますが、実装では S の長さをそのまま使えるため明示的には使っていません。

• hm1 = H - 1 としておくことで、判定式 2*q <= H - 1 + c を少し簡潔に書いています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    H = int(data[0])
    A = int(data[1])
    S = data[3]

    c = 0
    q = A
    hm1 = H - 1

    for i, ch in enumerate(S, 1):
        if ch == 67:  # 'C'
            c += 1
            q += 1
        else:         # 'A'
            q -= 1

        if q <= 0 or (q <= i and (q << 1) <= hm1 + c):
            print(i)
            return

    print(-1)

if __name__ == "__main__":
    main()

---

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