公式
B - Standing Outliers 解説
by
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)
投稿日時:
最終更新: