A問題 キャンディーとN人の子供イージー
|
1 2 3 4 5 |
n = int(input()) ans = 0 for i in range(1,n+1): ans += i print(ans) |
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に保存したコストの集合の最小値を出力する。という流れにしました。
解答
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
n = int(input()) a = list(map(int, input().split())) dict = {} for i in range(min(a),max(a)+1): #書き換え先の数字として、aの最小値から最大値までループ cost = 0 #コストを0に初期化 for j in range(n): #書き換え元の数字として、aの要素数(nの値)分ループ cost += (abs(i-a[j])**2) #コストを求める。iはmin(a)～max(a)の全ての値が順番に、a[j]はaの各要素が順番に入る。 dict[i] = cost #書き換え先の数字(i)をキー、コストを値として辞書dictに追加 #ans = min(dict,key=dict.get) 最小コストのキー ans = min(dict.values()) print(ans) |
わざわざ書き換え先の数字をキー、コストを値としてdictを作りましたが、今回の問題は答えとしてコストを出力すればよいので、辞書形式ではなくリスト形式でコストのみ保存する形で良かったかもしれません。
コメント