概要

この問題は、事前に決まっている青木君の行動に対して、高橋君が各ターンで「チャージ」または「アタック」を最適に選択し、最も早いターンで勝利する方法（または勝利不可能であること）を求める問題です。

各ターンにおける両者のエネルギーの推移を、高橋君がそれまでに行った「アタック」の合計回数に着目して定式化し、動的計画法（DP）のように状態を遷移させることで、時間計算量 \(O(T)\) で解くことができます。

---

考察

1. 状態の定式化（アタック回数 \(m\) への着目）

高橋君が各ターンで取れる行動は「チャージ」か「アタック」のいずれかです。青木君の行動は固定されているため、高橋君の行動の自由度は「各ターンでどちらを選ぶか」にあります。

第 \(k\) ターン終了時点までに、高橋君が「アタック」を選択した合計回数を \(m\) とします。 このとき、第 \(k\) ターン終了時の両者のエネルギーを \(m\) を用いて表してみましょう。

青木君の行動計画から、第 \(k\) ターンまでに青木君がアタックした回数を \(Y_k\) （文字列 \(S\) の最初の \(k\) 文字に含まれる A の個数）とします。

• 青木君の第 \(k\) ターン終了時のエネルギー \(P_k(m)\) 青木君は \(k - Y_k\) 回チャージし、\(Y_k\) 回アタックします。さらに高橋君から \(m\) 回アタックされます。 $\(P_k(m) = A + (k - Y_k) - Y_k - m = A + k - 2Y_k - m\)\( ここで、高橋君が一度もアタックしなかった場合の青木君のエネルギーを \)P_{\text{base}} = A + k - 2Y_k\( とおくと、実際のエネルギーは以下のように表せます。 \)\(P_k(m) = P_{\text{base}} - m\)$

• 高橋君の第 \(k\) ターン終了時のエネルギー \(Q_k(m)\) 高橋君は \(k - m\) 回チャージし、\(m\) 回アタックします。さらに青木君から \(Y_k\) 回アタックされます。 $\(Q_k(m) = H + (k - m) - m - Y_k = H + k - Y_k - 2m\)\( ここで、高橋君が一度もアタックしなかった場合の高橋君のエネルギーを \)Q_{\text{base}} = H + k - Y_k\( とおくと、実際のエネルギーは以下のように表せます。 \)\(Q_k(m) = Q_{\text{base}} - 2m\)$

このように、第 \(k\) ターン終了時の両者のエネルギーは、高橋君の累積アタック回数 \(m\) のみによって一意に決定されます。

---

2. 生存条件と勝利条件の不等式化

各ターン終了時に満たすべき条件を、アタック回数 \(m\) の不等式として整理します。

① 第 \(k\) ターンで「勝利」する条件

高橋君が勝利するためには、以下の2つを同時に満たす必要があります。 - 青木君のエネルギーが \(0\) 以下： $\(P_k(m) \le 0 \iff P_{\text{base}} - m \le 0 \iff m \ge P_{\text{base}}\)\( - 高橋君のエネルギーが \)1\( 以上： \)\(Q_k(m) \ge 1 \iff Q_{\text{base}} - 2m \ge 1 \iff m \le \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\)$

したがって、勝利に必要なアタック回数 \(m\) の条件は、 \(P_{\text{base}} \le m \le \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\)（かつ \(m \ge 0\)）となります。

② 第 \(k\) ターンで「生存して次のターンに進む」条件

勝利せずに次のターンへ進むためには、両者のエネルギーがともに \(1\) 以上でなければなりません。 - 青木君のエネルギーが \(1\) 以上： $\(P_k(m) \ge 1 \iff m \le P_{\text{base}} - 1\)\( - 高橋君のエネルギーが \)1\( 以上： \)\(Q_k(m) \ge 1 \iff m \le \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\)$

したがって、次のターンへ進むために許容される \(m\) の上限を \(U_{\text{next}}\) とすると、 $\(U_{\text{next}} = \min\left(P_{\text{base}} - 1, \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\right)\)\( となり、 \)0 \le m \le U_{\text{next}}$ を満たす必要があります。

---

3. 最大アタック回数 \(M\) の動的更新

高橋君が第 \(k\) ターン終了時に生存（または勝利）するために、達成可能なアタック回数 \(m\) の最大値 \(M\) を管理します。

