みんなのプロコン 2019 C - When I hit my pocket... (茶色, 400 点)

こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。

問題へのリンク

問題概要

すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。

• 持っているビスケットを叩き、1 枚増やす
• ビスケット A 枚を 1 円に交換する
• 1 円をビスケット B 枚に交換する

K 回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を求めてください。

制約

• 

考えたこと

超絶苦手系の問題。概ねビスケットの枚数が十分大きければ

• 2 回の操作によって、ビスケットを B-A 枚増やすことができる

という感じになっている。まず根本的に、操作の順序として

• ビスケットを 1 枚ずつ増やすのをやり続けてから、
• B-A 枚増やす 2 手一組を繰り返す

という順序で操作する場合のみを考えればよいことがわかる。どんな順番でやっても結局できるビスケットの枚数は変わらないので、それだったら最初にビスケットを増やすことで 2 番目の操作をできる可能性を増やした方がよいし、2 番目の操作をやった直後には 3 番目の操作をやった方がよい。

ここから丁寧に場合分けしよう。

B - A <= 2 のとき

「ビスケット A 枚を 1 円に交換する」をするメリットはまったくない。そんなことするくらいなら、毎ターン「ビスケットを 1 枚増やす」をした方がよい。

よって、K + 1 枚。

B - A > 2 のとき

まず最初にビスケットが A 枚になるまでは 1 番目の選択肢しかとれない。そして具体的には

• まずビスケットが A 枚になるまで 1 枚増やし続ける (K < A-1 だったら K+1 が答え)
• 残り回数が奇数だったら、あと 1 枚増やしておく
• 最後に残った回数で目一杯、2 手一組で B-A を増やし続ける

という風にすれば OK。

#include <iostream>
using namespace std;

int main() {
    long long K, A, B; cin >> K >> A >> B;
    if (B-A <= 2 || K < A-1) cout << K+1 << endl;
    else {
        long long res = A;
        K -= A-1;
        if (K % 2 == 1) ++res, --K;
        res += (B-A) * (K/2);
        cout << res << endl;
    }
}