結果

問題 No.3109 Swap members
ユーザー keigo kuwata
提出日時 2025-04-20 11:03:40
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,745 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2025-04-20 11:03:45
合計ジャッジ時間 4,369 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

def can_arrange(N, K, S, T):
    # インデックスiの部員がどの連結成分に属するかを記録
    component = [-1] * N
    component_id = 0
    
    # 連結成分を求める
    for i in range(N):
        if component[i] != -1:
            continue
        
        # BFSで連結成分を探索
        queue = [i]
        component[i] = component_id
        while queue:
            current = queue.pop(0)
            # current+K番目と繋がっている場合
            if current + K < N and component[current + K] == -1:
                component[current + K] = component_id
                queue.append(current + K)
            # current-K番目と繋がっている場合
            if current - K >= 0 and component[current - K] == -1:
                component[current - K] = component_id
                queue.append(current - K)
        
        component_id += 1
    
    # 各連結成分ごとに、元の並びと目標の並びを抽出
    original_components = [[] for _ in range(component_id)]
    target_components = [[] for _ in range(component_id)]
    
    for i in range(N):
        comp = component[i]
        original_components[comp].append(S[i])
    
    # 目標の並びから、各ユーザー名がどの連結成分に属するか特定
    user_to_component = {}
    for i in range(N):
        user_to_component[S[i]] = component[i]
    
    for i in range(N):
        comp = user_to_component[T[i]]
        target_components[comp].append(T[i])
    
    # 各連結成分内で、元の並びと目標の並びが一致するか確認
    for i in range(component_id):
        if sorted(original_components[i]) != sorted(target_components[i]):
            return False
    
    return True
0