結果

問題 No.3051 Make All Divisible
コンテスト
ユーザー LyricalMaestro
提出日時 2026-03-22 04:46:19
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,504 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 344 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 77,952 KB
最終ジャッジ日時 2026-03-22 04:46:22
合計ジャッジ時間 2,208 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 6 RE * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://yukicoder.me/problems/no/3051


def solve(N, K, A):
    sum_a = sum(A)
    if sum_a % K != 0:
        return -1
    
    if K == 1:
        return 0
    
    v = 0
    max_a = 0
    for a in A:
        max_a = max(max_a, a % K)
        v += a % K
    v //= K

    if v >= max_a:
        return v
    
    array1 = []
    array2 = []
    array3 = []
    for a in A:
        array1.append(a // K)
        array2.append(a % K)
        if array1[-1] > 0:
            array3.append(True)
        else:
            array3.append(False)
    
    n0 = 0
    for i in range(N):
        if array1[i] > 0:
            n0 += 1

    while n0 >= K:
        a = float("inf")
        for i in range(N):
            if array3[i]:
                a = min(a, array1[i])
        
        l = (max_a - v) // (n0 - K)
        l += 1 if (max_a - v) % (n0 - K) else 0

        if a < l:
            max_a += a * K
            v += a * n0
            for i in range(N):
                if array3[i]:
                    array1[i] -= a
                    if array1[i] == 0:
                        array3[i] = False
                        n0 -= 1
            for i in range(N):
                if array3[i]:
                    array2[i] += a * K
        else:
            max_a += (l - 1) * K
            v += (l - 1) * n0
            for i in range(N):
                if array3[i]:
                    array1[i] -= (l - 1)
                    if array1[i] == 0:
                        array3[i] = False
                        n0 -= 1

            for i in range(N):
                if array3[i]:
                    array2[i] += (l - 1) * K

            for _ in range(n0):
                target_id = -1
                min_ = float("inf")
                for i in range(N):
                    if array3[i]:
                        if array2[i] < min_:
                            min_ = array2[i]
                            target_id = i
                
                max_a = max(max_a, array2[target_id] + K)
                array2[target_id] += K
                v += 1
                array1[target_id] -= 1
                if v >= max_a:
                    return v
    return -1











    




def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N, K = map(int, input().split())
        A = list(map(int, input().split()))
        ans = solve(N, K, A)
        answers.append(ans)
    
    for ans in answers:
        print(ans)

if __name__ == "__main__":
    main()
0