結果

問題 No.2675 KUMA
ユーザー nu50218
提出日時 2024-05-19 09:25:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,137 bytes
コンパイル時間 861 ms
コンパイル使用メモリ 84,792 KB
最終ジャッジ日時 2025-02-21 15:50:40
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1 -- * 1
other -- * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <tuple>

using namespace std;

vector<pair<int, int>> get_observable_positions(int x, int y) {
    vector<pair<int, int>> positions;
    positions.emplace_back(x + 2, y - 1);
    positions.emplace_back(x + 2, y + 1);
    positions.emplace_back(x - 2, y - 1);
    positions.emplace_back(x - 2, y + 1);
    positions.emplace_back(x - 1, y - 2);
    positions.emplace_back(x + 1, y - 2);
    positions.emplace_back(x - 1, y + 2);
    positions.emplace_back(x + 1, y + 2);
    return positions;
}

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> umas(N);
    set<pair<int, int>> uma_positions;

    for (int i = 0; i < N; ++i) {
        cin >> umas[i].first >> umas[i].second;
        uma_positions.insert(umas[i]);
    }

    set<pair<int, int>> all_positions;

    for (const auto& uma : umas) {
        auto positions = get_observable_positions(uma.first, uma.second);
        for (const auto& pos : positions) {
            if (uma_positions.find(pos) == uma_positions.end()) {
                all_positions.insert(pos);
            }
        }
    }

    vector<pair<int, int>> kma_candidates(all_positions.begin(), all_positions.end());
    int min_kma_count = N;  // 最小値は最大でもN

    int candidate_size = kma_candidates.size();
    for (int bit = 1; bit < (1 << candidate_size); ++bit) {
        set<pair<int, int>> observed_positions;
        for (int i = 0; i < candidate_size; ++i) {
            if (bit & (1 << i)) {
                auto observable = get_observable_positions(kma_candidates[i].first, kma_candidates[i].second);
                observed_positions.insert(observable.begin(), observable.end());
            }
        }
        bool all_observed = true;
        for (const auto& uma : umas) {
            if (observed_positions.find(uma) == observed_positions.end()) {
                all_observed = false;
                break;
            }
        }
        if (all_observed) {
            min_kma_count = min(min_kma_count, __builtin_popcount(bit));
        }
    }

    cout << min_kma_count << endl;

    return 0;
}
0