【Python】AtCoder Beginner Contest 043 A,C問題 解答・解説

この記事は約2分で読めます。

A問題 キャンディーとN人の子供イージー

 

C問題 いっしょ

方針

N個の数字を全て同じ数字に書き換えるときの最小コストを求める問題です。

N=3、A = [1,2,3]の時、書き換えのコストは以下の通り求められます。

(1-2)**2 + (2-2)**2 + (3-2)**2

つまり、(書き換え元の数字 – 書き換え先の数字)の2乗の合計です。

最小コストを出力すると正解になります。

入力例を全て見てみると、どうやらコストが最小となるのは、aの最大値と最小値の間の数字のようです。

→入力例1:N=2,a=[4,8]、書き換え先の数字:6

→入力例2:N=3,a=[1,1,3]、書き換え先の数字:2

→入力例3:N=3,a=[4,2,5]、書き換え先の数字:4

→入力例4:N=4,a=[-100,-100,-100,-100]、書き換え先の数字:不要

 

なので、aの最小値から最大値までを書き換え先の数字として繰り返し処理を行う。

繰り返しの中でaの各要素(nの値)からの書き換えコストの合計値を辞書dictに保存する。

辞書dictに保存したコストの集合の最小値を出力する。という流れにしました。

解答

わざわざ書き換え先の数字をキー、コストを値としてdictを作りましたが、今回の問題は答えとしてコストを出力すればよいので、辞書形式ではなくリスト形式でコストのみ保存する形で良かったかもしれません。

参考

Pythonで辞書の値の最大値・最小値とそのキーを取得 | note.nkmk.me

コメント