結果

問題 No.1884 Sequence
ユーザー lam6er
提出日時 2025-04-16 15:42:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,642 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 154,880 KB
最終ジャッジ日時 2025-04-16 15:46:04
合計ジャッジ時間 12,976 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 5 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    S = [x for x in A if x > 0]
    
    if len(S) == 0:
        print("Yes")
        return
    if len(S) == 1:
        print("Yes")
        return
    
    S.sort()
    base = S[0]
    diffs = []
    for x in S[1:]:
        diffs.append(x - base)
    
    from math import gcd
    g = 0
    for d in diffs:
        g = gcd(g, d)
    
    if g == 0:
        print("Yes")
        return
    
    def get_divisors(g_val):
        if g_val == 0:
            return []
        divisors = set()
        for i in range(1, int(math.isqrt(g_val)) + 1):
            if g_val % i == 0:
                divisors.add(i)
                divisors.add(g_val // i)
        return sorted(divisors)
    
    divisors = get_divisors(g)
    
    found = False
    for d in divisors:
        r = S[0] % d
        valid = True
        for x in S:
            if x % d != r:
                valid = False
                break
        if not valid:
            continue
        
        x_r_list = [(x - r) // d for x in S]
        lower_bound_m = max(x_r - (N - 1) for x_r in x_r_list)
        upper_bound_m = min(x_r_list)
        
        if lower_bound_m > upper_bound_m:
            continue
        
        a_max = r + upper_bound_m * d
        if a_max > S[0]:
            continue
        
        a_min = r + lower_bound_m * d
        if (a_min + (N - 1) * d) < S[-1]:
            continue
        
        found = True
        break
    
    print("Yes" if found else "No")

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