Pythonで簡単な貪欲法を書く

貪欲法

貪欲法とはある基準を設けてその場その場で最適な解を選択し続けて最適解を求める方法です。短時間である程度最適な解を求める時に効果的だと思っております。貪欲法自体広い意味で使われているので、こういう時に使えるというのが難しいですが、個人的には

• 一つある値Aを固定させて別の値(B,C...)と比較することによって解が得られそう

な時に使えるかなと思っております。

今回の問題

AtCoderのB - Magic 2を貪欲法で解いていきます。

問題文
M君は、以下の 3枚のカードを持っています。

• 整数Aが書かれた赤のカード
• 整数Bが書かれた緑のカード
• 整数Cが書かれた青のカード

彼は天才的な魔術師なので、以下の操作をK回まで行うことができます。

• 3枚のうちいずれか1枚のカードを選び、書かれた整数を2倍する。

操作を行った後、以下の条件が同時に満たされれば、魔術は成功です。

• 緑のカードに書かれている整数は、赤のカードに書かれている整数より真に大きい。
• 青のカードに書かれている整数は、緑のカードに書かれている整数より真に大きい。

魔術を成功させることができるかどうか判定してください。

制約

• 1≤A,B,C≤7
• 1≤K≤7
• 入力はすべて整数

要はK回以内に赤<緑かつ緑<青を達成すれば良いと考えられます。この問題では、緑を赤に超えるまで2倍した回数+青が緑を超えるまで2倍した回数がKより以下であれば条件を満たす事が出来ます。

先ほどの一つの値を固定させるをこの問題的に言うと

• 赤の値を固定させて比較する

と解きやすくなるかなと思います。

自分の解答

B-Magic2.py

nums = input().split() #A,B,Cを入力

A = int(nums[0])
B = int(nums[1])
C = int(nums[2])

K = input() #Kを入力
k = int(K)

cnt = 0 #kより回数が以下だと魔術は成功するので比較するための整数cntを定義

while A >= B: #Bを2倍してA以上になる回数を記録
    cnt += 1
    B *= 2

while B >= C:  #Cを2倍してB以上になる回数を記録
    cnt += 1
    C *= 2


if cnt <= k:
    print("Yes")
else:
    print("No")

7 4 2    #A,B,C入力
3        #K入力
No       #出力

終わりに（メモ書き）

AtCoderでは難しい問題になってくるとそのまま問題の条件を書き移しても解答にたどり着かないので、問題の読解力と数学的思考力の両方が必要だなと思った。自分が高校まで国語を疎かにしていたつけが今来ている感じですね。ああ読解力が欲しい...

参考記事