結果

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

ソースコード

diff # 

import math

def get_divisors(n):
    if n == 0:
        return []
    divisors = set()
    for i in range(1, int(math.isqrt(n)) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(divisors)

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 not S:
        print("Yes")
        return
    
    all_same = True
    first = S[0]
    for x in S:
        if x != first:
            all_same = False
            break
    if all_same:
        print("Yes")
        return
    
    S_sorted = sorted(S)
    diffs = []
    for i in range(1, len(S_sorted)):
        diffs.append(S_sorted[i] - S_sorted[i-1])
    
    g = diffs[0]
    for d in diffs[1:]:
        g = math.gcd(g, d)
    
    divisors = get_divisors(g)
    
    possible = False
    for d in divisors:
        r = S_sorted[0] % d
        valid = True
        for x in S_sorted:
            if x % d != r:
                valid = False
                break
        if not valid:
            continue
        
        max_S = S_sorted[-1]
        min_S = S_sorted[0]
        lower_a = max(max_S - (N - 1) * d, 1)
        upper_a = min_S
        
        if lower_a > upper_a:
            continue
        
        rem = lower_a % d
        delta = (r - rem) % d
        a_candidate = lower_a + delta
        if a_candidate < lower_a:
            a_candidate += d
        
        if a_candidate > upper_a:
            continue
        
        possible = True
        break
    
    print("Yes" if possible else "No")

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