🚀

【競技プログラミング】AtCoder Beginner Contest 180_D問題

に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc180/tasks/abc180_d

要約

  1. いろはちゃんは高橋君というペットを飼っている。

  2. 高橋君の初期状態

    • 強さ: X
    • 経験値: 0

  3. 特訓の種類
    a) カコモンジム

    • 強さが A 倍になる
    • 経験値が 1 増える
      b) AtCoderジム
    • 強さが B 増える
    • 経験値が 1 増える

  4. 高橋君は強さが Y 以上になると進化しますが、いろはちゃんは進化させたくない。

  5. 目標：強さを Y 未満に保ちながら、経験値を最大化する。

  • X: 高橋君の初期の強さ
  • Y: 進化する強さの閾値
  • A: カコモンジムでの強さの倍率
  • B: AtCoderジムでの強さの増加量

既存投稿一覧ページへのリンク

一覧ページ

独り言

  • 経験値を最大化するには、できるだけ多くの特訓を行う必要がある。
  • カコモンジムは強さを倍増させるので、初期段階では効率が良い。
  • 強さが大きくなるにつれて、カコモンジムだと変身のリスクがある。
  • カコモンジムの効率がAtCoderジムを下回った時点で、AtCoderジムに切り替える。
  • 最後に、AtCoderジムでの特訓回数を計算して加算する。

アプローチ

  1. まず、カコモンジムでの特訓を可能な限り行う。
  2. カコモンジムでの特訓が不可能になったら、AtCoderジムでの特訓に切り替える。
  3. 最終的に得られる経験値の合計を計算する。

解法手順

  1. 高橋君の現在の強さを初期値Xとして設定する。
  2. 経験値の合計を0で初期化する。
  3. 以下の条件を満たす限り、カコモンジムでの特訓を繰り返す
    • カコモンジムでの強さの増加量が AtCoderジムでの増加量B未満である。
    • 特訓後の強さがY未満である。
  4. カコモンジムでの特訓を行うたびに、経験値を1増やし、強さをA倍する。
  5. カコモンジムでの特訓が不可能になったら、AtCoderジムでの特訓に切り替える。
  6. AtCoderジムでの特訓回数を計算する：(Y-1 - 現在の強さ) ÷ B
  7. AtCoderジムでの特訓回数を経験値に加算する。
  8. 最終的な経験値の合計を出力する。

ACコード

ac.py
def io_func():
    # 入力を受け取り、整数のリストとして返す
    return list(map(int, input().split()))

def solve(X, Y, A, B):
    current_strength = X  # 高橋君の現在の強さ
    total_experience = 0  # 経験値の合計

    while True:
        # カコモンジムでの強さの増加量を計算
        kakomom_increase = (A - 1) * current_strength

        # カコモンジムでの特訓が不可能な条件をチェック
        if kakomom_increase >= B:
            break
        if current_strength * A >= Y:
            break

        # カコモンジムでの特訓を実行
        current_strength *= A
        total_experience += 1

    # AtCoderジムでの特訓回数を計算し、経験値に加算
    total_experience += ((Y - 1) - current_strength) // B

    return total_experience

if __name__=="__main__":
    # メイン処理
    X, Y, A, B = io_func()
    result = solve(X, Y, A, B)
    print(result)

###
# X: 高橋君の初期の強さ
# Y: 目標とする強さの上限
# A: カコモンジムでの強さの倍率
# B: AtCoderジムでの強さの増加量
# current_strength: 高橋君の現在の強さ
# total_experience: 獲得した経験値の合計
# kakomom_increase: カコモンジムでの強さの増加量

# 1. io_func関数: 標準入力から4つの整数を受け取り、リストとして返す
# 2. solve関数: 主な処理を行う
#    a. 初期設定: 現在の強さと経験値を初期化
#    b. カコモンジムでの特訓: 条件を満たす限り繰り返し実行
#    c. AtCoderジムでの特訓: 残りの強さの増加分を計算し、経験値に加算
# 3. メイン処理: 入力を受け取り、solve関数を呼び出し、結果を出力

Discussion