結果

問題 No.2221 Set X
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:06:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,697 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 97,868 KB
最終ジャッジ日時 2025-06-12 18:08:18
合計ジャッジ時間 4,641 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    A = sorted(A)
    candidates = set()

    # Add candidates from 1 to 1e5
    for x in range(1, min(100000, A[-1] + 1)):
        candidates.add(x)
    
    # Add candidates around sqrt of each A_i
    for a in A:
        if a == 0:
            continue
        s = int(math.sqrt(a))
        for x in [s-1, s, s+1, s+2]:
            if x > 0:
                candidates.add(x)
    
    # Add candidates from differences between consecutive elements
    for i in range(N-1):
        d = A[i+1] - A[i]
        if d == 0:
            continue
        s = int(math.sqrt(d))
        for x in [s-1, s, s+1, s+2]:
            if x > 0:
                candidates.add(x)
        candidates.add(d)
        candidates.add(d+1)
        candidates.add(d-1)
    
    # Add candidates from each A_i
    for a in A:
        if a == 0:
            continue
        candidates.add(a)
        candidates.add(a+1)
        candidates.add(a-1)
    
    # Add candidate A_N + 1
    candidates.add(A[-1] + 1)
    candidates.add(A[-1] + 2)
    
    # Now evaluate all candidates
    min_f = float('inf')
    best_x = float('inf')
    for x in sorted(candidates):
        if x <= 0:
            continue
        seen = set()
        cnt = 0
        for a in A:
            q = a // x
            if q not in seen:
                seen.add(q)
                cnt += 1
        current = (x + 1) * cnt
        if current < min_f or (current == min_f and x < best_x):
            min_f = current
            best_x = x
    print(best_x)
    print(min_f)

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