結果

問題 No.1584 Stones around Circle Pond
ユーザー lam6er
提出日時 2025-03-26 15:57:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 657 ms / 2,000 ms
コード長 2,889 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,820 KB
実行使用メモリ 98,608 KB
最終ジャッジ日時 2025-03-26 15:59:20
合計ジャッジ時間 18,654 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from fractions import Fraction

def solve():
    N, L = map(int, sys.stdin.readline().split())
    d = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    
    # Check if all pairs sum to the same value
    if N == 0:
        print("Yes")
        return
    S = B[0] + B[N]
    for i in range(1, N):
        if B[i] + B[i + N] != S:
            print("No")
            return
    
    # Check if S is divisible by L
    if S % L != 0:
        print("No")
        return
    T = S // L
    
    # Compute D array
    D = [B[i] - B[i + N] for i in range(N)]
    
    # Build matrix A
    A = []
    for j in range(N):
        row = []
        for k in range(N):
            diff = abs(d[k] - d[j])
            a = 2 * diff - L
            row.append(a)
        A.append(row)
    
    # Augmented matrix: A | D
    aug = []
    for i in range(N):
        row = [Fraction(A[i][k]) for k in range(N)]
        row.append(Fraction(D[i]))
        aug.append(row)
    
    # Perform Gaussian elimination
    n = N
    rank = 0
    for col in range(n):
        # Find the pivot row
        pivot = -1
        for r in range(rank, n):
            if aug[r][col] != 0:
                pivot = r
                break
        if pivot == -1:
            continue
        
        # Swap with the rank-th row
        aug[rank], aug[pivot] = aug[pivot], aug[rank]
        
        # Normalize the pivot row
        pivot_val = aug[rank][col]
        for c in range(col, n + 1):
            aug[rank][c] /= pivot_val
        
        # Eliminate other rows
        for r in range(n):
            if r != rank and aug[r][col] != 0:
                factor = aug[r][col]
                for c in range(col, n + 1):
                    aug[r][c] -= factor * aug[rank][c]
        
        rank += 1
    
    # Check for inconsistency
    for r in range(rank, n):
        if aug[r][-1] != 0:
            print("No")
            return
    
    # Extract solution
    solution = [Fraction(0) for _ in range(n)]
    for r in range(rank):
        leading_col = -1
        for c in range(n):
            if aug[r][c] != 0:
                leading_col = c
                break
        if leading_col == -1:
            continue
        # Solve for leading_col
        val = aug[r][-1]
        for c in range(leading_col + 1, n):
            val -= aug[r][c] * solution[c]
        solution[leading_col] = val
    
    # Check if all solutions are integers
    for z in solution:
        if z.denominator != 1:
            print("No")
            return
    z_list = [int(z) for z in solution]
    
    sum_abs_z = sum(abs(z) for z in z_list)
    if sum_abs_z > T:
        print("No")
        return
    
    sum_z = sum(z_list)
    if (sum_z % 2) != (T % 2):
        print("No")
        return
    
    print("Yes")

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