[AtCoder] diverta 2019 Programming Contest 2 B – Picking Up
問題
方針
\( p, q \) を固定して全探索を行う
ボールの各座標を位置ベクトルとして、 \( \vec{v}_i = (x_i, y_i) \) と表すことにします。\( p, q \) の候補は、任意の二つの位置ベクトルの差分として、\( \vec{u}_{i, j} = (x_i – x_j, y_i – y_j) \) とします。これは、\( N \) 個から \( 2 \) 個選ぶ組み合わせに、向きを考慮して、\( N(N – 1) \) 通りあることになります。 なぜこのような候補になるかというと、これ以外の \( p, q\) の値は、コストが \( 0 \) になる可能性がないからです。
また、コストが掛からないときは、どういうことかというと、
\[ \vec{v}_i =\vec{v}_j + \vec{u}_{k, l} \ (i \neq j \wedge k \neq l)\]
を満たすということです。したがって、\(\vec{u}_{k, l} \) と \( \vec{v}_i, \vec{v}_j \) の全探索行うので、\( 4 \) 重ループの計算を行えば良いです。ここで、注意する点は同じ座標のボールは存在しないことから、\( \vec{u}_{k, l} \) と \( \vec{u}_j \) を固定したとき、上記の式を満たす \( \vec{v}_i \) は最大でも一つしかありません。
コード
提出したコード
全探索
int ans = N; for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N; j++) { if (i == j) continue; int p = x[i] - x[j]; int q = y[i] - y[j]; int cnt = 0; for (int k = 0; k < N; k++) { for (int l = 0; l < N; l++) { if (k == l) continue; if (x[k] - x[l] == p && y[k] - y[l] == q) { cnt++; } } } ans = min(ans, N - cnt); } }
ディスカッション
コメント一覧
まだ、コメントがありません