Python3で解く AtCoder Beginner Contest 180 D - Takahashi Unevolvedff

条件を検討すると、増えるか増えるかで小さい方を選びたいってことに気付ければなんとかなる。

目次

概要

問題

1. 初期の強さは、経験値は
2. カコモンジムに通う：強さが倍になり、経験値は増える。
3. AtCoderジムに通う：強さが増え、経験値は増える。
4. 経験値はを超えないように特訓した場合、最大の経験値は？

---

解くときに考えた内容

条件的に、増えるか増えるかで小さい方を選びたい。なので、以下の手順になる。

• が よりも小さいかつがよりも小さいなら、カコモンジムに通う。
• 残りの経験値は から初期の経験値とカコモンジムに通って得た経験値を引いた値。
• それを超えないようにAtCoderジムに通う。
• ここは割り算処理するのでぴったりの処理だけ気をつける。
• 今回は残りの経験値から引いたものをで割った整数部分をAtCoderジムに通った数とした。

---

コード

x, y, a, b = map(int, input().split())
a_cnt = 0
while (x*a) < b and (x*a) < y: 
    x *= a
    a_cnt += 1
b_cnt = (y-x-1) // b
ans = a_cnt + b_cnt
print(ans)

---

参考になる書籍

• 問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

章末問題を解いてる。まだ途中。 blacktanktop.hatenablog.com