結果

問題 No.2221 Set X
ユーザー lam6er
提出日時 2025-03-20 20:40:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,835 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 81,976 KB
実行使用メモリ 133,476 KB
最終ジャッジ日時 2025-03-20 20:40:30
合計ジャッジ時間 5,645 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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]))
    
    if N == 1:
        print(1)
        print(2)
        return
    
    gaps = [A[i] - A[i-1] for i in range(1, N)] if N > 1 else []
    max_gap = max(gaps) if gaps else 0
    max_A = A[-1]
    
    candidates = set()
    for X in range(1, min(200000, max_A + 2)):
        candidates.add(X)
    
    if max_gap > 0:
        candidates.update({max_gap, max_gap - 1, max_gap + 1, max_gap // 2, (max_gap + 1) // 2})
    
    candidates.update({max_A, max_A + 1, max_A + 2})
    
    candidates.add((max_gap // 3) if max_gap > 0 else 0)
    candidates.add((max_gap * 2 // 3) if max_gap > 0 else 0)
    
    for a in A:
        if a == 0:
            continue
        max_k = int(math.isqrt(a)) + 2
        for k in range(1, max_k):
            candidates.add(a // k)
            candidates.add(a // k + 1)
            candidates.add(a // k - 1)
    
    candidates.discard(0)
    if not candidates:
        print(1)
        print(2)
        return
    
    min_f = float('inf')
    best_X = None
    
    for X in sorted(candidates):
        if X <= 0:
            continue
        prev = A[0] // X
        count = 1
        for num in A[1:]:
            current = num // X
            if current != prev:
                count += 1
                prev = current
        current_f = (X + 1) * count
        if current_f < min_f or (current_f == min_f and X < best_X):
            min_f = current_f
            best_X = X
    
    X_candidate = max_A + 1
    current_f = (X_candidate + 1) * 1
    if current_f < min_f or (current_f == min_f and X_candidate < best_X):
        min_f = current_f
        best_X = X_candidate
    
    print(best_X)
    print(min_f)

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