概要

青木君の行動計画 \(S\) が固定されているので、各ターンまでに高橋君が何回アタックできれば勝てるかを調べます。
各ターン \(i\) について「必要なアタック回数」と「可能な最大アタック回数」を比較し、最初に勝てるターンを求めます。

考察

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

このとき、青木君がチャージした回数を \(c\) とします。
つまり、最初の \(i\) 文字のうち C の個数が \(c\) です。

青木君のエネルギー

青木君は

• チャージを \(c\) 回するので \(+c\)
• アタックを \(i-c\) 回するので \(-(i-c)\)

だけ自分のエネルギーが変化します。

よって、高橋君から一度も攻撃されなかった場合、青木君のエネルギーは

\(A + c - (i-c) = A + 2c - i\)

になります。

ここで、高橋君が \(i\) ターン目までに \(K\) 回アタックしたとします。
高橋君のアタックは青木君のエネルギーを \(1\) 減らすので、青木君のエネルギーは

\(A + 2c - i - K\)

です。

高橋君が勝つには、青木君のエネルギーが \(0\) 以下になる必要があるので、

\(A + 2c - i - K \leq 0\)

すなわち

\(K \geq A + 2c - i\)

が必要です。

したがって、\(i\) ターン目までに必要な高橋君のアタック回数は

\(A + 2c - i\)

です。

これをコードでは aoki_base としています。

---

高橋君のエネルギー

次に、高橋君が \(i\) ターン目までに \(K\) 回アタックしたとします。

高橋君は

• 自分のチャージを \(i-K\) 回するので \(+(i-K)\)
• 自分のアタックを \(K\) 回するので \(-K\)
• 青木君のアタックを \(i-c\) 回受けるので \(-(i-c)\)

だけエネルギーが変化します。

よって、高橋君のエネルギーは

\(H + (i-K) - K - (i-c)\)

です。整理すると、

\(H + c - 2K\)

になります。

高橋君が勝つためには、勝利判定時に高橋君のエネルギーが \(1\) 以上である必要があります。

したがって、

\(H + c - 2K \geq 1\)

が必要です。

これを変形すると、

\(2K \leq H + c - 1\)

なので、

\(K \leq \left\lfloor \frac{H+c-1}{2} \right\rfloor\)

です。

また、当然ながら \(i\) ターン目までにできるアタック回数は最大でも \(i\) 回です。

よって、高橋君が \(i\) ターン目までに可能な最大アタック回数は

\(\min\left(i,\left\lfloor \frac{H+c-1}{2} \right\rfloor\right)\)

です。

これをコードでは max_attack としています。

---

勝てる条件

\(i\) ターン目に勝てるためには、

• 必要なアタック回数 \(\leq\) 可能な最大アタック回数

であればよいです。

つまり、

\(A + 2c - i \leq \min\left(i,\left\lfloor \frac{H+c-1}{2} \right\rfloor\right)\)

なら、高橋君は \(i\) ターン目までに勝つことができます。

ターンを \(1\) から順番に調べ、最初にこの条件を満たしたターンが答えです。

---

素朴な方法が難しい理由

高橋君は各ターンで「チャージ」か「アタック」を選べるので、全探索すると最大で \(2^T\) 通りになります。
\(T\) は最大 \(2 \times 10^6\) なので、これは到底間に合いません。

また、エネルギーを状態に持つ DP を考えても、\(H,A\) が最大 \(5 \times 10^6\) と大きく、状態数が非常に大きくなります。

そこで、各ターンまでに必要なアタック回数と可能なアタック回数だけを見ることで、\(O(T)\) で解けます。

アルゴリズム

1. c = 0 とする。これは、これまでの青木君のチャージ回数を表す。
2. ターン \(i=1,2,\dots,T\) を順に見る。
3. \(S_i\) が C なら c を \(1\) 増やす。
4. 次を計算する。
   • aoki_base = A + 2 * c - i
     • 青木君を倒すために必要な高橋君のアタック回数
   • max_attack = min(i, (H + c - 1) / 2)
     • 高橋君がエネルギーを \(1\) 以上残しつつ可能な最大アタック回数
5. aoki_base <= max_attack なら、そのターンで勝てるので \(i\) を出力して終了。
6. 最後まで勝てなければ -1 を出力する。

計算量

• 時間計算量: \(O(T)\)
• 空間計算量: \(O(T)\)

実装のポイント

• \(H,A\) や計算途中の値は大きくなる可能性があるため、long long を使います。

• c は「現在までに青木君がチャージした回数」です。

• ターン番号は \(1\) 始まりで扱うと、式 \(A + 2c - i\) がそのまま使えて分かりやすいです。

• aoki_base が \(0\) 以下の場合は、高橋君がアタックしなくても青木君のエネルギーが \(0\) 以下になることを意味します。その場合も条件 aoki_base <= max_attack で自然に判定できます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long H, A;
    int T;
    cin >> H >> A >> T;

    string S;
    cin >> S;

    long long c = 0;

    for (int i = 1; i <= T; i++) {
        if (S[i - 1] == 'C') c++;

        long long aoki_base = A + 2 * c - i;
        long long max_attack = min<long long>(i, (H + c - 1) / 2);

        if (aoki_base <= max_attack) {
            cout << i << '\n';
            return 0;
        }
    }

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

---

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