みんなのプロコン2019 C When I hit my pocket...

今回はABC3完でもパフォーマンスにかなり幅が出ましたね

問題

atcoder.jp

問題概要

最初にビスケット $1$ 枚を持っている。
次の操作を $K$ 回行ったときに持っているビスケットの最大値を求めよ。

ビスケットを $1$ 枚増やす。
ビスケット $A$ 枚を $1$ 円に交換する。
$1$ 円をビスケット $B$ 枚に交換する。

考察

最初に答えが $K + 1$ 枚となる、ビスケットと円を交換すると損をする $B - A \leqq 1$ 、 $K$ 回ビスケットを増やしても円と交換できない $K \leqq A$ という条件を弾きます。

したがって、本問題で計算が必要なのは $A \lt K$ と $A \lt B$ という条件のときです。
この条件のもとではビスケットと円の交換において、ビスケットを2枚以上増やすことができます。

次に、ビスケット ➡️ 円 ➡️ ビスケットの交換で $B - A$ 枚ビスケットを増やすことができるのを踏まえて、手持ちのビスケットを $A$ 枚まで増やした後に何回交換ができるかを考えます。

まず、 $A$ 枚までビスケットを増やすと操作ができる残り回数は $K - A + 1$ です。
これを $remain$ と呼ぶことにします。

ビスケット ➡️ 円 ➡️ ビスケットの交換には $2$ 回操作が必要です。
そのため、 $remain \ / \ 2$ 回だけ操作を行うことができます。

しかし $remain$ が奇数のとき、最後に行う操作はビスケットを円に交換する操作になってしまうため、最後だけビスケットを1枚増やすということに注意する必要があります。

以上を踏まえると、
(i) $remain$ が偶数のとき $ans = (B - A) * (remain \ / \ 2) + A$
(ii) $remain$ が奇数のとき $ans = (B - A) * \ floor\ (remain \ / \ 2) + A + 1$
になります。

提出コード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
  ll k,a,b;
  cin >> k >> a >> b;

  if (b - a <= 1) {
    cout << k + 1 << endl;
    return 0;
  }

  if (k <= a) {
    cout << k + 1 << endl;
    return 0;
  }

  // k > a & a > bの条件下で考える
  ll remain = k - a + 1; // 残り操作回数
  ll kaisuu = remain / 2; // 小数点以下は切り捨てに注意
  ll sub = b - a;
  ll ans = 0;
  if (remain % 2 == 0) {
    ans = sub * kaisuu + a;
  } else {
    ans = sub * kaisuu + a + 1;
  }

  cout << ans << endl;
}