[イーコット]グリディ-大数の法則

🔔 質問する

「大数の法則」は統計分野の内容が一般的だが、東彬は独自の方法で異なる方法を使っている.東彬の大数法則は,異なる数の配列がある場合,与えられた数をM回加算して最大数を形成する法則である.しかし,この法則の特徴は,配列された特定のインデックス(番号)の数が連続してK回を超えないことである.
例えば、2、4、5、4、6の配列が順にあるとすると、Mは8、Kは3となる.この場合、あるインデックスの数を連続して3回加算することができるので、大数法則によれば、結果は6+6+6+5+6+6+5人46となる.
ただし、異なるインデックスの対応する数が同じ場合は、異なるとみなされます.例えば,3,4,3,4,3の配列が順にあると仮定すると,Mは7,Kは2である.この場合、2番目の要素に対応する4と4番目の再要素に対応する4とを2回交互に行うことができる.結果は4+4+4+4+4+4+4+4+4+4人28を導出した.配列の大きさN,数字を加算した回数M,Kを与えた場合,東彬の大数則に従って結果を出力する.

入力

第1行は、N(2<=N<=1000)、M(1<=M<=10000)、K(1<=K<=10000)の自然数を与え、各自然数はスペースで区切られる.

行目にはN個の自然数がある.各自然数はスペースで区切られています.ただし、自然数ごとに1以上10000以下の数です.

入力によって与えられるKは、常にM以下である.

しゅつりょく

の最初の行では、東彬の大数の法則に基づいて、加算された答えが出力されます.

🎯 解答方法

この問題を解決するには、入力値の最大数と2番目に大きい数を保存するだけです.連続加算できる回数はK回までで、「最大数K回、2回目の大数1回加算」を繰り返すとよい.

💻 Pythonコード

n, m, k = map(int, input().split()) # 배열 크기, 더해지는 횟수, 연속 몇번까지
numbers = sorted(list(map(int, input().split())), reverse=True)

first = numbers[0] # 가장 큰 수
second = numbers[1] # 두번째로 큰 수

answer = 0
while True:
    for i in range(k):
        if m == 0:
            break
        answer += first
        m -= 1

    if m == 0:
        break
    answer += second
    m -= 1

print(answer)

💡 考えなければならないこと

この問題はMが10000以下であるため、このような方法で解決することも可能であるが、Mの大きさが100億以上の大きさであればタイムアウトと判定される.簡単な数学思想で問題をより効果的に解決してみよう.例えば、Nを5、入力値を2、4、5、4、6とする.
この場合、次のように最大数と2番目の大きい数を選択します.

最大数:624579182

の2番目の数字:5

このときMが8、Kが3であれば、以下の場合に最大和を加えることができる.言い換えれば(6+6+6+5)+(6+6+6+5)、正解は46です.
この問題を解くには、まず繰り返しの数列を身につけなければならない.最大数と2番目の大数を加算する場合,特定の数列形式で一定の繰返し加算の特徴を持つ.上記の例では、数列[6,6,6,5]が繰り返される.では、重複数列の長さはどのくらいでしょうか.正(K+1)は、上記の例では4である.したがって,Mを(K+1)で割ったシェアは数列重複の回数となる.ここでKを乗じると出現回数が最も多い.この場合もMは区別しない(K+1)場合を考慮する.この場合、Mを(K+1)で割ると最大数が増えるので、この点を考慮する.すなわち、「最大増加数」はint(M/(K+1)*K+M%(K+1)である.その結果,上記式を用いて最大数加算の回数を求め,その後,この式を用いて2番目に大きい数加算の回数を求める.

💻 改良されたPythonコード

n, m, k = map(int, input().split())
numbers = sorted(list(map(int, input().split())), reverse=True)

first = numbers[0]
second = numbers[1]

count = int(m/(k+1))*k
count += m%(k+1)

answer = 0
answer += count * first
answer += (m-count) * second

print(answer)