こういう全探索、意外と思い浮かぶようになるまでが遠いよね。
そして のケースが結構厄介 ^^;
問題概要
二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、
- 最初の点では +1
- その後移動するたびに、移動ベクトルが のときは +0
- そうでないときは +1
したものがペナルティとなる。ペナルティの最小値を求めよ。
制約
考えたこと
まず の選び方が途方もなく多く見えるがそんなことはなく、
- ある についての
についてのみ試せば十分である。なぜなら、どの 2 点をとってもその差ベクトルになってないような を使ったらペナルティは になる。これより小さくはできない。なので、上記の場合だけ試せばよい。この時点で 通り。
さて、 を決めたらあとは、実際に 点を上手く並べることで、なるべく なジャンプが多くなるようにしたい。再びすべての に対して調べることで、 なジャンプが何個あるのかを求めればよい。
ただし、 の場合に要注意!!!!!
#include <iostream> #include <vector> using namespace std; int N; vector<long long> x, y; int solve() { if (N == 1) return 1; int res = N; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) continue; long long dx = x[j] - x[i], dy = y[j] - y[i]; int sub = 0; for (int i2 = 0; i2 < N; ++i2) { for (int j2 = 0; j2 < N; ++j2) { if (j2 == i2) continue; if (dx == x[j2] - x[i2] && dy == y[j2] - y[i2]) ++sub; } } res = min(res, N - sub); } } return res; } int main() { cin >> N; x.resize(N); y.resize(N); for (int i = 0; i < N; ++i) cin >> x[i] >> y[i]; cout << solve() << endl; }