公式

B - Standing Outliers 解説 by en_translator 印刷ページ


Consider whether each person \(i\) “stands apart.”

As stated in the problem, it suffices to check if \(|X_i - X_j| \ge D\) for all \(j ~ (i \ne j)\).

This can be done with a for statement: inspect all \(j\), and check whether “anybody violates this condition.” (It may be easier to understand by reading the sample code.)

All that left is to perform this for all \(i\), which can also be done with a for statement.


Sample code (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, d; cin >> n >> d;
  vector<int> x(n);
  for (int i=0; i<n; i++) cin >> x[i];
  
  vector<int> p;
  for (int i=0; i<n; i++){
      bool ok = true;
      for (int j=0; j<n; j++){
          if (i != j){
              if (abs(x[i] - x[j]) < d) ok = false; // Somebody violates the condition
          }
      }
      if (ok) p.push_back(i + 1);
  }
  cout << p.size() << endl;
  for (auto e : p) cout << e << " ";
  cout << endl;
}

In Python, one can use all or any to simplify the code:

n, d = map(int, input().split())
x = list(map(int, input().split()))
p = []
for i in range(n):
    if all(i == j or abs(x[i] - x[j]) >= d for j in range(n)):
        p.append(i + 1)
print(len(p))
print(*p)

投稿日時:
最終更新: