公式

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


各人 \(i\) について「一線を画す」かどうかを判定することを考えましょう。

これは、問題文にある通り、すべての \(j ~ (i \ne j)\) について、 \(|X_i - X_j| \ge D\) が成り立つかどうか、を判定すれば良いです。

これは for文 を用いて、すべての \(j\) を見て、この条件を「守らない人がいるかどうか」を判定すれば良いです。(詳しくは実装例を見た方がわかりやすいでしょう)

そして、これをすべての \(i\) について、計算すれば良いので、これも同様に for 文で処理できます。


実装例 (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; // 条件を満たさない人がいる
          }
      }
      if (ok) p.push_back(i + 1);
  }
  cout << p.size() << endl;
  for (auto e : p) cout << e << " ";
  cout << endl;
}

Python では all や any を用いることで、いくらか簡単に記述できます。

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)

投稿日時:
最終更新: