結果

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

ソースコード

diff # 

import sys
import math

def input():
    return sys.stdin.read()

def main():
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    S = [x for x in A if x != 0]
    if not S:
        print("Yes")
        return
    
    S.sort()
    if S[0] == S[-1]:
        print("Yes")
        return
    
    # Compute GCD of differences
    diffs = []
    for i in range(1, len(S)):
        diffs.append(S[i] - S[i-1])
    g = 0
    for d in diffs:
        g = math.gcd(g, d)
    
    # Function to generate all divisors of g
    def get_divisors(x):
        if x == 0:
            return []
        divisors = set()
        for i in range(1, int(math.isqrt(x)) + 1):
            if x % i == 0:
                divisors.add(i)
                divisors.add(x // i)
        return sorted(divisors)
    
    divisors = get_divisors(g)
    
    # Also consider the candidate d from (max_S - min_S) / (N-1)
    max_S = S[-1]
    min_S = S[0]
    if (max_S - min_S) % (N-1) == 0:
        d_candidate = (max_S - min_S) // (N-1)
        divisors.append(d_candidate)
    
    # Remove duplicates and ensure divisors are positive
    divisors = list(set(divisors))
    divisors = [d for d in divisors if d > 0]
    
    # Check each divisor
    for d in divisors:
        # Check all elements have the same remainder mod d
        remainder = S[0] % d
        valid = True
        for x in S:
            if x % d != remainder:
                valid = False
                break
        if not valid:
            continue
        
        a = remainder
        if a == 0:
            a += d  # Try to make a positive, but then check if it's valid
            # Check if a is positive and allows S[0] to be in the sequence
            # S[0] = a + k*d => k = (S[0] - a)/d
            if a == 0:
                a = d  # To ensure a is positive
            k = (S[0] - a) // d
            if k < 0 or k >= N:
                continue
        
        # Now check if all elements in S are in the sequence a + i*d for 0 <= i < N
        valid = True
        for x in S:
            delta = x - a
            if delta % d != 0:
                valid = False
                break
            k = delta // d
            if k < 0 or k >= N:
                valid = False
                break
        if valid:
            # Check all terms are positive
            if a <= 0:
                continue
            # The last term is a + (N-1)*d
            if a + (N-1)*d <= 0:
                continue
            print("Yes")
            return
    
    # Check the case where a is min_S and d is (max_S - min_S) / k, where k is the number of steps between min and max
    # This is a special case where the sequence starts with min_S and ends with max_S
    if (max_S - min_S) % (N-1) == 0:
        d = (max_S - min_S) // (N-1)
        if d == 0:
            print("Yes")
            return
        # Check if all elements are in the sequence min_S, min_S +d, ..., min_S + (N-1)*d
        valid = True
        for x in S:
            delta = x - min_S
            if delta % d != 0:
                valid = False
                break
            k = delta // d
            if k < 0 or k >= N:
                valid = False
                break
        if valid:
            print("Yes")
            return
    
    print("No")

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