ARC 145

Thu, Jun 19, 2025

A. AB Palindrome

https://atcoder.jp/contests/arc145/tasks/arc145_a

B. AB Game

https://atcoder.jp/contests/arc145/tasks/arc145_b

自力 AC. 茶色 Diff らしいがだいぶ難しく感じた。

$N < A$ のとき、Alice は確定で負け。

$N \geq A$ のときを考える。

(i) $A \leq B$ のとき

ゲーム $x \in [1, A-1]$ では Alice は石を取り除けないので負け。ゲーム $x \in [A, N]$ では Alice が石を取り除けるだけ除くと $x \mod A < B$ となるので Alice が勝てる。よって Alice が勝てるゲームの個数は $N-(A-1)$

(ii) $A > B$ のとき

Bob が勝つ回数について考える。まずゲーム $x \in [1, A-1]$ については Bob が勝つ。

ゲーム $x \in [A, N]$ について考える。 Alice が石を取り除いた後の個数が $B$ 以上のとき、$A > B$ より Bob は次のターンで Alice が負けるように石を取り除くことができる。よって Alice の戦略としてはなるたけ石を残さないことが最適な戦略となる。ゲーム $x$ において Alice が最適な戦略をとったとき、$x \mod A \geq B$ であれば Bob が勝つ。これらよりゲーム $1 \sim N$ において Bob が勝つ回数は

\begin{align*} \text{Bob が勝つ回数} = (A-1 - B + 1) \times \left( \floor{\frac{N}{A}} - 1 \right) + (A - 1) + \max \left\{ ( N \mod A ) - B + 1, 0 \right\} \end{align*}

である。よって Alice が勝つ回数は

\begin{align*} N - (\text{Bob が勝つ回数}) \end{align*}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, A, B;
    cin >> N >> A >> B;
    if (N < A) {
        cout << 0 << endl;
        return;
    }
    if (N >= A && A <= B) {
        cout << N - (A - 1) << endl;
        return;
    }

    ll ans = N, q = N / A, r = N % A;
    ans -= (A - B) * (q - 1) + A - 1 + max(r - B + 1, 0ll);
    cout << ans << endl;
}