第 \(k-1\) ターン終了時に生存可能であったアタック回数の最大値を \(M_{k-1}\) とします。第 \(k\) ターンにおいて、高橋君はアタックを「行う」か「行わない」かを選択できます。 - 前ターンで生存している（＝エネルギーが \(1\) 以上である）ため、第 \(k\) ターン開始時にアタックを選択することが可能です。 - したがって、第 \(k\) ターン終了時に達成可能なアタック回数の最大値（の候補）は \(M_{k-1} + 1\) となります。

これを用いて、毎ターン以下の処理を行います。

• 勝利判定: 高橋君が生存できる範囲での最大アタック回数は \(M_{\text{win}} = \min\left(M_{k-1} + 1, \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\right)\) です。 これが青木君を倒すのに必要なアタック回数 \(P_{\text{base}}\) 以上（かつ \(M_{\text{win}} \ge 0\)）であれば、第 \(k\) ターンで勝利可能です。
• 生存更新: 次のターンへ進む場合、最大アタック回数を生存条件で制限し、 \(M_k = \min(M_{k-1} + 1, U_{\text{next}})\) に更新します。 もし \(U_{\text{next}} < 0\) または \(M_k < 0\) となった場合、これ以上生存してゲームを続けることはできません。

---

アルゴリズム

1. 変数の初期化：
   • P (\(P_{\text{base}}\)): 青木君の初期エネルギー \(A\)
   • Q (\(Q_{\text{base}}\)): 高橋君の初期エネルギー \(H\)
   • M: 達成可能な最大アタック回数 \(0\)
2. \(k = 1, 2, \dots, T\) について、以下のループ処理を行います。
   • 青木君の行動 \(y\)（A なら \(1\)、C なら \(0\)）に基づき、P と Q を更新する。
     • P = P + 1 - 2 * y
     • Q = Q + 1 - y
   • 高橋君が生存できる上限 \(U_{\text{win}} = \lfloor (Q - 1) / 2 \rfloor\) を計算する。
   • 勝利のための最大アタック回数 \(M_{\text{win}} = \min(M + 1, U_{\text{win}})\) を求める。
   • 勝利判定: \(M_{\text{win}} \ge P\) かつ \(M_{\text{win}} \ge 0\) ならば、ターン数 \(k\) を出力して終了する。
   • 生存更新: 次のターンへ進むための上限 \(U_{\text{next}} = \min(P - 1, U_{\text{win}})\) を計算し、最大アタック回数を M = min(M + 1, U_next) に更新する。
   • もし U_next < 0 または M < 0 ならば、これ以上進めないためループを抜ける。
3. ループを抜けても勝利できなかった場合は -1 を出力する。

---

計算量

• 時間計算量: \(O(T)\) ターン数 \(T\) に対する 1 重ループであり、ループ内の各処理は定数時間 \(O(1)\) で実行されるため、非常に高速に動作します。
• 空間計算量: \(O(T)\) または \(O(1)\) 入力の文字列 \(S\) を保持するための \(O(T)\) の空間のみを使用します。

---

実装のポイント

負の数の切り捨て除算（床関数）

C++ における整数の除算 / は、負の数に対して 0 に向かって丸められます（例: -1 / 2 は 0 になります）。 しかし、数式中の \(\lfloor (Q - 1) / 2 \rfloor\) は床関数（負の無限大方向への丸め）である必要があります（例: \(\lfloor -1 / 2 \rfloor = -1\)）。

これを正しく処理するために、以下のような関数を用意して、負の数の場合にも正しく下方向に丸められるようにしています。

long long floor_div2(long long x) {
    return x >= 0 ? x / 2 : (x - 1) / 2;
}

ソースコード

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 負の数にも対応した床関数 (x / 2 の床関数)
long long floor_div2(long long x) {
    return x >= 0 ? x / 2 : (x - 1) / 2;
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long H, A, T;
    if (!(cin >> H >> A >> T)) return 0;

    string S;
    cin >> S;

    long long P = A;
    long long Q = H;
    long long M = 0;

    for (int k = 1; k <= T; ++k) {
        int y = (S[k - 1] == 'A' ? 1 : 0);
        P = P + 1 - 2 * y;
        Q = Q + 1 - y;

        long long U_win = floor_div2(Q - 1);
        long long M_win = min(M + 1, U_win);

        // 第 k ターンで勝利可能か判定
        if (M_win >= P && M_win >= 0) {
            cout << k << "\n";
            return 0;
        }

        // 次のターンへ進むための更新
        long long U_next = min(P - 1, U_win);
        M = min(M + 1, U_next);

        // 次のターンへ進むことが不可能な場合
        if (U_next < 0 || M < 0) {
            break;
        }
    }

    cout << -1 << "\n";
    return 0;
}

---

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