この問題は、3点を含む放物線の特性を利用して解くことができます。各放物線は原点を通るため、任意の2点で形状を決定できます。

状態遷移にはビットマスクを用い、stateという変数で現在の破壊状況を管理します。右端からi番目のビットが立っていると、対応する対象が破壊済みであることを示します。最終的に全ビットが立った状態(1 << n) - 1に到達すれば解決です。

事前処理として、path[i][j]という2次元配列を準備します。これはiとjを通る放物線が破壊可能な対象を表したビットマスクです。この配列は以下のように計算されます：

1. 2点のx座標が一致する場合は無視
2. 放物線の係数aが0以上（下に凸）の場合は無効
3. その他の条件を満たす場合、全対象に対して破壊可能性をチェック

解法実装例

バックトラッキング方式

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN = 20, MAXM = 1 << 18;
int T, n, m;
double x[MAXN], y[MAXN];
int path[MAXN][MAXN], dp[MAXM];

bool is_equal(double a, double b) {
    return abs(a - b) < 1e-8;
}

void compute_path(int i, int j) {
    if (i == j) {
        path[i][j] = 1 << i;
        return;
    }
    double xi = x[i], yi = y[i];
    double xj = x[j], yj = y[j];
    
    if (is_equal(xi, xj)) return;
    double a = (yi/xi - yj/xj) / (xi - xj);
    if (a >= 0) return;
    
    double b = yi/xi - a * xi;
    int mask = 0;
    
    for (int k = 0; k < n; ++k) {
        double yk = a * x[k] * x[k] + b * x[k];
        if (is_equal(yk, y[k])) mask |= 1 << k;
    }
    
    path[i][j] = mask;
    path[j][i] = mask;
}

void dfs(int state, int count) {
    if (count >= dp[state]) return;
    dp[state] = count;
    
    if (state == (1 << n) - 1) return;
    
    int idx = 0;
    while (state & (1 << idx)) ++idx;
    
    for (int i = 0; i < n; ++i) {
        if (path[idx][i]) {
            dfs(state | path[idx][i], count + 1);
        }
    }
}

int main() {
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
        
        memset(path, 0, sizeof(path));
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                compute_path(i, j);
            }
        }
        
        fill(dp, dp + (1 << n), 1000);
        dfs(0, 0);
        cout << dp[(1 << n) - 1] << endl;
    }
    return 0;
}

動的計画法方式

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN = 20;
const int MAXM = 1 << 18;
double x[MAXN], y[MAXN];
int path[MAXN][MAXN];

bool approx(double a, double b) {
    return abs(a - b) < 1e-8;
}

void build_path(int i, int j, int n) {
    if (i == j) {
        path[i][j] = 1 << i;
        return;
    }
    double xi = x[i], yi = y[i];
    double xj = x[j], yj = y[j];
    
    if (approx(xi, xj)) return;
    double a = (yi/xi - yj/xj) / (xi - xj);
    if (a >= 0) return;
    
    double b = yi/xi - a * xi;
    int mask = 0;
    
    for (int k = 0; k < n; ++k) {
        double yk = a * x[k] * x[k] + b * x[k];
        if (approx(yk, y[k])) mask |= 1 << k;
    }
    
    path[i][j] = mask;
    path[j][i] = mask;
}

int solve(int n) {
    vector<int> memo(1 << n, -1);
    function<int(int)> dfs = [&](int state) -> int {
        if (memo[state] != -1) return memo[state];
        if (state == (1 << n) - 1) return 0;
        
        int idx = 0;
        while (state & (1 << idx)) ++idx;
        int res = 1000;
        
        for (int i = 0; i < n; ++i) {
            if (path[idx][i]) {
                int next = state | path[idx][i];
                res = min(res, 1 + dfs(next));
            }
        }
        
        return memo[state] = res;
    };
    
    return dfs(0);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
        
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                build_path(i, j, n);
            }
        }
        
        cout << solve(n) << endl;
    }
    return 0;
}

どちらの実装も、枝刈り処理によって効率化されています。特にバックトラッキング方式は最悪ケースでも81msで処理を完了します。