結果

問題 No.1538 引きこもりさんは引き算が得意。
ユーザー lam6er
提出日時 2025-04-16 00:53:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,038 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 487,036 KB
最終ジャッジ日時 2025-04-16 00:55:16
合計ジャッジ時間 6,042 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys
from math import gcd

def main():
    n, k = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    if k in a:
        print("Yes")
        return
    
    def compute_gcd(arr):
        current_gcd = abs(arr[0])
        for num in arr[1:]:
            current_gcd = gcd(current_gcd, abs(num))
            if current_gcd == 0:
                break
        return current_gcd
    
    gcd_all = compute_gcd(a)
    
    if gcd_all == 0 or k % gcd_all != 0:
        print("No")
        return
    
    # Normalize the array and k
    normalized_k = k // gcd_all
    normalized_a = [x // gcd_all for x in a]
    
    # BFS setup
    queue = deque()
    initial_state = tuple(sorted(normalized_a))
    queue.append(initial_state)
    visited = set()
    visited.add(initial_state)
    
    found = False
    while queue:
        current = queue.popleft()
        if normalized_k in current:
            found = True
            break
        m = len(current)
        if m < 2:
            continue
        # Generate all possible next states
        for i in range(m):
            for j in range(i + 1, m):
                x, y = current[i], current[j]
                # Generate new state by replacing x and y with x - y
                new1 = list(current)
                del new1[j], new1[i]
                new1.append(x - y)
                new_state1 = tuple(sorted(new1))
                if new_state1 not in visited:
                    visited.add(new_state1)
                    queue.append(new_state1)
                # Generate new state by replacing x and y with y - x
                new2 = list(current)
                del new2[j], new2[i]
                new2.append(y - x)
                new_state2 = tuple(sorted(new2))
                if new_state2 not in visited:
                    visited.add(new_state2)
                    queue.append(new_state2)
    
    print("Yes" if found else "No")

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