概要

本問題は、お互いの行動がエネルギーに影響を与えるカードバトルのシミュレーションにおいて、高橋君が事前に分かっている青木君の行動計画に対して最適な行動をとったとき、最短何ターンで勝利できるかを求める問題です。

青木君の行動が固定されている点に着目し、高橋君が選択可能な「アタック回数」の最大値を動的計画法（DP）や累積の考え方を用いて効率的に求めることで、各ターンで勝利可能かを \(O(1)\) で判定し、全体 \(O(T)\) 時間で解くことができます。

---

考察

1. 各ターン終了時のエネルギーの定式化

第 \(t\) ターンまでに、青木君がチャージを \(c_t\) 回、アタックを \(a_t\) 回行ったとします。これらは青木君の行動計画 \(S\) の最初の \(t\) 文字から一意に定まります。 一方、高橋君がアタックを \(k\) 回、チャージを \(t - k\) 回行ったとします（\(0 \le k \le t\)）。

このとき、第 \(t\) ターン終了時の両者のエネルギー \(H_t, A_t\) は以下のように表せます。

• 青木君のエネルギー \(A_t\) 初期値 \(A\) から、自身のチャージで \(+c_t\)、自身のアタックで \(-a_t\)、高橋君からのアタックで \(-k\) 変化します。 $\(A_t = A + c_t - a_t - k\)$

• 高橋君のエネルギー \(H_t\) 初期値 \(H\) から、自身のチャージで \(+(t - k)\)、自身のアタックで \(-k\)、青木君からのアタックで \(-a_t\) 変化します。 $\(H_t = H + t - 2k - a_t\)$

2. \(t\) ターン目に高橋君が勝利する条件

高橋君が \(t\) ターン目に勝利するための条件は以下の通りです。

1. 青木君のエネルギーが \(0\) 以下になる $\(A_t \le 0 \iff A + c_t - a_t - k \le 0 \iff k \ge A + c_t - a_t\)$
2. 高橋君のエネルギーが \(1\) 以上である $\(H_t \ge 1 \iff H + t - 2k - a_t \ge 1 \iff 2k \le H + t - a_t - 1 \iff k \le \left\lfloor \frac{H + t - a_t - 1}{2} \right\rfloor\)$
3. 途中の任意のターン \(i\) (\(1 \le i < t\)) で、高橋君のエネルギーが \(1\) 以上に保たれている 各ターン \(i\) における高橋君の累積アタック回数を \(k_i\) とすると、同様に以下が成り立たなければなりません。 $\(k_i \le \left\lfloor \frac{H + i - a_i - 1}{2} \right\rfloor\)$

ここで、高橋君の各ターン \(i\) での許容最大アタック回数を \(M_i = \left\lfloor \frac{H + i - a_i - 1}{2} \right\rfloor\) と定義します。 青木君の行動において \(a_i + c_i = i\) （アタックとチャージの合計はターン数）であるため、 $\(M_i = \left\lfloor \frac{H + i - (i - c_i) - 1}{2} \right\rfloor = \left\lfloor \frac{H - 1 + c_i}{2} \right\rfloor\)\( と変形できます。驚くべきことに、**\)M_i\( は高橋君自身の行動に依存せず、青木君の累積チャージ回数 \)c_i$ のみによって決定されます。**

3. 実現可能なアタック回数の最大値 \(K_{\max}\) の導出

高橋君が \(t\) ターン目までに累積でアタックできる回数 \(k_t\) の最大値 \(K_{\max}\) を考えます。 各ターンで高橋君はアタックを最大 \(1\) 回しか行えないため、任意の \(i\) (\(0 \le i \le t\)) に対して、 $\(k_t \le k_i + (t - i)\)\( が成り立ちます（\)i\( ターン目から \)t\( ターン目まで毎ターンアタックし続けた場合が最大）。 さらに、途中でゲームオーバーにならないために \)k_i \le M_i\( （ただし \)k_0 = 0, M_0 = 0\(）である必要があるため、 \)\(k_t \le M_i + t - i\)\( がすべての \)0 \le i \le t\( について成り立たなければなりません。 逆に、この制約をすべて満たす最大の \)kt\( は実際に構成可能であることが知られています。したがって、 \)$K{\max} = \min_{0 \le i \le t} (Mi + t - i) = t + \min{0 \le i \le t} (M_i - i)$$ となります。

\(f_i = M_i - i\) とおくと、 $\(K_{\max} = t + \min_{0 \le i \le t} f_i\)$ と非常にシンプルな形で表せます。

4. 判定方法

各ターン \(t\) において、これまでの \(f_i\) (\(0 \le i \le t\)) の最小値を保持しておけば、\(K_{\max}\) を \(O(1)\) で計算できます。 高橋君が \(t\) ターン目に勝利できる条件は、 $\(K_{\max} \ge A + c_t - a_t\)\( を満たすことです。これを満たす最小の \)t$ が答えとなります。

---

アルゴリズム

1. 必要な変数群を初期化します。
   • 青木君の累積チャージ数 c_count \(= 0\)、アタック数 a_count \(= 0\)
   • \(f_i\) の最小値を表す min_f \(= 0\) （\(f_0 = M_0 - 0 = 0\) より）
   • 答えを格納する ans \(= -1\)
2. \(t = 1\) から \(T\) までループを回します。
   • 青木君の行動 \(S[t-1]\) に応じて、c_count または a_count をインクリメントします。
   • \(M_t = \lfloor (H - 1 + c_t) / 2 \rfloor\) を計算します（ビット演算 (H - 1 + c_count) >> 1 を使用すると高速です）。
   • \(f_t = M_t - t\) を計算し、min_f を \(\min(\text{min\_f}, f_t)\) で更新します。
   • \(K_{\max} = t + \text{min\_f}\) を計算します。
   • もし \(K_{\max} \ge A + c_t - a_t\) であれば、高橋君は第 \(t\) ターンに勝利可能です。ans = t とし、ループを抜けます。
3. ループ終了後、ans を出力します。

---

計算量

• 時間計算量: \(O(T)\) 各ターン \(t\) における処理は、定数時間 \(O(1)\) の算術演算と最小値の更新のみです。これを最大 \(T\) 回行うため、全体の時間計算量は \(O(T)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(T)\) 青木君の行動計画を表す長さ \(T\) の文字列 \(S\) をメモリ上に保持するため、空間計算量は \(O(T)\) となります。

---

実装のポイント

• 切り捨て除算の高速化: \(M_t\) の計算における \(2\) での除算（切り捨て）は、右ビットシフト >> 1 を用いることで高速かつ簡潔に実装できます。

• 初期値の設定: \(f_0 = 0\) であるため、min_f の初期値は必ず 0 に設定する必要があります。初期値を無限大（\(\infty\)）にしてしまうと、途中でエネルギーが \(0\) 以下になる（\(k_i > M_i\) となる）不正なアタックの推移を許容してしまうため注意してください。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    H = int(data[0])
    A = int(data[1])
    T = int(data[2])
    S = data[3]

    c_count = 0
    a_count = 0
    min_f = 0
    ans = -1

    for t in range(1, T + 1):
        char = S[t - 1]
        if char == "C":
            c_count += 1
        else:
            a_count += 1

        M_t = (H - 1 + c_count) >> 1
        f_t = M_t - t
        if f_t < min_f:
            min_f = f_t

        K_max = t + min_f
        if K_max >= A + c_count - a_count:
            ans = t
            break

    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。