コンテンツにスキップ

ABC477 B - Standing Outliers

サイト
AtCoder
コンテスト
ABC477
問題
B - Standing Outliers
難易度
79

数直線上に NN 人がいて、人 ii は座標 XiX_i にいます。自分以外のどの人との距離も DD 以上である人の番号を、昇順にすべて出力する問題です(N≤100N \le 100)。

N≤100N \le 100 なので、各人 ii について他の全員との距離 ∣Xi−Xj∣|X_i - X_j| を調べれば O(N2)O(N^2) で間に合います。

ソートを使うと O(Nlog⁡N)O(N \log N) にもなります。座標を昇順に並べると、ある人に最も近い人は並びで両隣のどちらかです。なので、両隣との差がどちらも DD 以上かどうかだけ調べれば十分です。同じ座標の人がいる場合は差が 0<D0 < D になるので、そのまま正しく判定できます。

Python
N, D = map(int, input().split())
X = list(map(int, input().split()))
ans = [i + 1 for i in range(N) if all(abs(X[i] - X[j]) >= D for j in range(N) if i != j)]
print(len(ans))
print(*ans)

全員の組を調べる O(N2)O(N^2) の解法です。

Uiua
≡&p+1⊚&p/+.⍜⍆(⬚1×⊂1.≥⊣:⧈-)∩(⊜⋕⊸≠@ &sc)

∩(⊜⋕⊸≠@ &sc) で 2 行を読み、それぞれ空白区切りの数値の配列にします。

⍜⍆(…) は、XX をソートしてから中の処理をし、結果を元の順番に戻します。中の処理は次のとおりです。

  1. ⧈- で隣り合う座標の差を求めます。
  2. ⊣: で 1 行目の [N,D][N, D] から DD を取り出し、≥ で各差が DD 以上かどうかの 0/1 の列にします。この列の kk 番目は、ソート後の kk 番目と k+1k+1 番目の人の間が離れているかを表します。
  3. ⊂1. で、この列を複製して片方の先頭に 11 を付けます。⬚1× で、もう片方の末尾を 11 で埋めて掛け合わせます。これで各人について「左隣とも右隣とも DD 以上離れているか」が求まります。両端の人は、いない側の隣を 11(離れている)として扱っています。

あとは /+. で人数を数えて &p で出力し、⊚ で 1 になっている位置を取り出して +1 で 1 始まりの番号にし、≡&p で出力しています。番号は 1 行に 1 つずつ出力しますが、AtCoder のジャッジは空白と改行の違いを区別しないので、これで通ります。