結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー Craft Boss
提出日時 2025-10-01 18:19:53
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 3,535 bytes
コンパイル時間 3,055 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2025-10-01 18:20:07
合計ジャッジ時間 14,337 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 入力の受け取り
N, A, B = map(int, input().split())
station_coords = list(map(int, input().split()))

# グループ（連結成分）を管理するリスト
groups = []
# 各駅の座標がどのグループに属しているかを高速に引くための辞書
# {駅の座標: groupsのインデックス} という形で格納する
station_to_group_idx = {}

# 1つずつ駅を処理していく
for i, current_station in enumerate(station_coords):
    
    # この駅が接続する可能性のある、既存のグループのインデックスを格納する集合
    # 集合(set)を使うことで、重複なくインデックスを管理できる
    connected_group_indices = set()
    
    # この駅より手前にある全ての駅との接続を調べる
    for j in range(i):
        prev_station = station_coords[j]
        distance = current_station - prev_station
        
        # 接続条件を満たす場合
        if A <= distance <= B:
            # 接続先の駅が属するグループのインデックスを取得し、集合に追加
            group_idx = station_to_group_idx[prev_station]
            connected_group_indices.add(group_idx)

    # --- 接続判定後のグループ分け処理 ---

    # 1. どの既存グループとも接続しなかった場合
    if not connected_group_indices:
        # 新しいグループを作成し、リストの末尾に追加
        new_group_idx = len(groups)
        groups.append([current_station])
        station_to_group_idx[current_station] = new_group_idx
        
    # 2. 1つ以上の既存グループと接続した場合
    else:
        # 接続したグループを全て1つに統合（マージ）する
        
        # 統合のベースとなるグループを決め、新しい駅を追加する
        # (ソートして一番若いインデックスのグループをベースにするのが分かりやすい)
        sorted_indices = sorted(list(connected_group_indices))
        target_group_idx = sorted_indices[0]
        groups[target_group_idx].append(current_station)
        station_to_group_idx[current_station] = target_group_idx

        # 残りのグループをベースとなるグループに統合していく
        # (インデックスが大きい順に処理すると、リストから削除する際に安全)
        for idx_to_merge in sorted_indices[1:][::-1]:
            # 統合されるグループを取り出す
            group_to_merge = groups.pop(idx_to_merge)
            
            # ベースのグループに要素を追加
            groups[target_group_idx].extend(group_to_merge)
            
            # 辞書の情報も更新する必要があるが、削除でインデックスがずれるため
            # この後のループで辞書を再構築する
    
    # グループの削除によってインデックスがずれた可能性があるので、
    # 辞書(station_to_group_idx)を現在のgroupsの状態に合わせて再構築する
    # (少し非効率だが、ロジックをシンプルで安全に保つため)
    station_to_group_idx = {}
    for idx, group in enumerate(groups):
        for station in group:
            station_to_group_idx[station] = idx


# --- 結果の出力 ---
results = {} # 各駅の答えを保持するための辞書
for group in groups:
    group_len = len(group)
    for station in group:
        results[station] = group_len

for station in station_coords:
    print(results[station])
0