Pythonで解くAtCoder(M-SOLUTIONS プロコンオープン 2020:B)
こんにちは、クルトンです！
この記事では
AtCoderの「M-SOLUTIONS プロコンオープン 2020」のB問題をPythonを使って解説します。
問題のリンクを載せておきます。
atcoder.jp
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_b
今回必要な知識
- 1行に複数の数字の入力があるときの受け取り方
- for文
- while文
入力の受け取り方や、for文、while文の使い方は下の記事で解説しています。
入力の受け取り方
1行に一つの数字の入力があるときの受け取り方
int(input())
1行に複数の数字の入力があるときの受け取り方
map(int,input().split())
今回の場合は
A, B, C = map(int,input().split()) K = int(input())
とすることで入力を受け取れます。
ではここからは解法について説明します。
簡単な解法
A, B, Cに2を掛ける回数をそれぞれp, q, rとすると
- A×2^p < B×2^q < C×2^r
- p + q + r ≤ K
をみたすp, q, rが存在すれば魔術を成功させることができます。
また、p,q,rはK以下であり、制約からKは7以下なので、p,q,rは7以下となります。
なのでfor文を使ってp,q,rのそれぞれが0から7のときを、すべて調べることによって答えを求めることができます。
このような、考えられるパターンをすべて調べるやり方を、全探索といいます。
以下にサンプルコードを載せておきます
少し難しい解法
最短で魔術を成功させることができるような操作について考えます。
まず、Aに2を掛けてもBとC2を掛ける回数が増えるだけなので、意味がないことが分かります。
そのため、まずBがAを超えるまで、Bに2を掛けます。
そしてその後、CがBを超えるまで、Cに2を掛ければよいことが分かります。
そして、2を掛けた回数の合計がKを超えていなければ、魔術を成功させることができます。
このような、あるルールに則って、そのときに応じた最善の手を選ぶアルゴリズムを貪欲法といいます。
このとき、BやCに何回2を掛ければよいかは分からないため、while文を使って実装します。
以下にサンプルコードを載せておきます
まとめ
今回は
- for文を使って全探索をする
- while文を使って貪欲に解く
という問題でした。
この問題を見て、全探索と貪欲法がどちらも思いつくようになると素晴らしいと思います！
ではまたお会いしましょう！さようなら～
