ABC477 B - Standing Outliers
- サイト
- AtCoder
- コンテスト
- ABC477
- 問題
- B - Standing Outliers
- 難易度
- 79
数直線上に 人がいて、人 は座標 にいます。自分以外のどの人との距離も 以上である人の番号を、昇順にすべて出力する問題です()。
なので、各人 について他の全員との距離 を調べれば で間に合います。
ソートを使うと にもなります。座標を昇順に並べると、ある人に最も近い人は並びで両隣のどちらかです。なので、両隣との差がどちらも 以上かどうかだけ調べれば十分です。同じ座標の人がいる場合は差が になるので、そのまま正しく判定できます。
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)全員の組を調べる の解法です。
Uiua
≡&p+1⊚&p/+.⍜⍆(⬚1×⊂1.≥⊣:⧈-)∩(⊜⋕⊸≠@ &sc)∩(⊜⋕⊸≠@ &sc) で 2 行を読み、それぞれ空白区切りの数値の配列にします。
⍜⍆(…) は、 をソートしてから中の処理をし、結果を元の順番に戻します。中の処理は次のとおりです。
⧈-で隣り合う座標の差を求めます。⊣:で 1 行目の から を取り出し、≥で各差が 以上かどうかの 0/1 の列にします。この列の 番目は、ソート後の 番目と 番目の人の間が離れているかを表します。⊂1.で、この列を複製して片方の先頭に を付けます。⬚1×で、もう片方の末尾を で埋めて掛け合わせます。これで各人について「左隣とも右隣とも 以上離れているか」が求まります。両端の人は、いない側の隣を (離れている)として扱っています。
あとは /+. で人数を数えて &p で出力し、⊚ で 1 になっている位置を取り出して +1 で 1 始まりの番号にし、≡&p で出力しています。番号は 1 行に 1 つずつ出力しますが、AtCoder のジャッジは空白と改行の違いを区別しないので、これで通ります。