結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー Craft Boss
提出日時 2025-10-07 17:17:58
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,530 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 32,248 KB
最終ジャッジ日時 2025-10-07 17:18:04
合計ジャッジ時間 6,016 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 RE * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
競技プログラミング Never walk alone
作成日 2025/9/30
問題
数直線上に配置された N 個の駅に関する問題です。要点は以下の通りです。
【駅と座標】  
N 個の駅があり、それぞれの駅には座標 x_i が与えられています。  
座標は昇順 (x_1 < x_2 < ... < x_N) で並んでいます。
【移動ルール】  
2 つの異なる駅 i と j の間の距離 |x_i − x_j| が、指定された範囲 [A, B] (A 以上 B 以下) に収まる場合、これらの駅間を電車で直接移動できます。
【求めるもの】  
各駅 i について「その駅から電車を乗り継いで（0 回以上の移動で）到達できる駅の総数」を求めなさい。  
「0 回以上の移動で到達できる」とは、駅 i 自身も含め、駅 i と同じ連結成分に属するすべての駅を数え上げることを意味します。
"""

N, A, B = map(int, input().split())     #N:駅数, AからBの範囲内駅同士なら線路で繋げる
xi = list(map(int, input().split()))    #0 2 5 7 9のように駅がある座標が小さい順に

linelist = [[xi[0]]]    #二重構造のリストで線ごとにリストに入れる
for i in range(1, N):   #０以外の駅の数だけ繰り返す
    for j in range(i):  #0からi番目の駅までに線路で繋げる駅が
        if A <= xi[i]-xi[j] and xi[i]-xi[j] <= B:   #１つでもあるかどうか
            for k, sublist in enumerate(linelist):  #その駅がlinelistの何番目の線に含まれているかkに記録
                if xi[j] in sublist:
                    break

            found=False #他に繋がる駅があるかも調べる↓
            for rest in range(j+1, i):  #見つかった駅の次の駅からi番目までの間で
                if A <= xi[i]-xi[rest] and xi[i]-xi[rest] <= B:
                    for l, sublist in enumerate(linelist):  #他に繋がる駅があれば線のリストを２つ以上合体しなければいけない
                        if xi[rest] in sublist:
                            linelist[k].extend(linelist[l])
                            del linelist[l]

            
            linelist[k].append(xi[i])   #最後にi番目の駅を線路に追加
            break
    else:       # 繋がる駅がなかったら新しい線として加える
        linelist.append([xi[i]])

for i in range(N):
    for sublist in linelist:
        if xi[i] in sublist:
            print(len(sublist))
            break
0